国内予選の季節ですね

気付いたらもうこんな時期に．日記もだいぶ放置してしまっていました．

近況はというと，UVa::Programming ChallengeフォルダのChapter1〜12を大体埋めました．最近は幾何対策でAizu Online Judgeを利用しています．あまり埋めていませんが今のところこんな感じ．
去年のアジア地区までは幾何対策がほとんどできていなくて，出題されたら尻尾巻いて逃げていた感じなので，今年はある程度着手できるといいなぁと思います．
とりあえず国内予選までに↓の2つの問題を解いておきたいです．

Tighten Up!
ICPC: Intelligent Congruent Partition of Chocolate

それぞれ2009年，2008年の国内予選の最終問題ですが，方針自体はそこまでややこしくなさそうなので，時間かけて頑張ればできそうなはず．実装が辛そうだけど．
↓の2問も気にはなっているのですがあまりに高難易度なので，こっちは夏休みに1〜2日くらいかけて1問解くとかやってみたいです．時間と気力があれば

Twirl Around
Secrets in Shadows

追記(6/16)

↑の2問を解いた．
Tighten Up! の方はひもが絡まっている点の情報を構造体にしてまとめて，点をはずしていく過程をひたすらシミュレートした．
点をはずすと 1.絡まっていた点が外れる 2.新たなピンと絡まる 3.そのまま素直に外れてくれる のいずれかがおこるので，これらを丁寧に場合分けしてやる．
初期点の扱いがちょっと特殊っぽくて面倒くさそうなんだけど，これは無限に巻きついている点と見なせば上手い感じにできる．

Intelligent Congru(ry の方は，チョコレートを重ね合わせる写像が「鏡像orNot(2通り)×回転(4通り)×平行移動(20*20通り)」程度しかないので，全部調べる．
各チョコレートの成分を写像で移したときにどこに移るかによって，出次数1のグラフができるので，そのグラフで条件に合うように2彩色できるかどうかを調べてやればよい．(かなり適当な説明)

ちなみに，他の人のAcceptedなコードサイズを見てみたら自分のと比べて結構小さかったようだ．どうも重装備をしてしまっていたらしい．
コードが長くなるとその分バグも入りやすくなってデバッグに時間がかかってしまうので，もっと軽い装備で実装できればいいなぁとは思うものの，実際にそうするのはなかなか難しい．