メメメモモ

プログラミング、筋トレ、ゲーム、etc

G - Distance Queries on a Tree

以下の問題の解説を理解するための知識をまとめてみました。 atcoder.jp 繰り返し二乗法 繰り返し二乗法とは、x1, x2, x4, x8, x16, ... を組み合わせて、xnを高速で計算するアルゴリズムです。 x1, x2, x4, x8, x16 は、二乗していけば、簡単に求めていくこ…

037 - Don't Leave the Spice(★5)

atcoder.jp DPをしつつ、セグメント木で高速化する。 普段は配るDPで実装することが多いが、この問題では貰うDPで実装するほうが良さそう。 dpの更新は、セグメント木から前段のLからRの間の最大値を取得する。 セグメント木の更新は、dp[i]の値を一通り一気…

036 - Max Manhattan Distance(★5)

atcoder.jp 2、3回解いているが、なかなか覚えられないのでメモ。 マンハッタン距離が出たら、ひとまず45度回転を考えるのは覚えていた。 45度回転の方法は (X, Y) = (x-y, x+y) を計算すること。 45度回転すると、距離の領域が正方形になり、処理がしやすく…

B - Gift Tax

atcoder.jp ソートして、最小値と最大値に対して、操作を繰り返せば良いかなと思ったが、うまくいかずにTLE。 答えに上限があることは分かったが、2分探索する発想はできなかった。 典型問題の「答えで2分探索する」は思いつきたかった。 そのあとの判定問…

A - Trailing Zeros

atcoder.jp 末尾がT[i]個の0になっている整数を作っていけば良いことは分かったが、作り方の方針が誤っていた。 「2T[i] で割り切れて、2T[i]+1で割り切れない整数」と言い換えられるところは典型っぽい考え方か? 上記の条件に加えて、「A[i-1]より大きい整…

C - Multiplication 3

atcoder.jp 浮動小数点の理解があまかったせいでACできなかった。 100倍して計算結果を100で割るところまでは思いついたが、キャストの部分でも誤差が出ることを理解していなかった。 例えば 0.79の場合、2進数で表すと 0 .1100101000111101011100001010001…

B - A^B^C

atcoder.jp 1の位の周期性を考える。 BCは繰り返し二乗法で求めて、周期の長さで割れば良い。 周期の中でどの位置にあるのかを求めるのが少し苦戦してしまった。 例えば、3 の周期は「3 9 7 1」の長さ4であり、39 の場合は周期により、1となる。単純に 9 % 3…

C - ±1 Operation 1

atcoder.jp 茶diffらしいが、実感としては緑diffくらいに感じる。 値の範囲にマイナスが含まれているので、場合分けや反転させる処理が思いつけなかった。 値の範囲が正のみ(D>0 && A,X > 0)であれば、特に難しいことはない。 負の場合(D<0)、反転するには、…

B - Village of M People

atcoder.jp 結構雰囲気で解いてしまった。 まずceil(AiM/N)でBiをざっくり求める。 Biの合計値を算出したら、Mと差分が出るので、max(BiN - AiM)が最小になるように、Biの値を減らしていく。 max(BiN - Ai*M) が大きい順に減らしていきたいので、PriorityQue…

D - Flip and Adjust

atcoder.jp 表か裏かで遷移する動的計画法。 dp[i][j] := カードi,...,iまでの和をjにできるなら1、そうでないなら0 dp[i][j] = 1 の場合、以下の遷移をする。 - dp[i+1][i+a[i]] = 1 - dp[i+1][i+b[i]] = 1 dp[N][S]が1であればYes、そうでないならNo。 ま…