国内予選2008
Problem A
Equal Total Scores
等しい合計点
Problem B
Monday-Saturday Prime Factors
月曜土曜素因数
Problem C
How can I satisfy thee? Let me count the ways...
如何に汝を満足せしめむ? いざ数え上げむ…
C_tk3.c シンプルイズザベスト。某ソースに触発されて作成。46行。
C_tk.cpp LLパーサで項の値27通りすべてを列挙しながら最終的な値を求める
C2_tk.cpp 文字列置換によって式を3値に還元する
C.c 3行。231byte。
C_tk.cpp LLパーサで項の値27通りすべてを列挙しながら最終的な値を求める
C2_tk.cpp 文字列置換によって式を3値に還元する
C.c 3行。231byte。
Problem D
Twirling Robot
ちょろちょろロボット
D_tk.cpp 位置と向きで拡張ダイクストラ
Problem E
Roll-A-Big-Ball
大玉転がし
E_tk.cpp 真上から見るとブロックは矩形に,コースは線分になるので,ブロックとコースの距離を求める問題は線分と点の距離を求める問題に分解できる.各ブロックの距離から最小の半径を求める.本番データ未確認.コースの始点と終点が共にブロックの中に入っている場合を考慮していなかった.修正.本番データ確認.
Problem F
ICPC: Intelligent Congruent Partition of Chocolate
ICPC: チョコレートの知的合同分割
F_tk.cpp
1、達也(以降A)に属するチョコを1つ決め、それに対応する和也(以降B)に属するチョコとその方向を決める。これで二つの欠片の位置関係が決定される。
2、位置関係を元にすべてのチョコに対して、そのチョコがAに属した場合それに対応するBのチョコ、そのチョコがBに属した場合それに対応するAのチョコを求める。ここで対応関係がないチョコが発生した場合はその位置関係では解くことができないので1に戻る。
3、1で決めたAに属するチョコの集合に隣接し、かつ対応するBのチョコが存在するチョコをAの集合に追加。それと対応するチョコをBの集合に追加。
4、バックトラックで3を繰り返し、全パターンを試すか、答えが見つかるまで3を繰り返す。
5、答えが見つかっていなければ1に戻り、対応するBに属するチョコの位置と方向を変えリトライ。
単なる探索だけど枝切りの条件がかなり厳しいので早い?。本番データ未確認。サンプルは一瞬だった。チョコは空洞でないという条件を利用していない。審判団は別の解法を意図している?Celeron1.5Ghzに本番データF1−4を食わせたところ0.6sだった。
1、達也(以降A)に属するチョコを1つ決め、それに対応する和也(以降B)に属するチョコとその方向を決める。これで二つの欠片の位置関係が決定される。
2、位置関係を元にすべてのチョコに対して、そのチョコがAに属した場合それに対応するBのチョコ、そのチョコがBに属した場合それに対応するAのチョコを求める。ここで対応関係がないチョコが発生した場合はその位置関係では解くことができないので1に戻る。
3、1で決めたAに属するチョコの集合に隣接し、かつ対応するBのチョコが存在するチョコをAの集合に追加。それと対応するチョコをBの集合に追加。
4、バックトラックで3を繰り返し、全パターンを試すか、答えが見つかるまで3を繰り返す。
5、答えが見つかっていなければ1に戻り、対応するBに属するチョコの位置と方向を変えリトライ。
単なる探索だけど枝切りの条件がかなり厳しいので早い?。