https://yukicoder.me/problems/no/874 前提知識 DP(【テク20: 編集距離】編集距離の計算は、2つの文字列の添字を持つDPでできる) 解説 https://yukicoder.me/submissions/374482 編集距離はDPで解けることが知られているので、とりあえずDPで考えてみよう。…

https://yukicoder.me/problems/no/873 解説 https://yukicoder.me/submissions/374460 42+32+22+11+11というのが決まれば、ここからバイナリを作るのは難しくないので、 二乗の和がNであって、底の総和が最小であるようなものを探せばいい。 まずは、実験す…

https://yukicoder.me/problems/no/872 解説 https://yukicoder.me/submissions/374451 全てのパスの長さの総和を求める問題であるが、こういう問題は集計方法を変えるといい。 全てのパスを列挙するのには、O(N2)かかるので、全てのパス全探索はしたくない…

https://yukicoder.me/problems/no/871 前提知識 二分探索 BFS 解説 https://yukicoder.me/submissions/374448 シミュレーションを考えてみる。 あるカエルが鳴くとそれに共鳴するのは、とある区間のカエルになる。 どこからどこまでのカエルかどうかの端点…

https://yukicoder.me/problems/no/870 解説 https://yukicoder.me/submissions/374446 シミュレーションしていこう。 A,B,Cの駒を動かしていって、最終的に指定の座標になるかを見ればいい。 駒毎に位置を持つのではなくて、盤面全体を管理すれば、操作はsw…

https://atcoder.jp/contests/jsc2019-qual/tasks/jsc2019_qual_e 解説 https://atcoder.jp/contests/jsc2019-qual/submissions/7125615 とりあえずは、解説放送を見るのがいい。 これを元にして考察過程を想像して書いてみる。 グリッドの問題は行と列をそ…

https://atcoder.jp/contests/jsc2019-qual/tasks/jsc2019_qual_d 前提知識 分割統治 解説 https://atcoder.jp/contests/jsc2019-qual/submissions/7125024 何もわからず解説を見てしまった。 分割統治を行う。 まず、パスが全て偶数になるために満たすべき…

https://atcoder.jp/contests/jsc2019-qual/tasks/jsc2019_qual_c 解説 https://atcoder.jp/contests/jsc2019-qual/submissions/7123399 何から手を付けていいかわからないかもしれない。 こういうときは、色々試していくしかないが、全探索対象を探してみる…

https://atcoder.jp/contests/jsc2019-qual/tasks/jsc2019_qual_b 前提知識 転倒数の計算 解説 https://atcoder.jp/contests/jsc2019-qual/submissions/7121477 Kの値が109なので、繰り返しの分をどのように効率的に計算するかが問題となる。 まず、2回Aを繰…

https://atcoder.jp/contests/jsc2019-qual/tasks/jsc2019_qual_a 解説 https://atcoder.jp/contests/jsc2019-qual/submissions/7120856 Mヶ月でD日なので、全部でMD日分あり、これは全探索が可能である。 全探索をして、条件を満たすものを数え上げよう。 i…

https://atcoder.jp/contests/tkppc4-2/tasks/tkppc4_2_g 前提知識 二分探索 DP 解説 https://atcoder.jp/contests/tkppc4-2/submissions/7037185 制約が割と小さい。小課題でヒントとして与えられている情報を考えると、dpできそうな感じがする。 dp[i][k] …

https://atcoder.jp/contests/tkppc4-2/tasks/tkppc4_2_f 前提知識 2次imos法 解説 https://atcoder.jp/contests/tkppc4-2/submissions/7036758 考え始めが難しい問題である。 制約にはこれと言った弱点が見つからない。 問題を見ると、「ちょうどゼロになる…

https://atcoder.jp/contests/tkppc4-2/tasks/tkppc4_2_e 解説 https://atcoder.jp/contests/tkppc4-2/submissions/7035886 何から手をつけたものかと思うのだが、何か全探索対象か固定できるものを考える。 q[i]を固定してみると、操作がやりづらいが、Lを…

https://atcoder.jp/contests/tkppc4-2/tasks/tkppc4_2_d 解説 https://atcoder.jp/contests/tkppc4-2/submissions/7034041 さて、何かを全探索することから考え始めるわけだが、xを固定してみよう。 すると、A[y], A[z]をどうするかという話になるが、まず…

https://atcoder.jp/contests/tkppc4-2/tasks/tkppc4_2_c 解説 https://atcoder.jp/contests/tkppc4-2/submissions/7033757 実験せよと問題が囁いてくるので、実験をする。 labo関数を使って、バックトラックで実験してみる。 眺めると、ゼロの個数は偶奇し…

