Rustコトハジメ

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

東京工業大学プログラミングコンテスト2019 反省会

参加者のみなさん5時間お疲れ様です。

東京工業大学プログラミングコンテスト2019 - AtCoder

最初から頭の6問に取り組むつもりだった。この6問が最弱のセットらしいので。

f:id:akiradeveloper529:20190831173915j:plain

5完出来た。400埋めの成果が着実に出ているといえる。

C

コーナーケースが厳しい問題だった。順位表を見ると、多くの人がハマっていたように感じる。

欠損値以外のxorと、Xのxorをとって、欠損値にそれを適用するというのが第一感だが、この値がXを超えている場合があるというのが罠。おれはassertを仕込みまくって何回かWAしたあとに気づいた。

この場合、X xor Yの2値で欠損値を作ってあげることを考えればよい。証明はしらんけど、0部分を埋めることで全ビット1は作れるので、これで作れないならたぶんだめでしょうという直感的な理解。

D

きたあああああああああ!!!!!!!

勉強の甲斐がありました!Grundy数。

www.rustforbeginners.com

一つの山の石数についてGrundy数を計算していけばいいんだけど、「素数分しかとれない。結果の石数も素数じゃないといけない」という制約があるため、奇数個から2と、奇数個からその数-2しか飛べないということがわかる。これで地道にGrundy数を計算すればいい。

素数の性質とGrundy数をかけたすごくきれいな問題。

おれは、13->11のようなジャンプが出来ることに気づかずに、叫んでた。

E

明らかにN偶数ではだめ。なぜかというと、各行各列のmodNを足したら、0になるはずだが、N偶数の場合そうならないため。

1つ出力せよ系は何か明らかな作り方を見つけるというIQテストに帰着するのだが、1時間くらい狂気の試行錯誤をして、なんとかひねり出せた。(ノートは横に使う派です)

f:id:akiradeveloper529:20190831175024j:plain

modNについて

01234 01111 02222 03333 04444

のようにすればよいです。

少しだが、

D - Five, Five Everywhere

の考え方に似てるかも知れない。

F

おれの考えていた方針は、ノード1からNの他に0とN+1をくっつけて、0からw,y、x,zからN+1へのコスト0キャパ1のエッジをつけ、全体に流量2を流す時の最小費用流に帰着させる(その他のエッジはキャパ2)というもので、それだとエッジを共有した場合にコストがかさ増しされるから、最後に、各エッジのキャパを調べて0になってるものがあればその分のコストを減らして調整すれば良いかなと思っていたのだが、

ライブラリがなんか動かなかった。つらすぎ。