JAPLJ Contest - aizuzia

寝起きでコンテストに出るのは良くないと思いました。

・・・え？Aのにいきなり難しそう？
- とりあえず全問目を通してみる。
  - 簡単そうな問題がない。泣きたい。
  - Standingsを見る限りだとAが一番簡単なのか・・・。
とりあえず、g_n(t) の形について思いを馳せてみよう。
...
...
...おお。
- だんだんギザギザが増えてく関数なのね。
で、問題文を整理すると、
- 適当な k をとって、y = g_n(t) と y = k の交点がちょうど p 個とすることが出来るような最小の n
を答えればいいわけだ。
考えるべきパターンは k = 0, k in (0, 1), k = 1 の3通りで、交点がそれぞれ 2^n-1+1, 2ⁿ, 2^n-1個。
- 下からループまわすんだから、2^n-1は無視して2パターンだけ考えれば良いよね。
書いた。submit.
No - 30% scored.
- あれれ？
  - よくわからないので次に行こう。

自分より強いと分かる人が高々 k-1 人しかいなければ良い。
正規表現っぽく言うと「自分{に勝った人}+」は自分より強いし、それ以外の人には勝てると言い張れる。
- 自分に勝った人がどこまで勝ち進んだかを見ればよいのでは。
  - 今冷静に考えるとどう見ても違いますね。
O(n²) で適当に実装してみる。
No - 10% scored.
あ、入力結構大きい？
- 1,000ぐらいだと思ってた。ひどい。(自分の頭が)
とりあえず A に戻ろう。

ケースごとのジャッジ結果が見られることに気付いた。
- 最初のケースだけ落ちてる。コーナーケースか・・・。
よく見たら p = 0 がありえるらしい。
- 自分のプログラムに入れてみると -1 が返ってくるけど...
- 問題文のとおりに解釈するなら、n = 0 で k < 0 または k > 1 が正しい？
  - とりあえず対応してみた。
他にコーナーケースはないだろうか。
- p = 1 を入れてみる。-1. あれ？
  - あぁ、2^n-1はいらないようでいて、n = 1 のときだけ必要になるのか。修正。
submit. Accepted.
- どっちのケースで落ちてたんだろう？

Bをまじめに書くのがしんどいのでCに逃げてみる。
DPの臭い・・・。
...じゃない？
隣り合った赤白は問答無用で消せる。
- 新しく隣り合った赤白が出来ればそれも消せる。
  - ひたすら消していけばいい気がしてきた。
    - 書くか。
      - いや、適当に書くと O(n) にならないぞ・・・？
あ、stackに積みまくればよさそう。
遅い遅いと評判だけど意外とどうにかなると信じてcinとvectorで特攻。書けた。
- こういう難しそうだけどきれいに実装できる問題って良いよね。
submit. 30%ぐらい scored.
- あからさまに最大ケースでTLEの予感。
cinをscanfに、vectorとstackを配列に書き直してsubmit.
- Runtime Error.
n = 100,000 だと思ってたけど 500,000 だったのね。配列の長さ直してsubmit.
- Time Limit Exeeded.
あー、coutをprintfに直してなかった・・・。
Accepted.
ひどすぎる。
- それどころか辞書順最小とか答えがなかったら -1 とかの条件を全部読み飛ばしていたことに翌日になって気付いた。