- 追加された行はこのように表示されます。
- 削除された行は
このように表示されます。
!!!ACM/ICPC 2004国内予選問題 解答例
[問題文、入力データ、出力データ|http://ccserv.adm.ehime-u.ac.jp/ICPC/problems/domestic/d2004/]
問題AとBが簡単で、後は少し難しかった。予選突破は2問を早く解くか、3問以上解くかが要求された。
*[[Problem A|2004da]]: Hanafuda Shuffle 花札を切る
*[[Problem B|2004db]]: Red and Black 赤と黒
*[[Problem A|2004da]]: Hanafuda Shuffle 花札を切る (解答例あり)
*[[Problem B|2004db]]: Red and Black 赤と黒 (解答例あり)
*[[Problem C|2004dc]]: Unit Fraction Partition 単位分数の分割
*[[Problem D|2004dd]]: Circle and Points 円と点
*[[Problem E|2004de]]: Water Tank 水槽
*[[Problem F|2004df]]: Name the Crossing 交差点の名前
!!Problem A: Hanafuda Shuffle 花札を切る
カードを切るシミュレーションの問題。カードの枚数と、切る回数が指定される。切る操作は、カードの山の上からp枚目から連続したc枚を抜き取り、山の一番上に置く。
!入力
*まず、カードの枚数nと切る回数r。nとrに0が入力されたら全ての操作を終了する。
*続いてr回の切る操作のpとc。
!出力
*切る操作をした結果、1番上に来たカードの番号を表示する。カードの山には一番下から1，2，3，・・・,nと番号が付いている。
!データ構造
配列を用いる。
!解答例
*方法1：山を表す配列と、コピー用の配列の2つ用意しておき、コピーする分をコピー遙拝列に置いておいて、残りを移動してから、上書きする。
**解答例 [[2004da1.c]]
*方法2：配列は1つだけで、p枚目を一番上に持っていく、p+1枚目を上に持って行く、p+2枚目を・・・をc枚分繰り返せばよい。
**解答例
***C言語 [[2004da2.c]]
***Java [[hana1.java]] Javaは入力が面倒だ。
問題の意味と入力データの意味を理解し、配列を使うときに添え字の番号を間違えなければ、素直に解けるでしょう。
----
!!Problem B: Red and Black 赤と黒
赤いタイルと黒いタイルが強いてある部屋で、隣接している黒いタイルだけ移動できる。このとき、最初の位置から移動できるタイルの枚数を数える問題。
!入力
*まず部屋の大きさW(横)とH(縦)。2つとも0だったら終了する。
*続いて文字の入力。．(ドット)が黒いタイル(移動できる場所)、＃が赤いタイル(移動できない場所)、＠が最初の位置を表す。
!出力
*最初の位置から到達可能なタイルの数を表示。
!データ構造
2次元配列で部屋を表現する。文字2次元配列でも解けると思うが、整数型にしてしまったほうが考えやすいかも。黒いタイルを0、赤いタイルを1などとして。
!解答例
*方法1：再帰でバックトラックのやり方が分かれば、解けるかな。
**[[2004db1.c]]
*方法2：再帰を使わなくても作れる。部屋の広さが大きいときは時間がかかるかも。
**C [[2004db2.c]]
**Java [[randb.java]]
----
!!Problem C: Unit Fraction Partition 単位分数の分割
与えられた分数を、単位分数(1/2 や 1/3 のように分子が1の分数)の足し算に分解する問題。
!入力
*p q a n の4個。全て0のときに終了。
**p と q は分数 p/q 表す。aは単位分数に分割したときの分子を全てかけたときの最大値。nは最大でn個に分割することを表す。
!出力
*この分割の仕方が何個あるか答える。
再帰を使う必要あり。少し難しい。
----
!!Problem D: Circle and Points 円と点
平面上に点が何個かある。半径1の円を動かして一番多く囲むことができる点の数を答える。
!入力
*最初に点の個数N。0で終了。
*次にN組のx座標とy座標。
総当たりにやるんだろうけど、計算量が多いので工夫が必要。誤差が出てくるのでそれをどう扱うか考える必要がある。難しい。
----
!!Problem E: Water Tank 水槽
水槽の形と、入れる水の量が与えられたときの、ある時点での水の高さを答える。
!入力
*まずデータセットの数。データセットは以下の3組。0の場合終了。
**次に区切り板の枚数。続いてそれを置くx座標と、その高さ。
**次に水道の蛇口の数。続いてそれのあるx座標と、1秒間に流れる水量(cm3/秒)。
**次に水の高さを測定する回数。続いてx座標と測定する時間(開始時からの秒数)。
!出力
*指定された時刻における水の高さを表示する。
これまでとは違ったパターンの問題。問題の意味は分かるだろうけど、どうやってプログラムするか。難しそう。
----
!!Problem F: Name the Crossing 交差点の名前
「Kawaramachi-Sanjo」のような交差点のリストが与えられる。KawaramachiとSanjoは東西か南北に通る道路の名前で、どちらが先に来るか優先順位がある。与えられた交差点のリストから優先順位を見つけ、交差点のリストが有効な交差点か、向こうかを判断する。問題を理解するのが難しそう。