aizuzia

Maximum Cup 2010

Contest

今日も何だか微妙な成績。

寝坊した...。1時間半遅れぐらいで参戦。

Problem A: さいたまトラップ

タイトルがものすごく怖いけど、書くだけだよね？
書いた。休憩時間の計算を間違えてデバッグしてる間に %02d で出力してないバグに気づいた。危ない。
submit. なかなか結果が帰ってこないので御飯食べながら問題を読んでみる。
- 後で見たら無事通ってた。

Problem B: 鶴亀算

厄介そう。とりあえず後回し。

Problem C: And then there were ...

何も考えずにスルー。

Problem D: 北海道のレストラン

どう見ても書くだけ。
- standing見てもみんな解いてる...のか？何でこの人が解いてないの、という人たちがちらほら。
  - トラップの予感！
とは言っても罠が見当たらないなぁ。普通にWarshall-Floydしてsubmit.
- WA. やられた。
問題見直す。なんか冗長な情報多いなぁ。「本店の番号は1」とかいらないだろ...。
- ...え？
- 「勤続100年目」「レストランの本店で」「(兼会場での司会)」
...
Accepted.

Problem F: Rectangle^2

DP臭。しかも多倍長必須？飛ばす。

Problem G: Arithmetic Geometric Sequence

数学ゲーっぽい。飛ばそう。

Problem H: Best Route

書くだけっぽいけど...。面倒くさそうだし、他に簡単なの無いかな？

Problem I: ブロックタワー

よく読んでないけど大変そう。

Problem J: ORIGINAL NECKLACE

Edit DistanceっぽいDPかな。頑張れば出来そう。

えーと、解かれてるのは...Gだと？

Problem G: Arithmetic Geometric Sequence

よく考えてみれば指数で増えてくのだから、 n*m¹⁰とかあまり出番無いよね。
n*m², n*m³, ... を列挙して、それ以外は計算で求まりそう。書こう。
...
なんか厄介だ。指が動かない。
- もっと簡単に書けないかな？
バイナリサーチとかどうだろう？
- 与えられた t が x 番目以降に現れるかどうかが分かればよい。
  - 言い換えれば、t より小さい数が x-1 個以上あるかどうか、ということかな？
    - さっきの方法より簡単そうだ。書いてみよう。
- 答えが微妙に合わない。
  - さっきの言い換えが嘘っぽい。
  - t 以下の数が x 個以上あるかどうか、が正しいよね。
答え出てきた。submit. WA.
- なんだろう。これにもトラップあるのかな。
...
あ、m <= 1 の時場合分けしてたけど、そのままcontinueせずに普通の処理に突っ込んでた...。
- WA.
なんだろう。オーバーフローはしてないはずだけど。
- とりあえずでかいケース入れてみる。
  - 合わない！
...
入力を int で取ってた。
Accepted.
トラップはいつも自分の心にあるのです。
もう時間無いし、きょうはこれで終了かな。
- ...終了時間勘違いしてた。あと1時間あるならBぐらい書けそう。

Problem B: 鶴亀算

えーと、よくよく考えると、連立方程式解くだけ？
- 入力もBNFで定義されてるけど、普通に cin で取るだけ？
  - 書こう。ガウスの消去法をコピペっとな。
連立方程式が解けなくてassertで落ちてる？なんでだろう。
...違う、assertは「真でないと困る条件式」を書くべきだったんだよね。
出てきた。submit. WA.
誤差で落ちてるのかな？doubleをlong doubleにして、intにキャストする代わりに %.0Lf で吐いてみる。
- WA.
ぐぬぬ。問題にトラップがあるのか？
- 「一意に正の整数解が定まる」のあたりが怪しい。
  - 実数解だと一意じゃないけど整数だと一意に定まるようなケースが作れるのか？
    - そんな入力の具体例が思い付かない。無いような気がする。(rngさんに指摘されるまで無いっぽいと思ってた)
    - そもそもそういうケースがあったとして、どう対処すればいいのか分からない...。
解ける問題は全部解いたというshioshiota君が遊びにきた。
どうしようもないままタイムアップ。

今年もどぎついトラップで楽しかったです。
埼玉の人、ありがとうございました。お疲れさまでした。