Codeforces Round#11 - simezi

久しぶりのCodeforces.リベンジのチャンスだった訳だが……
おい間違って自分の日記にスターつけちまったよｗどう取り消すすんだこれｗ

Result

+1 00:07/-6/-/-/-
296位 1469->1414

A. Increasing Sequence

問題

項数nの数列があたえられたとき、各項に自然数dを何度か足して数列が（狭義）増加列になるようにしたい。
dを足す最小回数を求めよ。

試行錯誤

む、今回は問題文が明快だ……
1分ほど思考。初項から単調増加になるようにどんどんdを足してけばいいな。
n<2000のd<10^6なら単純に足して時間大丈夫じゃね。

書く。送信→TLE

え？……数列の項が全部0でn=2000のケースでTLEになったのか？
たった400万でTLEになんの？信じらんねー
（良く考えたら最悪ケース400万じゃなかった。その数千倍。）

割り算でO(n)の解法に訂正→AC.(7分)

B. Jumping Jack

Aで早速WAとか勿体ない。。。

問題

数直線上の原点から、座標xの点に次のようにジャンプして移動したい。

n回目のジャンプはちょうど幅n
向きは左右のどちらに飛んでも良い

x(|x|<10^9)が与えられたとき、最小のジャンプ回数を求めよ。

試行錯誤

10^9ってことは探索ではないな。えーとこれGreedyでいけるんじゃね。
xを超えるまでジャンプすると1+2+3+...+k=nで、+iの項のプラスをマイナスにすると和はn-2iになる。
ってことは偶奇が一致するxより大きい数まで飛べばかならず項の符号入れ替えでxになるように和を作ることができる。楽勝。

書く。送信→WA(on case 4)

あれ。どこ間違ったんだろう。xを超えるkを求める部分かなー。
式を見直す。いや合ってる。なんかオーバーフローでもしてるの？？？

送信→WA(on case 4)→細かいとこ変えて送信→WA(on case 4)→細かいとこ変えて送信→WA(on case 4)

えー。。。なんでだ全然原因わからない。
問題取り違えてる？10回くらい読み直す。取り違えてねーよなー。

和のとこ全部足してく方式にしよう。最悪でもTLEになるはず。

送信→WA(on case 4)

意味わからん。全く原因の検討がつかない。
探索で答え書いて比較するかなあ。

探索書いた。あれ全然答え違うｗあ、探索は同じマスに2回入れること反映してないｗ
折り返しがある場合同じマスに二度入る場合もある。

結局原因わからないのでコンテスト投げた。終了。才能ないね。人生も終了しろよクズが。