fc2ブログ



パソコン甲子園 2009 本線

2010.01.21 20:44  パソコン甲子園 2009

番号問題難易度分野
問題01 じゃんけん 基礎
問題02 旅行はいつ? 基礎
問題03 ブロック グラフ
問題04 病院の部屋番号 ★☆ 整数
問題05 写真に写っている景色は? ★★ 全探索
問題06 ザ・スクエアーズ ★★☆ シミュレーション
問題07 みんなでジョギング ★★☆ 整数
問題08 高速バス ★★★ グラフ
問題09 土地分割 ★★★ バックトラック
問題10 秋のイルミネーション ★★★ 計算幾何学
問題11 パチモンクリーチャー ★★★☆ 動的計画法
スポンサーサイト



テーマ : プログラミング - ジャンル : コンピュータ

| コメント(1) | トラックバック(0) | ↑ページトップ |




パチモンクリーチャー

2010.01.21 20:40  パソコン甲子園 2009

パソコン甲子園2009 問題11 パチモンクリーチャー


X×Y個のセルから成るグリッド上のスタート地点から出発し、全5種類のパチクリ(生物)を捕まえた状態でゴール地点まで行く最短コストを求める問題です。各パチクリはそれぞれ、火、氷、木、土、水の属性を持ち、火のパチクリは氷のパチクリを捕まえることができ、氷のパチクリは木のパチクリを捕まえることができ、といったように火→氷→木→土→水→火というような属性の関連があります。スタート地点で最初に持つパチクリを1つ選ぶことができます。グリッドのサイズx, y はそれぞれ2以上1000以下で、各属性のパチクリの数はそれぞれ0以上1000以下です(全体の数は5000以下)。

最初に1つのパチクリを選んだ後のパチクリを捕まえる順番は、上記属性の関連の順番になります。例えば最初に火の属性をもつパチクリを持っていれば、氷、木、土、水の属性をもつパチクリを順番に捕まえてゴールに行けばよいので、下図に示すDAG(Directed Acyclic Graph)の最短コストを求めることになります。下図は、3体の氷のパチクリ、2体の木のパチクリ、3体の土のパチクリ、2体の水のパチクリを含むグリッドをDAGで表したものです。捕まえられないパチクリがいるマスを通っても現在保持しているパチクリの状態に影響はないので、ノード間の距離は対応するマス間のマンハッタン距離(x座標の差とy座標の差の和)となります。スタート地点で選ぶパチクリを変えて(5種類分ありますが、下図では最初に火のパチクリを選んでいます)、動的計画法によってゴールまでの最短コストを求めます。
パチモンクリーチャー

テーマ : プログラミング - ジャンル : コンピュータ

| コメント(0) | トラックバック(0) | ↑ページトップ |




秋のイルミネーション

2010.01.21 20:34  パソコン甲子園 2009

パソコン甲子園2009 問題10 秋のイルミネーション


凸な四角形がいくつか与えられ、重なったあるいは触れている四角形を1つのグループと見なし、いくつのグループが存在するかを求める問題です。

2つの四角形が接触しているかどうかを判定するプログラムを使ってグラフをつくり、連結成分の数を深さ優先探索で求めます。四角形Aのいづれかの辺と四角形Bのいづれかの辺が接触している、四角形Aが四角形Bの頂点を含む、または四角形Bが四角形Aの頂点を含む場合、四角形Aと四角形Bが同じグループに属すると判定することができます。

テーマ : プログラミング - ジャンル : コンピュータ

| コメント(0) | トラックバック(0) | ↑ページトップ |




土地分割

2010.01.21 20:30  ACM/ICPC 2009

パソコン甲子園2009 問題09 土地分割


X×Y個のマスから成るグリッドで表された分譲地を、長方形の区画に分割する問題です。各区画の大きさ(マスの数)とその区画が含まなければならないマス(看板で示されています)が入力として与えられます。

