Hatena::Grouptopcoder

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

2012-03-21

TopCoder SRM538 Div2 反省

| 19:38 | TopCoder SRM538 Div2 反省 - iwbtr - kmats を含むブックマーク はてなブックマーク - TopCoder SRM538 Div2 反省 - iwbtr - kmats TopCoder SRM538 Div2 反省 - iwbtr - kmats のブックマークコメント

Div. Place: 205/951

Points: 308.46

Solved: xo-

Challenge: +1 / -2

Rating: 1050 -> 1080 (+30)


個人的にも全体的にも割と荒れ試合だった模様.


538 Div2 300

問題文を読みながら"DFSでいいじゃん"と思ってしまったorz

?*50の場合計算量は2^50・・・DFS, BFSに対する計算量の見積もり癖が無かったのが敗因.

300なめすぎ.テストしなさすぎ.

?が全部Lの場合と全部Rの場合の2通りだけ試せばよかったですね.


538 Div2 500

一方こちらはマトモにやるとTLEになることにしばらく格闘してから気付く.

与えられたパリティビットと同じ偶奇のステップ数になるか,という”偶奇”の一点だけが問題なので,何か簡単な方法があるのだろうとサンプルケースを眺めてみれば,最後に訪れる点(x, y)が(x+y) % 2 == 1であればステップ数は奇数,== 0であれば偶数になることを発見.


(x+y) % 2 == 1になるような点を含んでいれば,1:CAN, 0:CAN

そのような点しかなければ,1:CAN, 0:CANNOT

そのような点が一つもなければ,1:CANNOT, 0:CAN

となる.


next_permutationを使って全探索するとTLEなので,これで1回撃墜.


538 Div2 1050

おおよそどのように組めばいいかは分かるも,そこそこ時間をかけて2問解いた後に解くには割と重かった.


反省点

  • 300をなめた
  • テストをサボった
  • DFSに対する計算量の見積りがあまかった

教訓

  • 普段より高い配点の場合は特にテストに気をつける
  • DFSを使うときは計算量に特に気をつける

2012-03-18

TopCoder SRM537 Div2 反省

| 04:11 | TopCoder SRM537 Div2 反省 - iwbtr - kmats を含むブックマーク はてなブックマーク - TopCoder SRM537 Div2 反省 - iwbtr - kmats TopCoder SRM537 Div2 反省 - iwbtr - kmats のブックマークコメント

Div. Place: 61/1365

Points: 652.84

Solved: oo-

Challenge: 1 succeeded

Rating: 916 -> 1050 (+134)

1回お休みした後の参加で多少不安ながらも良い感じに事が進んだ回.


537 Div2 250

与えられた条件にちゃんと沿うだけ.

が,ケアレスミスで落とされた人が割りといた印象.パス率70%ほどだった模様.


537 Div2 550

「(X, Y)の組み合わせで(A, B)の通貨制度に対応しろ」というのは,すなわち「XとYを用いてAとBを作れるようにしろ」ということ.XとYだけでAもBも作れれば,A*p + B*qも作れる=(X, Y)で(A, B)の通貨制度に対応していることになる.


XとYでAとBを作るにあたって,特殊な状況が2つある.

  1. 与えられたXだけでAとBを作れる(X==1を含む)
  2. Y==1であればYだけでAとBを作れる

1番の例)A=4, B=8であれば,A*p + B*q = 4(a*p+b*q)となり,(A, B)の通貨制度の元で付けられる値段は全て4の倍数になる.このとき,Xが1, 2, 4のいずれかであれば,Yがどのような値を取ろうとXのみで値段を表すことができる.この場合,-1を返さなくてはいけない.

よって,はじめにif (A % X == 0 && B % X == 0) return -1とする必要がある.


1番目のチェックを行った後は,Yを1<=Y<=max(A, B)の範囲で全探索する.上限はmax(A, B)としなくても,A, B, X <= 200であることから,Y <= 200としても計算量的に問題ない.

後は,0<= i, j <= 200程度の範囲でX*i + Y*j == A, X*i + Y*j == Bが成立すれば,その(X, Y)は代替貨幣制度として成り立つので,答えを+1する.

このとき,Y==1は必ず成り立つので,初めから答えを1にしておき,2 <= Y <= max(A, B)としても問題ない.


537 Div2 925

next_permutationを使って全探索すればいいじゃん,サンプルも通ったし・・といってそのまま出すとサイズ50の入力を突っ込まれてchallengeの餌食になる.next_permutation,すなわち順列がサイズnの配列(ベクトル)から生成する配列の数はn!個.50! = 3*10^64では当然TLEになってしまう.

他人のコードを見ただけだが,恐らく以下のようなことではないのかと・・


