2019-01-14 キーエンス プログラミング コンテスト 2019 A - Beginning A atcoder 問題 自分はsetを使ったが、sortでも解ける。 変数4つが、[1, 7, 9, 4] なら"YES"、そうでないならば、"NO"を出力する。 pythonコード
2019-01-11 AtCoder Educational DP Contest / DP まとめコンテスト H - Grid 1 atcoder 動的計画法 H dp_h 動的計画法 壁以外のある地点(i, j)にいるとする。 そこにたどり着く経路の数は、(i - 1, j) + (i, j - 1) の合計をmodで割った余り。 迷路の周りを'#'で囲むとシンプルに解くことができる。 pythonコード
2019-01-10 AtCoder Educational DP Contest / DP まとめコンテスト F - LCS atcoder F 動的計画法 dp_f 蟻本の最長共通部分列問題の類題？ 最後に共通部分文字列を出力する必要があり、それに手間取った。 共通文字が存在するときはその要素の右下が1大きくなるので、逆に辿れば共通部分文字列の反転を得られる。それを反転して出力すればいい。 計算量がO(|s||t)で 9 * 106 のため、pythonでは制限時間内に間に合わせるのが難しかったので、c++で提出した。 一応pythonコード c++コード
2019-01-09 AtCoder Educational DP Contest / DP まとめコンテスト E - Knapsack 2 dp_e 動的計画法 蟻本p60の01ナップサック問題その他2の類題？ O(nW)では 1011 となり、配列が長すぎてしまうため、工夫。 重さではなく、価値の配列にすれば、O(nv)で 107となり、計算可能になる。 pythonでは間に合わなかったため、c++で提出した。 一応、pythonコード c++コード
2019-01-09 AtCoder Educational DP Contest / DP まとめコンテスト D - Knapsack 1 D yukicoder 動的計画法 dp_d 動的計画法 通常のナップサック問題。 重さが 105 なので、O(NW)では 107。 pythonでは間に合わなかったため、c++で提出した。 一応、pythonコード c++コード
2019-01-08 AtCoder Educational DP Contest / DP まとめコンテスト C - Vacation C atcoder 動的計画法 dp_c 動的計画法 現時点をiとし、aについて考える。 現在のa[i]を最大にするには、 a[i]に１つ前のa以外(b、またはcのうち大きいほう)を合計すればいい。 b,cについても同様。 そして、最終的に最大なものを出力。
2019-01-08 AtCoder Educational DP Contest / DP まとめコンテスト B - Frog 2 B atcoder 動的計画法 dp_b 動的計画法 前問のAの範囲が２つ前までだったのに対し、今回はKつ前までとなる。 問題自体は難しくないが、普通に解くと計算量がO(nk)となり、pythonでは間に合わない(numpy使って工夫しないかぎり)。 一応、pythonコード c++コード