全ての区画について順番に、要求された大きさの長方形で分譲地を埋めていきます。各区画の長方形の大きさと位置については、すでに決定した他の区画と重ならずかつ分譲地からはみ出さないような全てのパタンについて調べます。この処理は、再帰関数によって実装します。全ての区画について長方形が配置できかつ全てのマスが0以外で埋まっている場合は解としてカウントし、そうでない場合はバックトラックでさらに探索を行います。

テーマ : プログラミング - ジャンル : コンピュータ

| コメント(0) | トラックバック(0) | ↑ページトップ |




高速バス

2010.01.21 20:26  パソコン甲子園 2009

パソコン甲子園2009 問題08 高速バス


グラフのノード間(バス停間)の最短経路のコストを求める問題です。ただし、チケットを使った場合はノード間を行き来するコストが半分になります。最初に持っているチケットの数、スタート地点、ゴール地点が与えられたときの最短コストを求めなければなりません。

基本的にはダイクストラのアルゴリズムで解きます。ただし、グラフのノードは、与えられたグラフのノードi(バス停)と残りのチケットの枚数kの組になります。つまり、2次元配列D[i][k]に「k枚のチケットを持ちバス停iにいるスタート地点からの最小コスト」をダイクストラのアルゴリズムで記録します。

テーマ : プログラミング - ジャンル : コンピュータ

| コメント(0) | トラックバック(0) | ↑ページトップ |




みんなでジョギング

2010.01.21 20:24  パソコン甲子園 2009

パソコン甲子園2009 問題07 みんなでジョギング


同じスタート地点にいるn人の人がそれぞれ1周di(km)のコースをvi(km/h)で走り続けるとき、全員が再びスタート地点で同時に出会ったときの、それぞれの周回数を求める問題です。

n人をそれぞれ0~n-1の番号iで表すことにします。まず、計算途中でのオーバーフローを避けるために、それぞれのvi/diを約分します。次にvi/di (i = 0 ~ n-1)を通分します。全ての分母diに対する最小公倍数LCMを分母とすると、それぞれの分子はvi×LCM/diとなります。最後に全ての分子をそれらの最大公約数で割ると、最初に全員が出会う周回数となります。最大公約数を求めるためにはユークリッドの互除法を用います。

テーマ : プログラミング - ジャンル : コンピュータ

| コメント(0) | トラックバック(0) | ↑ページトップ |




ザ・スクエアーズ

2010.01.21 20:21  パソコン甲子園 2009

パソコン甲子園2009 問題06 ザ・スクエアーズ


グリッドで表された迷路の中にいる人々が、全員脱出するために必要な時間をシミュレーションによって求める問題です。一定時間毎に、グリッドのマスにいる人がある定められたルールに従いマス目間を移動していきます。

問題文に書かれている手順でアルゴリズムを実装します。最初のステップで、各人についてその人の方向を定義されたルールに従い決定します。次のステップにて、各人について現在の方向に動けるか否かを定義されたルールに従い決定し、動ける場合は移動します。

テーマ : プログラミング - ジャンル : コンピュータ

| コメント(0) | トラックバック(0) | ↑ページトップ |




写真に写っている景色は?

2010.01.21 20:05  パソコン甲子園 2009

パソコン甲子園2009 問題05 写真に写っている景色は?


数字が書かれたn×n個のマスから成るグリッドにおいて、同じく数字が書かれたm×m個のマスから成るグリッドを0, 90, 180, または270度回転させたパタンに一致する領域を探し、その位置を出力する問題です。

m×mのグリッドを回転しながら、全ての場所について一致しているかを調べていきます。n×nのグリッドにおけるm×mの領域について、上から下、左から右の順番で調べていきます。各領域について、m×mのグリッドを回転させ、重なった部分のマスが全て一致するか(問題の仕様上-1は無視します)をチェックします。

テーマ : プログラミング - ジャンル : コンピュータ

| コメント(0) | トラックバック(0) | ↑ページトップ |