ラベル 値変更などのクエリ→セグメント木 の投稿を表示しています。 すべての投稿を表示
ラベル 値変更などのクエリ→セグメント木 の投稿を表示しています。 すべての投稿を表示

2020年5月23日土曜日

CodeCraft-20 (Div. 2)

 Dまで四完でした。Bで手間取ったため順位はイマイチ。
 日本語の解説記事があったので、復習のときは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


 制約からbit DP(かbit全探索)だろうな、と予想できる。
 問題は、どうやってその枠組みへ落とし込むかだけど、応援力(Aで与えられるもの)をソートしてやると、i人目まで決め、その選手をどのポジションにも選ばないと決めたとき、応援にまわすか/まわさないか、が決まるのでbit DPできる。

 結構自然な解法なんだけど、なぜか正当性が分からなくなって悩んでしまった。この問題の正当性というよりは、bit DP自体の正当性について悩んだ。部分集合で最善? それを二つに分けたとき、両方最善な必要がある? とかって。
 そういうことを考える必要はなくて、bit DPの正当性は、「最後にxを選んだとき」を考えて帰納法を回していく感じで言えますね。

 なお、この問題はPython/PyPyでは通せずKotlinでACしました。Kotlin Heroesが近付いているので、久々にKotlinを使ったけど、結構書きやすい!

F. Battalion Strength


 ゆるふわ競プロオンサイト #3のSweets Distribution(Hard)もそうですが、

・値変更などのクエリ→セグメント木

 は定番なんですね。

 ただ、どうやってセグメント木で処理するか、何をセグメント木に乗せればいいかも難しい。idsigmaさんの解説記事にはその辺りも全部書いてあるのですが、それでも理解するのに苦労しました。
 「求めたい値を、セグメント木で自分の下に位置する二つのノードから求めるためには何が必要か?」とちゃんと式を書いて考えれば分かると思います。

 さて。
 解法は理解できたのですが、TLEやMLEのためPyPyでACすることはできず、結局C++でACしました。(AtCoderのコードテストだとランダムケースで三秒ほどの実行時間なので間に合いそうなのですが、Codeforcesだと15秒くらいかかってしまう)

 ただ、pajenegodさんはPyPy2で通しているんですよね。他の人がPyPyで通している問題で、PyPyでのACを断念するというのは悔しいのですが……。仕方ない。

2020年5月9日土曜日

ゆるふわ競プロオンサイト #3 (Div. 1)

 三完+部分点で終了。
 結構がんばったのだけど、難しい問題は解けず悔しい出来でした。
 しかし、改めて復習すると、解けなかった問題はどれも解けそうになかった気がしてしまった。

コンテストへのリンク

解説スライドはここ

Bananas Multiplier

 LCAは書けますか? という問題。

Banana Game

 解説AC。
 Grundy数を知っていればやるだけの問題。
 Grundy数についてはふるやんさんのブログが分かりやすいと思う。

 ……が、その「やるだけ」のはずのパートが難しくないですか?
 Grundy数を調べるのも、そこから規則性を見つけるのも結構難しい。コンテスト中は、Grundy数の記憶が曖昧だったから飛ばしたけど、飛ばさずやったとしても非常に時間がかかった(もしくは、終わらなかった)気がする。

Sweets Distribution(Hard)

 解説AC。(Python3でACしましたが、同じコードをPyPy3で提出したらTLEでした)
 公式解説も分かりやすいし、検索すれば他にもいくつか解説(私にはアルメリアさんの解説が分かりやすかった)が出てきます。

 こういうものがセグメント木に乗る、ということを初めて見たので驚きました。面白い。
 「二点変更クエリを処理する」と思えば、セグメント木を使うのは不自然ではないですが、とはいえ、似たようなことをやったことないとセグメント木を使うという発想は出にくい気がします。

Yet Another Cake Division

 アルメリアさんの解説けんちょんさんの解説を見て解説ACはしました。
 (答えの式が書いてあったので、それを書いただけとも)
 最初の一手も、その後の考察も難しい……。

Digit Sum Multiple

 解説ACはしました。
 公式解説を読んだとき、「下k桁が$2^k$の倍数であるような整数」を見つける部分をどうすれば良いか分からなかったのですが、けんちょんさんのブログ記事に構築の仕方が書いてありました。
 いや実際は、公式解説にも帰納法で証明できる旨は書いてあったので、それをちゃんと実行すれば分かったんですよね。