https://atcoder.jp/contests/tkppc4-2/tasks/tkppc4_2_b 前提知識 全方位木DP 解説 https://atcoder.jp/contests/tkppc4-2/submissions/7033397 問題を少し読み替えて考えてみる。 全ての写真を集めることができない状況というのは、どういう状況だろうか。…

https://atcoder.jp/contests/tkppc4-2/tasks/tkppc4_2_a 解説 https://atcoder.jp/contests/tkppc4-2/submissions/7031891 操作を見ると、y座標は+2するしかないので、yが負の場合は達成できない。 目標のy座標の上限が105なので、多くても105/2回くらいし…

https://atcoder.jp/contests/abc138/tasks/abc138_e 解説 https://atcoder.jp/contests/abc138/submissions/7015274 文字列tを先頭から貪欲にs'からとっていく。 貪欲にとるためには、文字列sのある場所から一番近いどころにある、とある文字の座標を取って…

https://atcoder.jp/contests/abc138/tasks/abc138_d 前提知識 imos法 解説 https://atcoder.jp/contests/abc138/submissions/7014727 木上でimos法をやる。 頂点p[j]にx[j]を足す。この状態で根からある頂点の値を子供に足していく。 これを続けていくと、…

https://atcoder.jp/contests/abc138/tasks/abc138_c 解説 https://atcoder.jp/contests/abc138/submissions/7014597 abcの具材があったときに、((a+b)/2+c)/2=a/4+b/4+c/2のような場合が考えられる。 なるべく、分母が大きいものは、なるべく小さい数にあて…

https://atcoder.jp/contests/abc138/tasks/abc138_b 解説 https://atcoder.jp/contests/abc138/submissions/7014467 問題で与えられている計算を素直にやろう。 割り算は整数同士でやると、整数の結果となってしまうので、A[i]もdoubleで取得して、全体的に…

https://atcoder.jp/contests/abc138/tasks/abc138_a 解説 https://atcoder.jp/contests/abc138/submissions/7014434 A以上とA未満の場合分けをして、出力する文字列を分けよう。 int A; string S; //-----------------------------------------------------…

https://yukicoder.me/problems/no/868 前提知識 戻すDP 解説 https://yukicoder.me/submissions/370474 戻すDPを知っている人は、適用するだけである。 まずは、普通にDPを作ろう。 dp[i][k] := 配列Aのi番目まで使って、総和がkである組み合わせ 戻すDPを…

https://yukicoder.me/problems/no/867 解説 https://yukicoder.me/submissions/370451 まず、やはり気になるのは、制約である。 K2がついているし、かつ、A[i][j]の値がとても小さい。 これはKが増えれば増えるほど、K2による影響が増えていきそう。 なので…

https://yukicoder.me/problems/no/866 解説 https://yukicoder.me/submissions/370328 結構計算量が厳しいらしいので、ゴリゴリ計算系であろうと思う。 全探索で考えると、左上をHW通り試し、正方形の一片を試してmin(W,H)通り試す。 これだと間に合わない…

https://yukicoder.me/problems/no/865 解説 https://yukicoder.me/submissions/370121 クエリ計算を行っていくが、降水量が減ることはないため、 変化する分を計算すればいい。 ある個所が変更されたときに影響を受けるのは24区間である。 なので、その24区…

https://yukicoder.me/problems/no/864 解説 https://yukicoder.me/submissions/370113 ab + bc + cd + da = Kを変形していく (ab + da) + (bc + cd) = K a(b + d) + c(b + d) = K (a + c)(b + d) = K となるので、a+c, b+dはKの倍数になる。 なので、Kを2つ…

https://yukicoder.me/problems/no/863 解説 https://yukicoder.me/submissions/369283 計算量が線形時間であれば、Nが40倍になれば、かかる時間も40倍になっているはずである。 小数点切り捨てでAミリ秒なので、実際には、A.0～A.9999であるので、40倍する…

https://atcoder.jp/contests/agc037/tasks/agc037_a 前提知識 DP 解説 https://atcoder.jp/contests/agc037/submissions/6964393 AGCの頭ということで貪欲で解きたい気持ちをこらえて解法を考える。 順位賞を見ると爆速で解いている人もいるが、結構落ちて…

https://atcoder.jp/contests/otemae2019/tasks/otemae2019_e 解説 https://atcoder.jp/contests/otemae2019/submissions/6931414 問題を整理すると、校長がまず出発して、先頭から順番に前との距離がある一定の距離になったら歩き出すような 入場でよくある…