Rustコトハジメ

プログラミング言語Rustと競プロに関する情報をお届けします。

技術室奥プログラミングコンテスト#4 Day2 反省会

地獄のような難しさであった。Aしか解けなかった。

技術室奥プログラミングコンテスト#4 Day2 - AtCoder

B

最初に出したのがリーフの数を数えて2以上だったら死というもの。これは4つを除いて全テスト通ってしまうけど、明らかに間違っている。リーフがない場合すらある。

方針としては、まじめに再帰して枝分かれを探索する。実装例の中で良いと思ったのは、

  • 巻き戻りをなくすために再帰関数に前のpreを渡している。エッジは双方向なので、preも探索してしまうが戻ってしまうのは本意ではないため。これすら思いつかなかった
  • 純粋な枝分かれをinfという数で実装している点。わかりやすいとは思うけど、Rustならenumで実装してより明確にしてしまうかもしれない

現状ではこの問題をコンテスト中に出来るとは思えなかったので、探索の実装方法のみを学びとする。

C

計算で求まるであろうというのはわかるのだが、「天使がBを奇数ぎりぎりまでとると仮定した場合のそれぞれのとり方が実現可能かどうか調べる」という方針でやり始めたところ破綻した。

解説の中でそこまではたどり着くべきだったと思うのは、まずオーダーは無視して愚直にDPしてみるという点。解説ではそこから規則を見出している。先手後手それぞれ最善を選ぶ系はまず愚直にDPから考えるくせをつけたい。

D

Axが求まること、Ay+Azが求まることはわかった。和の形なので、片方を決めたあと二分探索する形というのが第一感だった。

こういう式はとりあえず、全部の和をとってみたくなる。

D - Rain Flows into Dams

これもそういう感じだった。

なので、次に、仮にAがソートされているならば、それぞれのAyについてAzの個数がlog(upper_bound-lower_bound)で求まるから、なんとかなりそうという感じはしていたが、現実はソートされていない。

解答は、逆からたどっていって、Azの出現カウントを持っておき、あるAyに出会った時にそれとペアになれるAzが何個あるか調べるというもの。こうすると、AyからそれとペアをなすAzのカウント数の累積和が計算出来るから、各Axについて足し合わせていけばおわり。

BITというデータ構造を持ったままイテレートするという点においては、LISに似ている。

逆に辿るという点では

E - Sequence Decomposing

とも共通点がある。逆に考えるというのはAtCoderではよく見られる解法だと思う。

あまりにもわからなすぎて途中から「新入生なんか歓迎しなくていいんだ!!」と叫ぶ異常を起こした。

E

第一感で思ったのは、「あるlを採用したときに条件が満たされるか」という関数を考えて、二分探索してLを探索するというもの。満たされるかは、実際にlより大きい路線を抜いた上でUnion Findでグループ分けするつもりだった。しかしこれは、解説にある愚直案より悪い解法で、逮捕どころか即死刑に相当するものだった。

もしこの方針でやるとしても、エッジを昇順ソートして短い方から近づけていって、条件が満たされた瞬間の長さを採用すればいい。これが愚直解。正直今の自分としてはもしここまで安定して思いつけるならば十分という気がする。(そんな意識の低いやつは競プロから去れと言われるかも知れないがそうしたら腕力で対抗する)

解法はそこから発展して、集合サイズの分布を調べていく方針で進めている。そうすると、最小集合サイズがx(単調増加)になった時のUF内の最大のエッジ長が毎回わかるので、これを予め記憶していく。

そして、あとはクエリにO(1)で答えていくというのが想定解法。

クエリがたくさんあって、それぞれに答えていく系では、このようにそもそも予め計算してしまってそれから答えるものが多い気がする。毎回そうかは知らん。

これも同様に途中でブチ切れて「全員引きこもってろクソが」と叫んでいた。

F

よくわからない。

G

平均がtになるか?という関数を考えて、二分探索するという方針が良いらしい。

AtCoder 版!蟻本 (中級編) - Qiita

によると、

「a[0], ..., a[n-1] の平均が K 以上」を「a[0]-K, ..., a[n-1]-K の総和が 0 以上」にするテクは二分探索に限らずちょくちょく見る印象です。

と書いてあるが、これならば今何個あるか不問になるからパラメータが減らせるという意味だろうか?エッセンスだけのもっと簡単な問題を解く方がいいと思った。