2010-12-05

■ [Codeforces]Codeforces Beta Round #43 00:50

2010-12-05 17:00-20:00

http://codeforces.com/contest/46

ID	タイトル	結果	ひとこと
A	Ball Game	AC 00:14	ひどい問題文ミス
B	T-shirts from Sponsor	AC 00:14	やるだけ
C	Hamsters and Tigers	AC 00:20	真面目に考えない
D	Parking Lot	AC 00:47	ぐだぐだ場合分け
E	Comb	WA*1->AC 01:10	DP, 整数オーバーフロー
F	Hercule Poirot Problem	WA*3->AC 02:50	UnionFind
G	Emperors Problem	Opened	謎幾何

Coding

• A
  • さすがにやるだけ
  • 答え合わない…
  • どう考えてもおかしい
  • 後回し
• B
  • まあこれもやるだけ
  • AC
• A
  • そうこうしているうちに案の定Aの訂正が来ていたので提出
  • AC
• C
  • 難しく考えるとハマりそうだけど
  • O(N^2)で良いよね
  • ハムスターの固まりになる部分の先頭位置を全通り試した
  • AC
  • どうでもいいけどタイトルが最初 Hanshin Tigers に見えた
• D
  • がんばって実装するだけっぽい
  • あんまり考えずに書いてたら両端の処理が面倒なことになってしまった。番兵使うべきだった
  • なんとか一発AC
• E
  • 問題文の意味がつかみづらい
  • いかにもDPだ
  • 単純にやるとO(N*M*M)でTLEするのでオーダーを落とす
    • たとえばi行目（i:偶数）の状態を更新するとき、
    • i行目をj個取る場合に最適になるのは、
    • 「i-1行目でj+1個取った場合、j+2個取った場合、…、N個取った場合 のうち最大になるもの」に、i行目の分を足したもの
    • 同様に、i行目をj-1個取る場合に最適になるのは
    • 「i-1行目でj個取った場合、j+1個取った場合、j+2個取った場合、…、N個取った場合 のうち最大になるもの」に、i行目の分を足したもの
    • けど、j個の場合を除いた「j+1個取った場合〜N個取った場合」の部分はさっき求めたので再度計算しなくても良い
    • ということを利用してO(N*M)にする
  • WA
  • 整数オーバーフローしてた…。1回確認したはずだったが計算違いをしていた
  • AC
  • 問題文が読みづらいのを除けば、けっこうありがちなDPで練習に良い問題だと思います
• F
  • どの部屋が繋がっているかUnionFindで管理して、ベルマンフォードみたいにN周回して空けられるところは全部空けていく
  • 全部ドアを開けた状態で、各人と各鍵が2日目の位置まで移動できるかを判定する
  • WA
  • さっぱりわからないのでよーく問題を読んでみると条件の見落としに気づいた
  • 最終的に鍵は全部閉じないといけない。閉じることができるかどうかも判定しないといけない
  • けどこれグラフ理論的にやろうとすると難しい…（自分がグラフ苦手だからかもしれないけれど）
  • ふと思いついた
  • 全部空いた状態から鍵を閉めていって最後の状態にできる⇔最後の状態から鍵を開けていって全部空いた状態にできる
  • だから、鍵を閉めることは考えずに、1日目→2日目にできるかどうかと、その逆の2日目→1日目にできるかどうかを見れば良い
  • AC
• G
  • 解がないケースはなさそうだと思うのだけど
  • 解法不明

結果

• 7問中6問AC
• Penalty：415
• 順位：22位/644人
• レート：1865->1994

赤までもうひといき