Hatena::Grouptopcoder

iwbtr - kmats このページをアンテナに追加 RSSフィード

2012-02-02

Codeforces Round #105 (Div. 2) 反省

| 05:16 | Codeforces Round #105 (Div. 2) 反省 - iwbtr - kmats を含むブックマーク はてなブックマーク - Codeforces Round #105 (Div. 2) 反省 - iwbtr - kmats Codeforces Round #105 (Div. 2) 反省 - iwbtr - kmats のブックマークコメント

Rank: 427/1320

Score: 1628

Solved: 2 (A: 980, 00:05 / C: 748, 01:28)

Rating: 1350 -> 1448 (+98)


出題者による問題点の不適当な設定を避けるために5問すべてが1000点になったRound.

148A

お姫様がd匹のドラゴンをなぎ倒していく,

姫は4つの攻撃手段を持っており,各攻撃手段では”各”第k, l, m, n番目のドラゴンを倒すことができる.

全部で何匹のドラゴンを倒すことができるか?という問題.


問題文だけ読むと(゚Д゚)ハァ?な問題だが,sampleを見れば一目瞭然.

i番目のドラゴンに対し,iがk, l, m, nのいずれかで割り切れる = そのドラゴンは倒せる,ということ.

https://github.com/k-mats/codeforces/blob/master/140/148A.cpp


148B

お姫様がドラゴンの巣から城へ逃げ帰る.城までの距離はc.

姫が逃げてからt時間後,ドラゴンは脱走に気づき追いかけ始める.

姫(速度vp)がドラゴン(速度vd)に追いつかれた場合,宝玉をその場に捨てる.

するとドラゴンは宝玉を一旦持ち帰り時間fをかけて宝玉を整頓し,その後追跡を再開する.

このとき,上手く逃げ帰るのに必要な宝玉の数はいくつか?という問題.


姫の位置をxp, ドラゴンの位置をxd, 追いつくまでにかかる時間をdtとおき,dt時間後に追いつく

-> 宝玉の数++

-> ドラゴンが帰って整頓するまでの時間分xpを進める

-> xd = 0にする・・

というのを,xp >= cになるまで続ければOK.


・・が,systestで撃沈.よくよく考えればvp > vdの場合(もちろん宝玉は0個)を忘れていたorz

https://github.com/k-mats/codeforces/blob/master/140/148B.cpp


148C

お姫様が花婿を探している.姫は複数の候補者と順番に謁見するが,その比較基準はお金.

ある候補者がそれまでの候補者よりもお金持ちなら,姫は"Oh..."と言う.

ある候補者がそれまでの候補者全員のお金の和よりもお金を持っていたら,姫は"Wow!"と言う.

1人目の候補者に対しては何も言わない.

候補者の数をn人,Oh...と言った数をa, Wow!と言った数をbとした場合,あり得る候補者の列を答えよ(候補者iは整数,すなわち所持金tiで表す),という問題.あり得る列がない場合は-1を出力.


初めにWow!と言い切らせ,次にOh...と言い切らせる作戦.

お金は1から50000までなので,候補者1人目はt1 = 1とする.

その後,bの数だけti = sum + 1を繰り返す.(sumはi-1までの和)

その後,aの数だけti = t(i-1) + 1を繰り返す.

最後に,残りの候補者はすべて1にする.

例)10 2 3

1 2 4 8 9 10 1 1 1 1


ただし,n - a = 1の場合は-1になる.なぜなら,a = n - 1の場合,2人目以降の全候補者に対しOh...と言わせないといけないのだが,1人目がどのような数であろうと,2人目に対しては何も言わない or Wow!しか言えないので.

例)t1 = 1 に対し,t2 = 1なら何も言わないし,t2 = 2ならWow!と言ってしまう.


途中で使ったbool flagの初期化を忘れてかなりタイムロス.

ずーーーーーっとpretest 1が通らず,もうだめだあああと思っていたらオチがこれだとは・・

手元の環境では上手く動いてしまったのが運の尽き.

https://github.com/k-mats/codeforces/blob/master/140/148C.cpp


148D

姫とドラゴンによるネズミを使ったゲーム.

姫が勝つ確率を求めよ,ということなので,数学の問題だなあ,と思いつつ試行錯誤していたところでタイムアップ.

ちょっとしたことに気をつければ,なんてことはない問題・・な気がする.

白ネズミwと黒ネズミb,およびそこから求められる確率をdpで保存していくと上手くいく?


148E

みてない


反省点

  • 初期化忘れに気付かずタイムロス

教訓

  • 初期化を忘れるべからず
  • 何をやってもpretest 1で通らなかったら問題文の読み間違いやコードのケアレスミスを考慮する