Codeforces Round#6(Div2 only) - simezi

緑なので参加。
今回も5問セット。そろそろ問題数が収束しつつあるのだろうか。
前回のDiv2 onlyのRoundは問題が易しめだったので、始まる前に今度は沢山解いてやろうと漠然と思っていた。

4本の棒が与えられる。そのうち3本を使って三角形を作ることができるか。

あれーなんだか今回問題文難しいなあ。non-degenerateな三角形って何なんだろう……縮退してない？鈍角三角形？違うな、どうもサンプルをみるに三角形が一直線になってしまうことらしい。

理解後コードを書く。Submit→AC.
おｋおｋ.

また問題文が理解できないorz単語を調べる。
assemblyは会議、deputyは副官らしい。have a common side of a positive lengthって何ぞ。正の長さの辺を共有する？正って何だろ。
良く解らない。サンプル見る。

要するに大統領の机に接している他の色の机の数を数えろという問題らしい。

そうだと仮定して解こう。がりがりしてサンプル通ってSubmit→WA.
あれ？見直す。あー幅のループの変数を高さにtypoしてる勿体無い。

修正→AC.

n個のチョコをAとBが両端から順に食べていく。
i個目のチョコを食べるのにかかる時間が与えられるとき、AとBの食べられるチョコの数を求めよ。AとBが同時に同じチョコに達した場合Bは紳士なのでAにゆずるものとする。

なるほど。今のチョコを食べる時間をta,tbとして順にみてけばいいのかな。
書く。サンプルあわない。なんでだ。修正して合った
→Submit
WA.
あれ？もしかしてAとB同時に食べるときBが食べてる？
Submit→WA.

いかん、落ち着こう。とりあえずケースを作ろう。
3個で1 1 1の場合、2個で1 1の場合を作る。
Submit→WA.
あれー？どこが悪いのかわからないぞ。添え字をa=-1からb=nからにしてみるSubmit→WA→（中略）→AC.

ふう尺取メソッドで6WAだぜorz

正解者が今のとこ1名、やたら少ない。問題文も理解不能。何でサンプルがあの結果になっているのかわからないし、飛ばす。

読む。意味がわからん。なんで今回こんなに問題文読めないんだろ。
サンプルを見て考える。

どうも数列のうち連続する部分列で、その最大値と最小値の差がk以下のもののうち長さが最大のものを書き出せという問題のようだ。そうに違いない。
あれでも問題文のどこに連続する部分とか書いてあるんだろ。。。

方針を考える。O(n^2)じゃ間に合わないし、なんか動的計画法っぽい感じだよなあ。ほんとDP苦手だorz
15分ほど思考。

あ、これ分割統治法的な考え方でいけるんじゃ！分割統治法書いたことないけど！
最初数字を全部幅1の区間と考えて、区間の最小最大を記録。
区間を2個ずつマージして幅2の区間で最小最大を記録……（略）

それで、最後に成功したマージから横に幅を伸ばしていく。
自分と区間では失敗するのでその半分の長さの区間から試していけばいいだろう。
お、これきっとO(nlogn)でいけるぞ。

書く。書いたことないのでやたら手間取る。
数列の要素が2^nじゃないんだよなあorzこういう場合どうするんだろ。
右端の区間だけ短くすればいいのかしら。
そんな感じにして、区間毎に最大最小を求める部分を書き終える。

次に解を記録する。
各区間を伸ばしていって、解を今までの最大長さに等しいのは全て記録しておいて、最大長さが更新されたら記録を破棄してけばいいかな。
がりがり。

あーもう時間ないやばい。
なんとか書けた。実行してみる。落ちる。配列をありえない位置初期化してる……
直す。実行。なんか数字でた。残り30秒……数値ちげーし。

コンテスト終了。

3問正解のとこに人数が集中してるらしくペナルティがかなり響いた。110位ちょいorz
問題Dにジャッジ不備があったらしいがレーティングは変動。
さがったお……

敗因はなんだろう。デバッグ力不足が一番酷かった？うーん。ｻｲﾉｳﾅｲｯｽﾈ。