Codeforces Beta Round #8
せっかくはてなのIDを取得したので、コンテストの参加記録でもつけてみる事に。
今日は研究室の先輩からおススメされ、Codeforcesに参加してみました。
- -
問題：3つの文字列s, a, bに対し，sとsRがそれぞれa, bをこの順で含むか判定する
- やるだけなのに2WAという体たらく。
- 1WA ⇒ sをreverseした時に何故かaとbもreverseしてた。
- 2WA ⇒ if(pa!=-1) s.find(b, pa+a.size()) を s.find(b, pa+1) とか書いてた。
- どうしてこうなった…。
問題：与えられた2点間の経路が最短経路であるような障害物の置き方が存在するか判定する
- 経路長が高々100なので，201×201の配列を使ってトレース余裕。
- 移動先に隣接するマスに，2ステップ以上前に訪問してたらアウト。
- 最初に書いてたコードが RL みたいな経路に対して"OK"とか出力してて1WA。
問題：n(≦24)個の荷物を鞄に拾い集める最短経路を求める
- スタート地点は鞄の位置で，1個か2個拾うごとに鞄に戻しに行かなければならない。
- 回収済みの荷物集合をビットで表してDPすれば良さそう。
- 上限24でO(n^2 2^n)はどうなんだろう…と思ってたら普通にTLEした。
- 未回収の荷物のうち最小のindexのものは必ず回収する…とするとO(n 2^n)に。
- 来た！と思って提出したら、なぜか問題Dに提出しててWA(問題Dで)。
- ちゃんとCに提出したら通った。
問題：Aは映画館⇒店⇒家と帰り，Bは映画館⇒家と帰る。それぞれにt1, t2の距離の寄り道を許すとき，一緒に帰れる最大の距離は？
- とりあえずサンプルが通ったあたりでTime Up。
- 終わってから提出しましたがWAでした。あとで良く考えよう…。
- -
結果：0:18(+2) / 0:33(+1) / 1:25(+2) / --(+1) / -- ，76位
レーティング：1661
次の目標：もうちょっと落ち着いて行動する。
