katsu_y practice 002

記録: hadrori

問題セット

Regionals 2009 :: Europe - Central
2014/05/28 15:25 - 20:25 (5h)
コード(pushし忘れたので今度やっときます)
練習用コンテスト

練習前

またしても計算機室が混んでいる.
クイックソートを実装する課題に苦戦している人々を観測した.

練習

20分

頭から問題を読んでいくもすぐ解けそうなのがない……
国内予選を意識して難易度(solved数)順に解くことにする.

43分 D RE

A2OJのstandingsからverdictを確認していたためREではなくWA(色しか表示されない)だと思ってコードを印刷してデバグを始める.
その間にIをやってしまうことに.
Dは実装上のミスはなさそうで悩む.

66分 I AC

AC(ponyo). 2番目に簡単な問題だったけれど状態を逆順にたどってunion-findする問題だったらしい(難しめな気がする).
このときにDがREだったことに気づく.

72分 D AC

範囲外参照はしてなさそうだったのでREの原因はスタックオーバーフローだと気づく(実際偏った入力だと明らかにやばい).
DFSしていた部分をBFSに書き直してAC(stqn).
次はCがいけそう.

114分 C AC

途中で少し詰まっているようだったけど細かい修正を繰り返してAC(stqn).
解けそうな問題がなくなる.

130分

BがいけそうということなのでBの実装に入る.
Jが残っている中で一番簡単なはずなのでJを考える.

148分 B WA

ここらへんから同じことを繰り返しているので時間の感覚が消える.
BのWAはささいなミスだったので修正してsubmit. TLE.
ほとんど線形なのにTLEとか厳しい.
BのTLEの原因はpowを毎回計算しているからと思って前計算で生成しといて提出するもTLE.

Jは完全マッチングだがsolved数的に何かあるはず......閉路か, 橋か......
Fはmod2だったら簡単にいけることが知られているらしいのでなんとかそれを利用するのではというところで止まってる.

200分

WAが続いてしまい, assertで毎回愚直に計算した結果とおなじになるかテストするとうまくいかないケースとうまくいくケースがある.
しばらくやってpowの前計算にミスがあったことに気が付き修正して提出. TLE.
どうすればいいのかもうわからないので低数倍高速化を極めることに.

220分

これcinがボトルネックなのでは……となりscanfにして提出. TLE
どうしようもない感がでてくる.

246分 B AC

コードながめる.
"assert(ans==checksum())"
愚直解との比較のassertを残したままでした. 消してsubmit. AC
おそらく始めのTLEのときにscanfにしていたら通ったと思われる. ジャッジがクソ

少し他の問題を考えるも解けそうにないのでやめて解説を眺め始め終了.

練習後

解説を読んでみてやっぱり難しかったという印象だが, あと一歩というところまで考察できているのも多かった.
当時の順位表見るとポーランド強すぎてやばい.

夕食は駅の近くにあるお好み焼きやさん(ひろBa'y)でした.

反省

Eの題意がちゃんと伝わっていなかったので進行表と合わせて必要十分な情報を伝えるようにする.
イージーミスが出るのは仕方ないところがあるのでバグりそうなものはペアプロをする.
毎回のことだけれど机の上で問題とか計算用紙とかがぐちゃぐちゃになっているので解決方法を模索する.