スポンサーサイト

--.--.-- --:--  スポンサー広告

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

| - | - | ↑ページトップ |




パソコン甲子園 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) | ↑ページトップ |




病院の部屋番号

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

パソコン甲子園2009 問題04 病院の部屋番号


4と6の数字を使わない数字の列S = {1, 2, 3, 5, 7, 8, 9, 10, 11, 12, 13, 15, ...} のn番目の数を求めよという問題です。ただし、nの値は最大1,000,000,000です。

nの値が非常に大きいため、数列を生成して解くことはできません。4と6の2つの数字を用いてはいけないので、10 – 2 = 8 進数でnを表せばよいことになります。ただし、基数変換後の数の各桁の数字をdとすると、dが0~3の場合はそれぞれ0~3、dが4の場合はd+1(4の分)= 5、dが5以上の場合はd+2(4と6の分)に変換して出力します。文字列”01235789”のd番目の文字を返す関数を定義しても良いでしょう。

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

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




ブロック

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

パソコン甲子園2009 問題03 ブロック


2次元グリッド(配列)上に迷路を作り、スタートのマスからゴールのマスまでの道があるかどうかを判定する問題です。各マスには色がつけられ、色が同じマス間を上下左右の方向に移動することができます。

深さ優先探索または幅優先探索によって解くことができます。以下に示す解答プログラムでは深さ優先探索を実装しています。深さ優先探索は、一度訪問したマスを二度訪問しないように注意しながら、再帰的に隣接するマスを訪問していくアルゴリズムです。プログラムの関数dfsに示すように、グリッドにおける探索の問題では、現在地からのx方向及びy方向への移動距離を示すdx[4]、dy[4]を宣言しておくと、グリッドのマス間の移動の記述を簡潔に記述することができます。

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

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




旅行はいつ?

2010.01.21 19:59  パソコン甲子園 2009

パソコン甲子園2009 問題02 旅行はいつ?


1カ月に得られるお小遣いMと使うお金Nの組を12カ月分入力し、目的の金額Lに達するために必要な月数tを求める問題です。

合計金額Sが目的の金額Lに達したとしても12カ月分(i: 1~12)のMとNの組を読み込まなければならないことに注意しながら、(M - N)の合計金額Sが目的の金額Lに達する月tを求めます。tの初期値を0とし、SがL以上でかつtが0(初期値から未だ変更されていないことを示す)のとき、tに現在の月iを代入します。

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

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




じゃんけん

2010.01.21 19:52  パソコン甲子園 2009

パソコン甲子園2009 問題01 じゃんけん


5人がじゃんけんをしたときのそれぞれの手(グー、チョキ、パーをそれぞれ1~3で表します)を入力し、それぞれの人の勝ち・負け・引き分け(それぞれ1~3で表します)を判定する問題です。

様々なアルゴリズムが考えられる興味深い問題の1つです。ここでは、2重ループを使ったアルゴリズムで解きました。各人について他の4人に対する勝ち・負けの数をそれぞれ数え、「勝ちが1つ以上でかつ負けが0」の場合は勝ち(1)、「負けが1つ以上でかつ勝ちが0」の場合は負け(2)、その他の場合は引き分け(3)、と判定することができます。2人に対する勝敗判定については、1(グー)→ 2 (チョキ)→ 3(パー)→ 1(グー)・・・という関係があるので、A君の手をa、B君の手をbとすれば、a%3 が b-1 に等しいとき、A君がB君に勝ったと判定することができます。ここで、a%3はaを3で割った余りを示します。

データセットごとに処理しなければならない入力については、一人目の手を読み込みそれが0でない場合処理を行うという繰り返し構造とし、処理の最初に残りの4人分の手を読み込むとう手順で記述すると良いでしょう。

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

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

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。