perarduaadastra

競技プログラミングとかをしています

ZONeエナジー プログラミングコンテスト “HELLO SPACE” 反省

久しぶりにまた情けない冷え方をした。ZONe飲んでからコンテスト出たんだしちょっとくらい色つけてくれてもいいんじゃないの〜?

 

結果を鑑みて

1000 35:52

853位となった。ABC級で水パフォを出したのはかなり久しぶり。学業やバイトを気にしなくてはいけなくなる時期は決まってとんでもないパフォーマンスを出してしまう傾向にある。それに加えて精進不足から来る視野の狭さ、定数倍感覚のズレによってえらい目に遭ってしまった。

 

A - UFO Invasion

直前に似たような問題をtwitterに投げていたので少しドキッとした。

 

B - Sign of Friendship

初見では角度が問題の本質だと思った。arctanや二分探索(今回は誤差はあまり気にしなくていいので)が思い浮かんだ。

「これ二分探索必要だったのか」と実装中に思いもしたが、普通に実装して通せた。

このときの順位は普通だったと思う。

 

C - MAD TEAM

Dを先に解いている。

最小値の最大化ということで二分探索が結びつくわけだが、これは最大値の最小値の最大化なのでなかなか一筋縄ではない。

制約的に考えると2乗対数時間だが、この場合定数倍が重いと破滅の可能性があり、定数倍は軽めに作る必要に迫られた。

答えを二分探索しながら二乗で2人選出して、残りの1人を選ぶ時、 足りない部分のパラメータを充足してくれるような人間を求めることになるが、これをO(1)時間で行わねばならない。

充足する必要のあるパラメータの組み合わせ2^5 - 1に対して、充足しなくてはならないパラメータの最小値が最大のものを先に選出しておけば良い。この前計算で解くことが可能になった。

ところで、この場合二分探索が必要なく、この31人の中から3人選べば十分だということに気付けたので十分実行時間に余裕を持って制することができた。

 

順位はこの時点で悪くはないものだったと思う。Eを速い時間で通せれば橙パフォに大きく近づくので本腰入れてEに取りかかった。

 

D - Message from Aliens

reverseしているかどうかを持ってクエリを処理していくような問題は最近何度か見ている。

いつも通りやるだけだが、先頭追加があるのでdequeで実装した。

 

結構手間取った気がしていたが、この時点で200位切っており好順位につけていた。

 

E - Sneaking

読んですぐ頂点倍加してのdijkstraであることには気付けた。頂点数が10^5を超えた時に自分のdijkstraは定数倍がでかすぎて通らないことがあったので、陽にグラフを持たない方針で空間計算量を削減して解くことにした。これがすべての始まり、あるいは人生の終わりだった......。

 

(y, x)→(y - 1, x)方向の移動についての処理が頭の中でぐちゃぐちゃになってしまい、結局7ペナつけた上に本番中に通すことができなかった。なお、陽にグラフを作ってdijkstraしても十分余裕を持ってACできた。

 

定数倍感覚を改める必要があるのと、微妙な計算量なら最悪ケースを作って試してみることを教訓、ぐちゃぐちゃ実装を作らないことを課題とした。

 

F - Encounter and Farewell

あまり読めていない。本番中ではおそらく合計5分くらいはこの問題を考えていた。

さて、Eまで一応復習したことだし今からこの問題を考えてみることにする。

 

-

 

全域木の問題っぽい。ある頂点xを木に加えることができる場合に後回しにするメリットはない。0からいろいろ繋いでいくことにしてよい。

補グラフが与えられての全域木問題と考えられるか。数列Aの補集合を取るとxor基底がいくらか得られて、これで1~2^N - 1を作る問題に落ちた。なるほど。Eで焦っている時にF見ても解けはしなかっただろうと思うのでまあいいか。

 

なんかここまで解けた気でいたが、構築パートが難しい。一旦基底に分解すると厄介だ。

基底で新たなベクトルに対してxorを行って新しい基底を作る操作は辺を張るのと同義。のはずなんだけれど

 

ごちゃついたがなんとかAC。

小さい方から数列Aに含まれない数xを見ていって、まず0からxへの辺を張る。それまでに手に入れた基底でxorを貪欲に取りながら見たことのある数に辿り着いたらbreakする。そこまでの遷移をすべて辺として持つ。ということを繰り返して、最後に持っていた辺を使ってunionfindで全域木にする。という方針だった。

ごちゃついてペナしまくった原因だったのは「それまでに手に入れた基底を使って」という部分だった。本来log(N)個の基底が手に入って、それで以って連結グラフにできるはずなのにグラフの構築と基底の作成を同時に行ったために連結になっていなかったのだ。基底パートを2回回すことで無理やりAC。

 

総括

Dくらいまでの問題はいつものABCよりやや難しかったが、良いペースで解けていた。少し数学すればいい部分を実装パンチに持っていったところは少し反省。E以降はこの世の終わりのような実装でレートを持っていかれてしまった。定数倍感覚のアップデートが必要なのがわかった。もったいないペナとかしないように気を付けたい。焦って視野が狭くなるのを感じたら一回横になって天井を見ることにしているが、今回は感覚として焦っていると感じなかったのでこれを行わなかったが、20~30分おきに天井見てゴロゴロした方がいいのかもしれない。