2012-02-20

Codeforces Round #108 (Div. 2) 反省

Codeforces | 02:48 |

Rank: 696/1260

Score: 1288

Solved: oox--

Rating: 1501 -> 1451 (-50)

Cのaccept率826/1260なのにTLEで通せなかったorz

152A

vector<string>に成績を格納し，各科目における最高点を記憶．

別途0で初期化したint a[n]を用意しておき，その最高点と等しい人iはa[i] = 1とする．

最後に，1となった人（＝1度でも最高点を取ったことある人）の数を数えればOK．

https://github.com/k-mats/codeforces/blob/master/150/152A.cpp

152B

各ベクトルi < kに対し，一回適用するごとにステップ数stepをインクリメントを繰り返す．

それ以上適用できない（フィールドを超える）場合は次のベクトルi+1に移り，同じように一回適用してはインクリメントを繰り返す．

最後にstepを出力・・するとTLEになる．

ので，まずはベクトルiを最大何回適用できるかを数え，その数aの分(dxi * a, dyi * a)だけ一気に移動＆step += aする．

aの算出は，ベクトルの向きに気を付けつつ，x方向とy方向それぞれ移動できる回数を求め，小さい方をaとすればよい．

https://github.com/k-mats/codeforces/blob/master/150/152B.cpp

152C

TLE@pretest 7の文章を見ること約20回orz

前回"TLEになるようなら大元の処理を見直せ”と反省したものの，何が違うのかさっぱり．

dpしても探索範囲を狭めても処理を軽くしてもTLE．

で，他の人のコードを見て納得・・

生成されうる文字列の数 == m文字の各位置で取りうる文字を取った時に生成される文字列の数

なので，各文字列のj<m番目の文字の種類の数を数え，順位掛け算すればよい．</ppp>

正答率が高いのは，この手の問題は頻出もしくは典型的なものなんだろうと予想．

純粋に練習量が足らない・・

https://github.com/k-mats/codeforces/blob/master/150/152C.cpp

152D

みてない

152E