SRM479(Div 2) の結果

参加してきたのでこれに関する記事でも書こうかなぁと.もともとこれが目的でブログ立ち上げたんだし.

Coding

250点問題

そう燃料と,フライトに必要な燃料が与えられて,何回フライトできますか?っていう問題.


配列が与えられるから,始めから順にたどっていって,総和が与えられた整数より小さい間をカウントすればいいだけ.


英文を読むのに時間がかかっただけ.(辞書使わずに1回,辞書使って1回)

500点問題

Ratingが下がったのが大体こいつのせい.

フライトアテンダント(って言わないと怒られる気がした)がお茶とコーヒーを給仕する問題.


一瞬DPかなとか思ったりもしたけど,気のせいだった.貪欲っていう言葉を使っていいのかもわからない.

  1. 初めに給仕するのと,珈琲と茶を補給するのに使用する時間を計算.
  2. 1000近い配列を用意して各席の珈琲と茶の区別をつける.
  3. 配列を後ろからたどる.
  4. 動いた数を数えて7回給仕したら,機械に戻る.(ただし,この操作は珈琲と茶で分ける.)これを繰り返す.
  5. 最後に機械のそばに戻る.


で終了.

なぜかこいつで時間を大量に食った.理由は下で詳しく書く.

1000点問題

問題文を読んでない.(開いてはみた)


今度やる.(やらないフラグ)

Challenge

特に何もしなかった.


ただし,500点問題で1つほど配列境界外アクセスで死ぬだろうなと思うものがあった.


SystemTest

Challengeの時に落ちるだろうと思っていたのが落ちてた.


やっておけばよかったなと後悔...


ちなみに2問とも通過

結果

問題 250 500 1000
点数 239.49 189.88 0 429.37

Rating: 1143 -> 1133


ぴったり10落ちるっていうね!!

500点問題の感想...

俺,焦り過ぎ...

テストケースに引っ掛かりまくってましたともハイ.


テストケースを全部通過するまでは絶対に提出すまいとは思っていたのでいつまでも出さなかった.

時間がかかった理由
  1. 実装ゲー苦手.
  2. 席の後ろ側からたどるはずなのに前の方からたどっていた.


1つ目はしょうがない...なんてことも言ってられない.


実際読みなおしてみても実装に時間がかかるようなものでもなかった.


途中で思い直して実装方法を変更したのが痛い.




2つ目は...自分がアホでした.


3番目のテストケースがないと,Challengeとか,SystemTestで落ちていた.


なぜかこのケースだけが通らなかったので,頭を抱えていた.


終了10分前に,1つまずいなぁと思うところを見つけた.



実装を変えた.


通った.


泣いた.




どういうところがまずかったかというと,先頭から順番に給仕を行うと移動距離が最小になると思っていたのがまずかった.


例えば次のケース.


乗客が8人で,全員茶を希望.

Before

  1. 1-7に給仕
  2. 機械に戻る.
  3. 8に給仕
  4. 機械に戻る.

After

  1. 8-2に給仕(どちらから給仕しても移動距離は同じ.)
  2. 機械に戻る.
  3. 1に給仕
  4. 機械に戻る.


明らかに,2番目の実装のほうが移動数が少ない...


きっとこれがなかったら,Ratingは上がっていたはず...


少年号泣中...

反省


もっと よく かんがえましょう

次回

SRM480 出られない.SuperConともろかぶり.泣きたい.


それなので,次はSRM481です.それまで緑かぁ....



次は名実ともに青になれるといいなぁ...(2回目)



(このタイミングで朝刊がきました.)


あ〜あ...もっと早く500点問題解いて,Challengeしておけばなぁ.....

(負け惜しみ乙)