Maximum-Cup 2010
埼玉大学による
http://www.aise.ics.saitama-u.ac.jp/~t_koh/
に参加したのでその戦記．
13:00 開始
今日は6時半という早い時間に起きてしまったので昼間がどうも眠かった．まぁ眠いのはいつも通りなので問題ないのだけど．
早速Aを開く．さいたまトラップ? なにそれ… よく分からないけどmap
適当に書いて投げる．WA．あれ．ああ，時間が1時間ちょうどになっているときは休憩いらないね… 直してAC．
Aにしては若干難しかったような気もします．
13:07 A Accepted (1WA)
Bを見る．鶴亀算，やるだけ? かと思いきや変数がいっぱい… ギョエー．Bでこれってちょっと，このコンテスト実は結構難しいのだろうか…? Cもついでに見る．うーん，なんかよくわからない… とりあえず連立方程式はライブラリが一応あるのでBを進める．
実装が若干重い，めんどい．がとりあえずAC．
あとで知ったのだけど，問題文そのまんまの記述だと行列式=0のときでも解が存在するようなケースがあってまずいことになるらしい．(けど問題の入力は親切なので助かる．)
あと，First Acceptedだったようです．
13:33 B Accepted
Standsを見るとGが人気のようなのでGを見る．2分探索とかでええんでは．ちょっと悩みながらも書き上げるて投げる．RE．え．
よく見ると愚直にlong longで掛け算しまくると余裕でオーバーフローすることがある…．適当に直してAC．
13:59 G Accepted (1WA)
Standsを見るとDが人気のようである．読む．え，なにこれすごい簡単なのでは… 適当に書いて投げる．WA．なんだと…?
とりあえずもう1回問題文をよく読む．本店とか書いてあるけどこれなんだろう．オーナーが100年? なんじゃそりゃ… 意味が良く分からないけどとりあえず100足して送る．AC．
なんというかトラップすぎないですかこれ．
14:14 D Accepted (1WA)
解けそうなやつがあんまりなくなってきた!! Eとか読む．去年のJAGのQueen's Caseっぽいなぁと思ったけど面倒そうに見える．とりあえずH,Wの値域が書かれていないのでクラを投げる．両方とも10以下らしい．状態数的には探索するのに妥当だけどなんか怖いので放置することにした．
Standsを見ると2人ほどJを解いている．見る．なんか難しいのかと思ったけど普通に編集距離っぽい感じでやると良いのでは．書く．
添え字とかバグりまくって時間がとてもかかってしまう．ただの編集距離なのに… ログ取りはTLEになるだろうなぁとは思いつつもめんどかったのでstringに格納するようにした．ここも地味にめんどうくさい．手順を記すのはけっこう頭がこんがらがったけど，適当にやったらそれっぽくなったのでもういいやと思って投げる．WA．
適当にテストを作ってテストする．すると明らかに違う答えが返ってきている…．vectorの初期化し忘れがあった．直す．TLE．はい．
stringじゃまずかったので適当にlong longとかに格納するようにする．その反動で境界外参照も発生するようになったので直す．AC．
結構手間取ってしまった．
15:31 J Accepted (2WA)
解けそうなのが本当に無くなってきた… Iがあまり解かれていないけど結構簡単なんじゃないかと思う．(実装するだけだし)
これって崩れるのを判定するだけなのか，変な置き方(もうすでにあるところに置くとか，空中に置くとか，変な向きに置くとか)も考慮しないといけないといけないのか，どっちなんだろう．実装しつつもクラを投げる．
実装，実装，面倒くさい…問題文をよく読まないといけない系の問題で心がちょっと蝕まれる．
クラが返ってこない．とりあえず一通り書けたので，変な入力にassertした状態で送る．RE．うわ，ちょっと嫌な予感が…．
30分くらいしてクラが返ってくる．問題文をよく読んでください．え，あ，そうですか… さらに実装を増やす．問題文でいくつか分からないところもあるのだけど一部妄想で補完する．
提出する前にトラップが無いかよく見る．あれ，一番上の段の一つ下のブロック以外はどこを抜いてもいいってことは，一番上のブロックは抜いてもいいのか?
…分からん．再びクラを投げる．待つのも面倒なのでとりあえず投げてみる．AC．あれ，意外とあっさり．
16:35 I Accepted (1WA)
疲れたのでふとtwitterを見ると，コンテストも残り1時間だなというツイートが目に入る．え，そうなの? たしかにコンテストページには17:30までと書かれている．うっかり5時間のコンテストだと勘違いしていたのでちょっと心に余裕がなくなる．
あとはどれを解けばいいのだろう… Standsを見た限りだとトレンドはEなのだけど自分の目にはどうもそんなに簡単には見えない．時間を掛ければ出来るだろうけどあと1時間で実装しきれるか正直怪しい．
LayCurseさんとりんごさんしか解いてないFを見る．なになに，2つの長方形の配置の場合の数を求める? 多倍長必須らしいけどそれを除けばそこまで難しそうには見えない．うーん，しかしどうやるんだろう．
考える．重なっていないものそのものをカウントするよりも，全体から重なってるものを取り除く方が楽そうに見える．
ただ，辺を共有している場合が厄介っぽくてどうすればいいのかよく分からない．うーむ．
とりあえずC++の多倍長ライブラリをコピペしてコードを書ける状態にしておく．
考える．なんかそれっぽい式が浮かぶ．組み合わせ係数でごにょごにょすればよいのでは? 書く．合わない．2つの長方形に区別が無い(番号とかを振らない)のが厄介のようだ．
考える．完全一致する場合が鬱陶しい．2つの長方形に1,2の番号を振ったとき，完全一致する場合は2つの長方形を交換しても同じ扱いになってしまい，それ以外の場合は交換すると別の状態になる．
そもそも重ならない場合は完全一致のケースとかありえないんだから，長方形に1,2の番号を振ったものを考えて，重なるものによって除外して，最後に2で割ればいいんでは．書く．サンプル合う．投げてAC．
分からないと地獄だけど分かってしまうと意外とあっさり…．
17:24 F Accepted
残り6分なので何もせず晩飯のことを考えていたら終了した．
17:30 終了
というわけで7AC 6WAでした．なかなかトラップのある問題が多かったですが楽しめました．
あいにく順位が付かないらしいですがたぶん周囲の状況を見る限りだと4位くらいなんじゃないかと． 追記：3位だったようです．