prerequisitesの要素は重複しないので,与えられたprerequisitesに対し,prerequisitesが-1のものを抜いたToastbookは,食べなくてはいけない順番が決まっていることになる.

視覚的な例としては,-1のToastbookをバラバラになった鎖一つ一つ,特定のprerequisitesが必要なToastbookをつながった鎖とすると,適当な長さの鎖列がいくつかと,その他バラバラの鎖,という状態ができあがる.

ooooooo ooo oooo oooooo oooo oo o o o o o o o o...

この鎖列は前から順番に辿らないと残りが無駄になってしまうのである.つまり,鎖にランダムにアクセスしたときに得られる鎖列の長さと,その確率を掛けた”得られる長さの期待値”が,鎖列一つ一つの部分解となる.

例えばlength=2の場合,ランダムに鎖にアクセスしたときに先に頭にアクセスし,次に尾にアクセスする確率は1/2である.

このとき,部分解は1*1/2 + 2*1/2 = 1.5となる.

length=3の場合,ランダムに鎖にアクセスし得るパターンは3!通りである.この内,3つ全てを得られるのは1/6,1しか得られないのは5/6となる.よって,部分解は3*1/6 + 1*5/6 = 4/3である.

length=1で列をなさない場合の部分解はもちろん1である.

すべての鎖・鎖列の部分解を求めたら,後はそれらの和を求めればreturnすべき解となる.

なお,鎖列の長さが同じ場合は,Toastbook一つ一つにどのような番号が振ってあっても同じ部分解となる.よって,部分解の導出ではメモ化が有効である.


反省点

  • 愚直にコードを組んで終わった(next_permutation)
  • challengeであまりコードを読まなかった

教訓

  • 問題の読み替えをすべし
  • 広くコードをチェックしてケアレスミスを見逃すべからず

2012-02-24

Codeforces Round #109 (Div. 2) 反省

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

Rank: 981/1284

Score: 492

Solved: ox-x-

Rating: 1451 -> 1383 (-68)


フルボッコキタ――(゚∀゚)――!!

の割には,あまり下がってない様子.

いずれにせよ,今回のDは勉強になりました.


155A

最大値・最小値が更新されたらcount++するだけ.

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


155B

a[n]とb[n]を用意しておき,b[i] > b[i+1]になるようにaとbをソート.b[i] == b[i+1]の場合は,a[i] > a[i+1]になるようにソート.

その後,i == 0から順にcount_b == 0になるまでcount_a += a[i], count_b += b[i]すればいいだけ.


が.実際に書いたソートが間違っていたカウントする際の処理を間違えていた/(^o^)\

SRM533 Div2 250のピカチュウの時もそうだったけれど,解法が思いついた状態でさっさと書いたコードの中にケアレスミスがあっても見つけようがないなあ・・

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


C (154A)

前から順に貪欲法で解いて死亡.

abbaaaのときはbを全て潰し,abbaaabbbbのようなときはaを全て潰す必要があることに気付いたのはCを飛ばしてDをsubmitしてから..


D (154B)

何も考えずon/offの状態を配列で保持し,二重ループするとO(10^10)になって死亡する.

ので,on状態のcolliderのみset<long> colsに保持し,offのリクエスト時にはcols.findしてoffを判断.

onのリクエスト時にも同様にcols.findし,無ければリクエストされた番号とcolsの中の番号をしらみつぶしにユークリッドの互除法.


で死亡.そりゃあいくらfindで計算量減らしても,ループの中で全探索やってりゃ結局O(10^10)になるわな・・


