!!!ACM/ICPC 2003アジア予選問題 解答例

[全問題(PDF)|http://ccserv.adm.ehime-u.ac.jp/ICPC/problems/regional/r2003.pdf]

!!Probrem A: Unreliable Messengers

途中で変化する伝言ゲームの、もとのメッセージを見つける。入力データは、誰を通って伝わったかと、伝わったメッセージ。

問題文の中に誰がどのようにメッセージを変えてしまうかが書いてあるので、その逆変換を伝わったメッセージに対して行っていけばよい。

解答例[[2003aa1.c]]

!!Probrem B: Lagrange’s Four-Square Theorem

ラグランジェの定理「どの整数も4つの平方数の和で表される」に基づいて、与えられた整数に対し4以下の平方数で表す組み合わせの数を求める。

すべての組み合わせをしらみつぶしに調べるようにして解いてみたけど、異様に時間がかかる。もっと賢い方法があるんだろうな。
→ 某S君のアドバイスに従ったら、全然簡単だった。

解答例[[2003ab1.c]]

!!Probrem C: Area of Polygons

ポリゴンの面積を求める。

!!Probrem D: Weather Forecast

天気予報。4×4の土地。神様になって2×2の雲を動かす。雲の下では必ず雨が降っている。雲は上下左右に1マスか2マス動かすか消し去ることができ、土地からはみ出ない。初日に雲は中心にある。

雨が6日間連続して降らないのは許される。

何日にどこで市場か祭があるというデータが入力される。

すべての条件を満たすことができるかできないかを出力。

!!Probrem E: Molecular Formula

分子式。元素の重さの表が与えられた時に、分子式の重さを求める。

まず、1文字か2文字かで判断し、元素表にある元素かどうか判断。次に数字がくるのか判断し、数字の場合はそれだけ倍にする。カッコが来た場合はそれまでの合計をスタックに退避しておけばよいだろう。逆ポーランド記法みたいなのを使えばもっと楽かも。

解答例[[2003ae1.c]]

!!Probrem F: Gap

トランプのソリティアみたいな物。ルールに沿って解けるか。11〜17, 21〜27, 31〜37, 41〜47の28枚のカード。10の位はマーク。4行7列に並べる。

まず11,21,31,41をみつけて一番左の列に順に移動。4つの空き(Gap)ができる。GapにはGapの左のカードに続くカードを移動できる。
 例) 42 Gap の時は 42 43 と43を移動できる。
27のように7の次はGapがあっても移動できない。

ゲームのゴールはすべてのカードを4行7列に順番に並べること。ゴールまでの最小手順の回数を出力。解けない場合は-1を出力。

!!Probrem G: Concert Hall Scheduling

コンサートホールのスケジューリング。同じホールが2つある。何日から何日までいくらで使いたいと言う要望があるので、できるだけお金を稼ぐようにスケジュールを組んだときの、儲けた金額を表示する。

!!Problem H: Monster Trap

怪物を直線で囲めたかどうか判定する。入力は直線の始点と終点の座標。怪物は原点(0,0)にいる。入力された直線で怪物を囲めたかどうか判定する。