Maximum-Cup 2010 - simezi

オンライン参加か現地参加か迷ったんだけど、最近かなり疲れがたまっていたのでオンライン参加に。

Result

A: AC(1WA)
B: AC(10RE 4WA)
C: -
D: AC(4WA)
E: -
F: -
G: AC
H: -
I: -
J: -

10位（全体順位）

D

13時に起床して、うとうと（っていうか寝る寸前でカクカク）しながらとりあえず問題文を読んでいく。

Aはめんどそう。BはBNF記法で読む気がなくなる。Cも長いので後回し。
Dは……この前のZOJのコンテストに同じ問題あったっけ。ワーシャルフロイドでおｋそう
Eはゲームで探索っぽい。サイズもそんなに大きくないので単純に書く問題かな？
Fは苦手そうな順列組み合わせ。しかもBigIntが必要ぽい。Gは二分探索でよさそう。

Hを読み始めたとこで本当に寝落ち寸前になったので、簡単そうなDを実装することに。
書いた。サンプル合わない。エッジの張り方間違えてた。

修正して送信。WAになる。
初期化か何かミスってた。訂正。WA.
問題文を良く読むと重辺がないとは書いてない。もしかしたらあるかもしれないのでその処理を付け加えてみる。WA.
候補がない場合があるのかも？と思って、その場合空行を出力するように。WA.

これってもしかして本社から社長が移動するコストも考えるのだろうか。
サンプルはどちらでも通るようになっている。まさかと思って試しに修正して送信。
……AC.

Maximum-Cupに参加するのは初めてで、さいたまトラップという言葉を使ってる人が結構いたけど、こいつがさいたまトラップか！！！
なんという疑心暗鬼コンテストだ。

ついったーにさいたまトラップくそふいたｗｗｗというtweetをする。

A

少し目が覚めてきた。
Standsを見るとAを解いている人がかなり居たのでもう一度問題文を読み直す。

あ、休憩しても作業は途中から再開できるのか。
ならば60分の作業に毎に単純に10分を足してやればよい。
書いた。WA.

あ、これじゃちょうど60分の作業の場合に70分を答えてしまう。
訂正。AC.

G

次にみんなが解いているのがG.
単なる2分探索でよさそうだったのだがボケボケでサンプル通すのに凄く時間がかかった。
簡単に紙上シミュレートができるなら一度ちゃんとサンプルを紙に書いたほうがいいね。

送信。AC.

B

次に何をやろうか迷う。とりあえずBをもう一度読むと、単に連立一次方程式を解けといっているだけのような気がしてきた。

連立一次方程式のライブラリ持ってない……
（注：spaghetti sourceにありました。LU分解と一緒のページにあったので気づかなかった）

紙でやった掃きだし法をプログラム上でやるだけならすぐに書けるだろう。
という訳でとりかかる。
あれ？計算誤差減らすのってピボットって最大の係数選ぶんだっけ？最小の係数選ぶんだっけ？
とりあえず読み込みエラーに苦労しながらサンプルが通った。

送信RE.
0除算エラーが起こっているんだと思い、方程式を解く部分をなんか色々直して再送信を数回くりかえす。
ライブラリを用意しておかないと、方程式がバグってるのか他の部分がバグってるのか判断できないからキツイよう。

1時間以上格闘して疲れてきた。

どうしてもREが取れないので、ピボットが0の場合強制的に1にしてみた。
けどRE.
これってもしかして読み取り部がバグってる？？？

問題文とBNF記法をよく読み直すと、動物が全ての器官を1つ以上持っているとは書いてない！！
あーこれで読み取りバグってたのか！！！
さいたまトラップその２．

色々サンプルつくりながら修正→送信→REのループを繰り返す。
もう一回問題文を読み直す。

ん？？？ん？？？？？nの範囲いつの間に100未満から100以下になったんだ！！！
うおおおおおおclar来てた！！！

僕はいつも配列をぴったりしか確保しないので、そこでREってた模様。

clarにまでトラップを含めるさいたまトラップ最強すぎだろ。
ちゃんとclarを見なさいってメッセージだな。Dのオーナーとかよりも真面目に教育的だなあとか思う。

直す。
うおおおWAになった！！うれしい！！（感覚がマヒしている
うーんでも何でWAなのだろう。

ピボットをいじってみる。WA.
もしかして小数点誤差？？(int)(ans[i]+EPS)に訂正。WA.
うーん……そんなに誤差が蓄積するとは思わないけど四捨五入にしてみよう。

通った。なるほどなー。
二時間半もこの問題と格闘していたようだ。もうバッテバテ。

上位の神々はよくこんな長丁場で集中力もつよなー。

J

あまり残り時間がない。その上思考力がもう０
なんとかJを解こうとしてみる。どうもDP+経路復元っぽい。

30分以上かけてサンプルすら通らず。
紙上シミュレートも全然できず、時間切れorz

反省

と、こんな具合だった。普段とはなかなか傾向の違ったコンテストで面白かった。
（ただ、M-cupはトラップで有名と評判があったから楽しめたのであって、いきなり参加したコンテストが地雷だらけだったらブチきれてる気もするｗ）

あとJは解けてしかるべき。さてこれからも頑張ろう。