診断人さんの放送(http://com.nicovideo.jp/community/co78570)を見ていたら,”整数のペアを共に素因数分解し,同じ素数を持っていたら互いに素ではない”ということを利用すれば良いと知る.なるほど.


k番のリクエストが来たらk番と一緒にkの素因数もon状態と考えておけばユークリッドの互除法は必要なくなる.

更に,使用中の素因数を覚えておけば,k番を削除するときにも役立つ,と.


ついでに,整数が非常に多く出てきても,出てくる素因数はそんなに多くない,というのも有用な情報だと思った.


E (154C)

読んだだけで解いていないが,u, vを使ってる時点でグラフ問題だなあ,という感想.

ノードが2つのみの木を構成するペアおよびその他のノード全てとつながっているノードのペアを探せ,ということですね.


反省点

  • ”互いに素”に対してユークリッドの互除法しか対処法を知らなかった

教訓

  • "互いに素" = "共通する素因数を持たない"と言えるので,素因数分解が有効

TopCoder SRM534 Div2 反省

| 23:39 | TopCoder SRM534 Div2 反省 - iwbtr - kmats を含むブックマーク はてなブックマーク - TopCoder SRM534 Div2 反省 - iwbtr - kmats TopCoder SRM534 Div2 反省 - iwbtr - kmats のブックマークコメント

Div. Place: 282/943

Points: 353.65

Solved:oo-

Challenge: 1 failed

Rating: 940 -> 964 (+24)


250で許されざる時間ロス&チャレンジ失敗.何とか500を通したものの,その500も糞コードすぎて解いた気がしない・・

20分後のCodeforcesも頑張ります.


534 Div2 250

ただイテレータスワップするだけ.するだけだったのだが・・


後ろ2つが"."か".."であることを確認するために

vector<string>::iterator it = files.end();
advance(it, -1);

等とするところを,

it = advance(it, -1);

としてたorzorzorz


一発で解けなかった時点で半分パニック状態に陥り,大幅に時間ロスしてしまった・・

イテレータの基本的な使い方を復習しないと・・


どう見ても撃墜できるだろう,という回答が一つあったのに弾かれた.

Codeforcesが終わってから要確認.


534 Div2 500

"o"マーク(checker)を左から右に移動させていき,移動できなくなった方が負けるゲーム.

対戦形式のゲームなのでミニマックス法的な考え方が必要なのかと思いきや,今回は特に各プレイヤーの最適解を考える必要はなく,操作する人が一人だけと考えてしまって良い.

  1. 最も左のチェッカーを操作対象として選ぶ
  2. 右端に到達するか,他のチェッカーが邪魔で移動できなくなるまで移動させる
  3. まだチェッカーが残っていれば1に戻る
  4. 全てのチェッカーを移動し終わったら,操作回数の偶奇で勝利プレイヤーを判定する.

またもや実装しながら考えていたため,二度と見たくないような糞コード爆誕.

なぜか2度もチャレンジされてた.


534 Div2 1000

ちらっと問題文を読むも,解いた人がほとんどいなかったため投げた.

結果的に0%..


反省点

  • イテレータの扱い方を忘れていた
  • 考えながら実装した

教訓

  • 基礎的な文法やアルゴリズムを復習すべし
  • せめて大まかな方針を固めてから実装し始める

2012-02-20

Codeforces Round #108 (Div. 2) 反省

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

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

みてない


反省点

  • よく考えずに愚直にコードを組んだ
  • 練習量が足らない

教訓

  • Cで愚直な方法は弾かれやすい.アプローチをよく考えるべし
  • 精進すべし

2012-02-18

TopCoder SRM533 Div2 反省

| 04:39 | TopCoder SRM533 Div2 反省 - iwbtr - kmats を含むブックマーク はてなブックマーク - TopCoder SRM533 Div2 反省 - iwbtr - kmats TopCoder SRM533 Div2 反省 - iwbtr - kmats のブックマークコメント

Div. Place: 428/1535

Points: 424.1

Solved: xo-

Challenge: 3 succeeded

Rating: 915 -> 940 (+25)


ピカチュウで笑いピカチュウで泣くorz

問題文で笑ったりMidの方針間違えてタイムロスしたり3つも撃墜できたりピカチュウ落としたり色々なことがあった・・

撃墜成功は初めてだったから心臓バックバクやったぞ!


533 Div2 250

お!ピカチュウー!


ただ文字列を前から調べていくだけ,いくだけだったのに・・

インデックスのインクリメント後にword.size()を超えていないか調べるタイミングを間違えていた・・

Easyといえど油断してはならない・・


一方で,"pi", "ka", "chu"の部分文字列があったらそれを空文字列と置き換える人が割といたので,撃墜させていただいた.

例)この手法では"pkai"はYESになってしまう

他の部屋を覗いてみるとEasyが撃墜されていたので,何事かと思いコードを読んだところ,これを発見.

Challenge中に他の部屋の様子を見る,というのは割と良い作戦だなあと思った.


533 Div2 500

お!東方ゥー!


Div1 Easyとほとんど同じ問題だったらしいが,向こうは最大50 elements.こっちは10 elements.

よって全探索しても8!=40320通りにしかならないので,普通に再帰で深さ優先探索した.


が,その前に”greedyでいけるんじゃね?”と思いしばらく格闘.

ある程度組んだところで,生半可なgreedyでは死ぬケースを思いつき急遽全探索に切り替え.

systestで死んだ人はgreedyで提出したのだろう・・

一方,div1の方は全探索できないのでdpか何かで解く・・はず.


533 Div2 1000

お!魔法少女ゥー!


時期的にまどマギかしらん?と思いながら解くも500で大分時間を食ったためにtime up.

各魔女の情報は日付順にソートしてから処理する必要があるはず・・


反省点

  • Easyを舐めた

教訓

  • Easyといえど侮る無かれ
  • Challengeでは他の部屋の様子も見ると良い