久しぶりすぎてすみません、予定がうまくかみ合わなくて出れない回が...
今回は6分くらい遅れての参加
94:16 7完 60位(わーい！)
A Integer Sum
Aでforだ！とは思うけど、学んだことそのまま活かせるので簡単なのかも？
初心者が1問目は解けるといいですよね
(AC 9:23)
B Everyone is Friends
二重ループをたくさん回します、考察はあんまいらないよくあるBですね
友達かどうか？を二次元配列で管理するのがいいかな
(AC 13:12)
C Max Even
知識はいらなくて、ちょっと考えれば解けるCすき
2つ足して偶数＝(偶数+偶数) or (奇数+奇数)なので、偶奇でわけてソートしてあげればよいです
サンプルにもあるけどできない時だけ注意
個人的にはBより簡単だし、そう思う人の方が競プロ楽しめそう(めっちゃ偏見ですみません)
(AC 16:17)
D Root M Leaper
最初寝ぼけて誤読して、全点対の最短距離だと思ってた
(1,1)からの最短距離なので、BFSやDijkstraあたりに落とし込みたいところです
1つの点からどこに行けるか？がわかればよいので、xの変化分(= i-k)を固定してみます
そうすると、(j-l)^2も一意に定まります
Mが10^6なので、i-kは10^3まで考えてあげればよいです、と思いきやそもそも盤面がそんなに広くないのでN-1まで考えればよいです
i-kやj-lの値はプラスマイナスどちらもとれることに注意しながら辺を全部張って最短路問題を解けばできました
(AC 27:52)
E Add and Mex
なんか無駄なハマり方した...
まず、MEXの最大値はNです(0,1,2, ... N-1のN個となったとき)
つまり、見る必要のある値は0~N-1のみでそれ以外は無視してもかまいません
さらに思うことがあって、iが大きいときはめちゃくちゃ値がとびとびになります
たとえば、i = 100, Ai = 0なら、0,100,200,...となってすぐにNになってしまいそうです
これが実は少ないといいな～と思うんですが、なぜかこの合計をN*(N-1)/2と見積もってしまいました
となると、どうしよう？？となります
Aiに加えられる数が1ずつ増えることを考えると、階差をみてみるといいかな？と思います
あらかじめAiでソートしておいて、大小関係が入れ替わるたびにswapすると、回数が抑えられるとかないかな～？と思います
でも最大ケースでN*(N-1)/2回のswapが起こりそうで困ります
ぼーっと考えていると、さっき考えた「実際に気にしないといけない数」は N/1 + N/2 + N/3 + ... N/Nなので調和級数であることに気づきました(なんで？)
これならNlogN程度になるので間に合います
ということで、マイナスの場合は0以上になるまでジャンプして、そこからNを超える(またはM回目以降になる)まで足していくことで必要な値を列挙できます
あとはこれを全部見てMEXを計算してあげればよいです
MEXの計算は、i回目の操作ごとのsetやvectorをつくってソートしてあげればよいです
(AC 51:53)
F Two Strings
ABC-Fの文字列が主眼っぽいやつ、とりあえずSuffix Array考えるのいい説
ということでSuffix Arrayを考えます
まず、「操作」は単に文字列をrotateしているだけで、S+Sのように2つ連結してしまえば、その中の連続した文字列になります
ということで、S+S+T+Tをつなげた文字列をつくって、そのSuffix Arrayを考えてみましょう
f(S,i) ≦ f(T,j)ということは、基本的にSuffix Arrayを考えたときに、f(S,i)の時の値≦f(T,j)の時の値であればいいかなと思います
ただし、一つだけ面倒なことがあります
それはf(S,i) = f(T,j)の時で、AAASSSZATTTAAA (S,Tがそれぞれf(S,i), f(T,j)の位置)みたいに直接含まれないものによってSuffix Arrayの値が入れ替わってしまうことがあります
ここで登場するのがLCP Arrayです
LCP Arrayではi番目とi+1番目の共通接頭辞の長さが求められるので、もしf(S,i) = f(T,j)であればLCP Arrayが「もとの文字列の長さ」以上になります
この性質を用いて以下のようにSuffix Arrayの前からループを回します
1. もしSA[i] がN~2N-1, 3N ~ 4N-1ならば、これはf(S,i), f(T,j)のいずれでもないのでスルーします
2. もしSA[i]が2N~3N-1ならば、これはf(T,j)のひとつです
まだ後に出てくるf(S,i)に等しいかもしれないので、候補として数えておきます
3. もしLCP[i-1]がN未満であれば、後に出てくるf(S,i)に等しい可能性はなくなるので、候補をすべてクリアします
4. もしSA[i]が0~N-1なら、これはf(S,i)のひとつです
前にあるけど等しいもの + 後ろにあるもの の2つの個数を足してあげればよいです
少し書き方が違いますがコードをはっておきます
(AC 74:23)
G Yet Another mod M
順位表をみるとそれなりに通されているのでがんばるぞ！と思って考えます
まずN≦5000なので、2乗で何かできないかな？と思うと、全ペアの差をとれそうです
もしAi mod M = x かつAj mod M = xなら、 Ai-Aj ≡ 0(mod M)となります
つまり、Ai-Ajの約数が候補になることがわかります
実際にサンプル2で試してみるとうまくいくんですが、これを愚直にやるとO(N^2 sqrt(Ai))なので、さすがに間に合わなそうです
dp[i][j] = i番目までみてあまりjのものの数、みたいなDPできないかなとも思うんですが、Mの値が大きい場合にあまりを持てなくて困ります
Ai-Aj ≡ 0(mod M)、これをもう一度考えると、i = 0のケースだけに限定する、つまり1つの項は絶対使うとするとうまくいかないかな～と思います
でもこれは落とそうと思うとダメなケースがあるので、ならランダムにシャッフルしちゃえばよくね？と思いつきます
そう思うと、適当にとっても過半数もあるならだいたい当たりそうな気もしてきます
時間がないので、「ランダムに2項とってその差の約数を候補として試す」ことを繰り返すことにします
回数もよくわからないので、ある程度いい感じになりそうな100回にしてみます
ダメもとで出すと... AC！非想定かと思ったら想定でした
(AC 94:16)
総括
ABC最高順位更新うれしすぎる
