人間だけど競プロやる

解けなかった問題を理解できたら記事を投稿します。日本語の解説が見つからなかったもの中心。

Codeforces Round #851 (Div. 2) D. Moving Dots

Codeforces


主客転倒がすんなり発想できたけど、実装バグって間に合わなかった。
残念だったので簡単に書いておく。


2点だけを決めると真ん中に一つの不動点ができる。
いわゆる主客転倒で、この不動点が現れる組み合わせを数える。
任意の2点a ,b (a < b)を決めた時、

  • a ,bの間には他に選ばれる点はない。（間の点を選ぶと、別の不動点ができるか、同じ位置に別の2点によって不動点がつくられる）
  • a ,bの距離をdとするとき、aから左にdより大離れた点は選んでも選ばなくても影響しない。（等しい場合aが左に動いてしまう）
  • a ,bの距離をdとするとき、bから右にd以上離れた点は選んでも選ばなくても影響しない。（等しいときはbは左に動くので影響しない）

よって選んでも選ばなくても良い左側の点の数をL、右をRとして、
任意のa,bにたいして、
\sum {2^{L} \times 2^{R}} が答え。


本番ではL,Rを2分探索で求めようとしてバグってしまった。
L,Rを両端キューで管理して、尺取のような要領で管理したほうが楽だった。(aを決めた時、bを動かしていくとdは単調増加)

Educational Codeforces Round 140 (Div.2) C - Count Binary Strings

Codeforces

まずは条件を整理する。
インデックス i,j,k があって（ i \lt j \lt k ） 、

  • i から i までで条件が「2」のとき、長さ1に \{0,1\} 両方を含むことはできないので明らかに0通り。
  • i から k までの条件が「1」で j までの条件が「2」のとき j までに2種類を含むので0通り。

以上から答えが「0」のときは予め出力して処理を打ち切っておく。

上の条件を含まない時、

  • i から j の条件が「2」のときかつ k の条件が「2」のとき、k の条件は「0」と同一視してよい（\because i から j ですでに二種類ふくむ）。
  • i から k の条件が「1」のとき、すべての j の条件は「1」と同一視してよい。

よって i が始点になる条件は、「 最後の条件1のインデックス」と「最初の条件2のインデックス」だけが必要になるので変換しておく。




解法
最後に「0」になったインデックスと、最後に「1」になったインデックスを保存してDPをする。
dp[i][j][k] = i番目までみて、最後に「0」になったインデックスがj、最後に「1」になったインデックスがkとする。
遷移は次に「next = \in \{0,1\}」どちらにするかを試して、条件に違反しないなら
dp[i+1][nj][nk] += dp[i][j][k]
（nj,nkはnextの値によって最後の \{0,1\} のインデックスに更新する）

N \le 100 で条件がO(N)あるので遷移もO(N)かかかって、全体でO(10^8) 。

実装上ではインデックス0を「\{0,1\}」を使用していない状態とした。
よって初期化は dp[0][0][0]=1 。





条件に違反しないかの判定

（以後インデックス0は未使用状態を表すので1-indexedになっている）
例えば、j=5 ,k=8 のとき「****0111」となっている（＊は \{0,1\} どちらでもよい）。

ここで x=max(j,k)+1 （xは今更新してようとしているインデックス）として、
iからx までが「条件1」とすると、

  • i \lt k のとき明らかに2種類含むので不適。
  • j \lt k なので次に採用する値next が「0」なら不適（今決めようとしている一つ前のインデックスの状態はj,kの大きい方になってるいる）。

「条件2」の判定は「条件1」の逆になる（連続しないなら2種類の数字を含む）
j,kの大小と、0（未使用）のときも含めてうまく書く。


以上を実装してAC。

Educational Codeforces Round 139 (Rated for Div. 2) D. Lucky Chains

Codeforces

d = y-x。Pをdの素因数の集合とする。

\displaystyle{ f(p) = \lceil \frac{x}{p} \rceil \times p - x }
\displaystyle{ \forall p \in P について \qquad min \lbrace f(p) \rbrace }

が答え。

xとyは互いに素なので両方が、dの素因数pの倍数であることはない。 またdがpの倍数なのでxがpの倍数の場合、yもpの倍数。 よってxとyは共にpの倍数ではない。
以上からxとyにある数f(p)を足すことでx,y両方をpの倍数にできる。
dのすべての素因数にたいしてこの足す数f(p)の最小値が答え。

