こんにちは, Shinoryoです.
今回はAtCoder Beginner Contest 204を, Pythonで解いてみた結果を書き連ねていこうと思います.
AtCoder Beginner Contest 204 - AtCoder
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
A - Rock-paper-scissors
$x$と$y$が等しければ同じ数を, $x$と$y$が異なればそれらではない数を出力すればよいです. もちろん, 全ての場合を列挙しても構いません.
B - Nuts
リスト$A$の各要素から$10$を引いて下限を$0$にしたリストを合計すればよいことが分かります.
C - Tour
ある都市に対して, その都市からどの都市に道がつながっているかを調べて, 行くことができる都市を数え上げることを考えます. これを数え上げる有効な方法として, AtCoder Beginner Contest 177の「D - Friends」と同様に, 幅優先探索(breadth first search; BFS)と呼ばれる方法を用います.
AtCoder Beginner Contest 177をPythonで解く
こんにちは, Shinoryoです. 今回は AtCoder Beginner Contest 177 を, Pythonで解いてみた結果を書き連ねていこうと思います. AtCoder Beginner Contest 177 - AtCoder AtCoder is...
D - Cooking
$T_1$から$T_N$までの和を$T_{\mathrm{sum}} = \sum_{i=1}^N T_i$とします. 1つ目のオーブンを使う時間が2つ目のオーブンを使う時間以上であると仮定してよく, このとき, 1つ目のオーブンを使う時間は$T_{\mathrm{sum}} / 2$以上になります. つまり, $T_1$から$T_N$までの部分和で作れる数のうち, $T_{\mathrm{sum}} / 2$以上の最小値を求めればよいことが分かります.
この問題は「$T_1$から$T_N$までの部分和で$x$を作ることができるか？」という問題を各$x$に関する解けば十分です. $x$は$0$から$T_{\mathrm{sum}}$まで調べます. 以下ではdp[i][j]を$T_1$から$T_i$までの部分和で数$j$を作ることができるか(True or False)とします.
$T$を用いずに数$0$を作ることができるので, dp[0][0] = Trueとします. $T$を用いずに数$1, 2, \ldots$を作ることはできないので, dp[0][1], dp[0][2], ……はFalseのままにしておきます.
原則として, $T_1$から$T_i$までの部分和で数$j$を作ることができるならば, $T_1$から$T_{i + 1}$までの部分和で数$j$を作ることができます(dp[i + 1][j] = dp[i][j]).
$T_{i + 1} \leq j$ならば, $T_1$から$T_i$までの部分和で数$(j - T_{i + 1})$を作ることができることを条件に, $T_1$から$T_{i + 1}$までの部分和で数$j$を作ることができます(dp[i + 1][j] = dp[i][j - T[i]]).
以上のようにすることで, 「$T_1$から$T_N$までの部分和で$x$を作ることができるか？」という問いに答えることができます. Python (3.8.2)ではTLEですが, PyPy3 (7.3.0)ではACとなります.
E以降
E以降は私の能力不足故に省略いたします.
0 件のコメント:
コメントを投稿 (Please feel free to ask me about your questions! You can use Japanese or English in the comments.)