OBOG夏合宿 2008 - プログラミング道場 ACM/ICPC

OBOG夏合宿 2008

問題/講評/ジャッジデータ

2nd Day

Problem A: Pi is Three

A_tk.cpp

Problem B: Left Hand Rule

B_tk.cpp ハマった箇所多し。壁を線として左手ルールを実装。
B_tk2.cpp 講評参照。

Problem C: Alice and Bob

Problem D: Deadly Dice Game

D_tk.cpp 講評参照。

Problem E: Reverse a Road

E_tk.cpp 始点と終点からダイクストラ。i番めの道を逆転した場合のコストを求める。オーダはO（N^2）

Problem F: Webby Subway

Problem G: Time Trial

G_tk.cpp 公開されているインプットがCeleron1.5Ghzで2分。岩の位置と勇者の位置を座標で保存。勇者の位置を岩の隣接位置に限定。実装がヘタレ？

Problem H: Vending Machine

H_tk.cpp 動的計画。講評の方法と違う。計算量はO(2^N M)で最大で一千万。構造が単純だから問題無いだろうと考え実装。インプットがCeleron1.5Ghzで3秒。

Problem I: Memory Match

I_tk.cpp 講評参照。ボトムアップ。メモライズ。

Problem J: Tile Puzzle

J_tk.cpp 講評参照。Gauss-Jordan。ピボット選択で対角成分が０になっても操作を止めない。double使わずともintで十分。