注意点1。 y-x=1のとき出力する答えは-1。「差が1の2数は互いに素 \rightarrow gcd(x,y)=1」は有名事実。いくつ足してもxとyの差は1のままなので、永遠に互いに素。
注意点2。 上の考察を素直に実装するとTLEになる。素朴に高速化するとMLEになった。いい感じに実装する必要がある。

イメージ図

AtCoder Beginner Contest 281 (ABC281) F. Xor Minimization

AtCoder




i=0..NにたいしてA_i \oplus xを最大値として採用できるように、かつA_i \oplus xをできるだけ小さくするxを求めて、これらの最小値が答え。


どうやって計算するか。
2進数で考える。
A_i \le 2^{30}より30桁考えれば良い。上の桁から決めていきたいので、以下では左から0,1,2..桁目と数えることとする。
A_i \oplus xが条件を満たすように、j-1桁目までxを決めたとする。その時xのj桁目を0,1のどちらにするのが最適か決めることができる。



0からj-1桁目までが一致している数があり

  1. j桁目が0,1両方ある時 \Rightarrow A_iのj桁目が「0ならA_i \oplus xのj桁目は1」、「1ならA_i \oplus xのj桁目は1」にしないと、A_i \oplus xが最大値として採用されない。
  2. j桁目が0,1片方しかない(=A_iのj桁目が0,1のとき) \Rightarrow A_iのj桁目が「0ならA_i \oplus xのj桁目は0」、「1ならA_i \oplus xのj桁目は0」にすると、A_i \oplus xが最大値として採用されて、かつA_i \oplus xを小さくできる。

どうやって実装するか。
あらかじめ入力されるAを2進数表記でグラフ（二分木）に変換しておく。
このグラフ上で上の条件は

  1. 親が0,1両方をもっている時
  2. 親が0,1片方を持っている時

と言い換えることができる。
以上を実装してAC。

サンプル1のとき

AtCoder Beginner Contest 224 (ABC224) E - Integers on Grid

AtCoder

グラフを作ってからメモ化再帰で答えをもとめる。
数字が大きいところにしか辺を貼れないので、グラフはDAGになる。



あるマスから行または列の、自分の次に数が大きいマス（複数ありうる）に辺を貼る。
「自分の次に数が大きいマス」にだけ辺を貼れば良い。なぜなら、解の経路が「自分の次の次に数が大きいマス」を使う場合、一つ小さい「自分の次に数が大きいマス」を経由したほうが常に得だから。
（問題の性質上、使用したマスより小さいマスをあとから使用することはできない）


注意点としてこのまま実装すると1テストケースでTLEだった。
同じ数字のマスが大量似合った場合、最悪O(N^2)の辺が貼られることになりそう。
行・列内で同じ数字について超頂点を追加して、これを経由することで解決できた。
超頂点を経由するときに移動回数として数えないように注意。

AtCoder LINE Verda プログラミングコンテスト（ABC263）F - Tournament

AtCoder


kyopro_friendsさんの公式の解説の通り。
解説動画がくれば詳しく解説してくれそうだけど、実装に時間がかかったので残しておく。


dp[i][j] = i番目の試合でj番目の選手が勝ったときの、得られるポイントの最大値とする。
遷移はdp[i+1][j] = (i+1)番目の試合でj番目の選手が勝ったときの最大値で、


dp[i+1][j] = dp[i][j] - (i-1)番目の試合でjが勝ったときのポイント + dp[i][jと反対のブロックの範囲]の最大値 + i番目の試合でjが勝ったときのポイント


となる。
（ポイントは何回目に勝ったかなので、前の状態から勝利ポイントを引かないといけないことに注意）
反対のブロックは公式解説の図の通り。


問題はこの反対ブロックの範囲を求める方法で、jに対してbit演算を適切に行うことで求めることが出来る。
方針は2つ思いつた。

  • セグ木などを用いて、範囲の最大値を求める

左端をl、右端をrとする。
j のi bit目が0なら右側、1なら左側のブロックと足すことになる。よってiビット目にたいしてxor 1をとって、0なら1、1なら0に変更して、下位ビットを0にすれば、左端が求まる。
l = ((j>> i ) ^ 1) << i;
となる。
ブロックのサイズが2^iなので
r = l + (1 << i );


  • ブロックが何個目になるかを管理してその都度maxを取っていく（速い）

遷移ごとにブロックごとのmaxを記録していく。
セグ木がいらないのでこっちのほうが軽い。
i番目の試合で見るべきブロックを
index = (j >> i)^1;
i番目の試合が属するブロックのindexを、
index2 = (j >>(i+1))
とする。
ブロックを保存する配列のサイズは \frac{1 << N} {1 << i} （ブロックのサイズが2^iなので）