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

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-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では他の部屋の様子も見ると良い

2012-02-09

Topcoder SRM532 Div2 反省

| 03:58 | Topcoder SRM532 Div2 反省 - iwbtr - kmats を含むブックマーク はてなブックマーク - Topcoder SRM532 Div2 反省 - iwbtr - kmats Topcoder SRM532 Div2 反省 - iwbtr - kmats のブックマークコメント

Div. Place: 554/1361

Points: 234.58

Solved: ox-

Rating: 930 -> 914 (-16)


registerした後仮眠を取って起きたら0:59.250を理解するのに時間がかかった..

systestでは600点問題大虐殺.ただのgreedyで解くとx.xの場合に引っかかることに終盤気付くも950が気になってそっちを優先してしまったorz


532 Div2 250

Mr. Dengklekが数えそこねたアヒルの数の最小値を求める問題.

アヒルに付いた数字の最大値をmax_num, 最小値をmin_numとして,

return (max_num - min_num + 1 + 1 - ducks.size());

するだけ.


532 Div2 600

できるだけ綺麗な鎖の列を作る問題.

鎖を場合分けすると,

  1. "xyz"のように錆のない鎖
  2. "x.."や"xy.", "..z", ".yz"のように片端が錆びている鎖
  3. "x.z"のように中央が錆びている鎖
  4. ".y."のように両端が錆びている鎖

の4通りになる.1番目は何も考えず連結に使えるので,int sumに値を保持しておく.

2番目はそれぞれ左端もしくは右端にしか使えず,3番目は左端・右端両方に使える.

そこで,2番目もしくは3番目に属する鎖は別途vectorなどに保存しておき,そこから"最も値が大きくなる左端・右端の組み合わせ"を探す.

ただし,"x.z"型の鎖はそれ一つで両端に使うことはできないので,そのことに注意する必要がある.

4番目は連結不可なので,4番目に属する鎖の内最も値が大きいものと,1〜3番目を連結した鎖の値を比べる必要がある.


引っかかるポイントはおそらく2つ.

  1. 4番目の鎖の処理を最後に行うのを忘れる
  2. 3番目の鎖の処理を間違う

この内1つ目はExamplesの中にあるので,大抵の人が気付くはず.

2つ目は,初めにint left, rightという左端・右端用の変数を用意しておき,chainsを順に見てその場で大小比較することにより左端候補・右端候補を決めてしまうgreedyな方法を思いついてしまうとハマる.

この方法の場合3番目の鎖の処理で迷うが,それっぽい条件でleftもしくはrightと比較する処理を書くとExamplesは通ってしまう.自分がこれだったorz


例)"..3", "2..", "5.4", "6..", "111"

正解は"5.41116..."で13になる.

しかし,greedyな方法の場合,"5.4"を見たときにこの鎖を右端候補としてしまう可能性がある.

(まだ"6.."を見ていないので,左端候補で間違いないといえるような処理は書けないはず.)

よって,"..31115.4"で12・・というような誤答を返す可能性がある.


コードを書いている途中も"greedyだと無理じゃないかなあ"と思いつつもExamplesが通ってしまったので"まあいいや"と思ってしまった・・

950を解いている途中で無理だということに気付くも時すでに遅し・・Easyはともかく,Mediumは回答の妥当性をちゃんと確かめないと駄目だと痛感..


532 Div2 950

愚直に全探索するとオーダーが大きすぎてしまう問題.

dpでなんとかするのかな.

なんかdpが必要そうな問題は毎回ほとんど手を付けずに終わってる気がする・・


反省点

  • 起きたら開始直前だった
  • 回答の妥当性を確かめずに提出してしまった

教訓

  • 仮眠しなくてもいいように前日・当日の睡眠を調整する
  • 回答の妥当性をちゃんと確かめる,もしくは気になったケースは手でちゃんと確かめてからsubmitする