日本語の解説記事があったので、復習のときはEやFもACしよう、と思ったらかなり時間がかかってしまった……。
コンテストへのリンク
B. String Modification
実験してみれば、操作後のSがどうなるか分かるので、それらの最小値を見れば良い。
ただ、PyPyだと、それらをソートするとTLEになると思う。普通に、一回一回最小値を取っていけばOK。
自分は、コンテスト中これが思いつかず、一文字目で枝狩りをしてソートしたらACした。
なんか、最小値だけ求めれば良いところでList→ソートを使ってしまったり、上限の値が小さい正整数の、重複しない要素の個数を求めたいときにsetを使ってしまったり（上限の値までのListでOK）、本質的ではないところで遅い実装に走ってしまう癖がある気がする。気を付けたい。
C. Primitive Primes
一見難しいけど、実は簡単。Codeforcesでレートを上げたいならこういう問題を落とさないのが結構重要。
A, Bの係数のgcdが1でないので、素数pで割り切れない係数がA, Bのどちらにも必ず存在する。
それらの最小のものを足せばOK。
D. Nash Matrix
まず、動かない点を処理。
次に、その点がゴールになっている点をゴールからのDFSで処理。
その後、無限ループする点が、別の無限ループする点と接していればそちらへ向かわせる。
これらの処理をして、ちゃんと全ての点が埋まればVALID、ダメならINVALID、とする。
面倒だけど、やること自体は分かりやすい。
E. Team Building
けんちょんさんの解説記事、akiradeveloperさんの解説記事を読んで解説AC。
制約からbit DP（かbit全探索）だろうな、と予想できる。
問題は、どうやってその枠組みへ落とし込むかだけど、応援力（Aで与えられるもの)をソートしてやると、i人目まで決め、その選手をどのポジションにも選ばないと決めたとき、応援にまわすか/まわさないか、が決まるのでbit DPできる。
結構自然な解法なんだけど、なぜか正当性が分からなくなって悩んでしまった。この問題の正当性というよりは、bit DP自体の正当性について悩んだ。部分集合で最善？ それを二つに分けたとき、両方最善な必要がある？ とかって。
そういうことを考える必要はなくて、bit DPの正当性は、「最後にxを選んだとき」を考えて帰納法を回していく感じで言えますね。
なお、この問題はPython/PyPyでは通せずKotlinでACしました。Kotlin Heroesが近付いているので、久々にKotlinを使ったけど、結構書きやすい！
F. Battalion Strength
けんちょんさんの解説記事、idsigmaさんの解説記事を読んで解説AC。
ゆるふわ競プロオンサイト #3のSweets Distribution(Hard)もそうですが、
・値変更などのクエリ→セグメント木
は定番なんですね。
ただ、どうやってセグメント木で処理するか、何をセグメント木に乗せればいいかも難しい。idsigmaさんの解説記事にはその辺りも全部書いてあるのですが、それでも理解するのに苦労しました。
「求めたい値を、セグメント木で自分の下に位置する二つのノードから求めるためには何が必要か？」とちゃんと式を書いて考えれば分かると思います。
さて。
解法は理解できたのですが、TLEやMLEのためPyPyでACすることはできず、結局C++でACしました。（AtCoderのコードテストだとランダムケースで三秒ほどの実行時間なので間に合いそうなのですが、Codeforcesだと15秒くらいかかってしまう）
ただ、pajenegodさんはPyPy2で通しているんですよね。他の人がPyPyで通している問題で、PyPyでのACを断念するというのは悔しいのですが……。仕方ない。
0 件のコメント:
コメントを投稿