fc2ブログ



病院の部屋番号

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) | ↑ページトップ |




パソコン甲子園 2009 予選

2009.09.19 23:08  パソコン甲子園 2009

番号問題難易度分野
問題01 十日市での人気の出典は 基礎
問題02 野球大会 ソート
問題03 最大公約数-ユークリッドの互除法 整数
問題04 芸術家品川のピンチ ★★☆ シミュレーション
問題05 難儀な人たちが座る椅子 ★★☆ シミュレーション
問題06 高校生一人旅~青春の片道切符編~ ★★☆ グラフ・最短経路
問題07 錬金マスター ★★★ 動的計画法(探索?)
問題08 上司のおごり ★★★ 動的計画法
問題09 会津山スキー場の新企画 ★★★ 動的計画法
問題10 UFO撃墜作戦 ★★★☆ 計算幾何学・シミュレーション


難易度の差や想定解法などを考えると、 バランスの良い問題セットとは言えませんね。

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

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




UFO 撃墜作戦

2009.09.07 22:55  パソコン甲子園 2009

パソコン甲子園2009予選 問題10 UFO 撃墜作戦

問題はこちら

計算幾何学+シミュレーションの問題です。
円と線分の交差判定ができるかが問われています。

少し面倒ですが、円と直線の交点を求めて、 それが有効範囲のレザーの上(線分)にあるかどうかを判定しました。

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

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




会津山スキー場の新企画

2009.09.07 22:50  パソコン甲子園 2009

パソコン甲子園2009予選 問題09 会津山スキー場の新企画

問題はこちら

典型的な動的計画法の問題です。

マス(y, x)にたどり着く場合の数は、以下のものの合計になります:
  • マス(y-1, x) (そこが移動可能なマスの場合)
  • マス(y-1, x-1) (そこが移動可能なマスの場合)
  • マス(y-1, x+1) (そこが移動可能なマスの場合)
  • マス(y-2, x) (そこがジャンプ台の場合)

ただし、 y が増えていく方向に(順番に)計算を行います。
例えば、マス(y, x)が移動可能な場所であれば、
マス(y+1, x)
マス(y+1, x-1)
マス(y+1, x+1)
にそれぞれ マス(y, x)の値を加算していきます(移動可能な場合のみ)。

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

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




上司のおごり

2009.09.07 22:43  パソコン甲子園 2009

パソコン甲子園2009予選 問題08 上司のおごり

問題はこちら

典型的な動的計画法の問題です。

K[i] を i 番目の金額、
Ti[j] を i 番目までの金額を使って j を払えるかのフラグとする (1の場合に払えるものとする)と、

T0[j] を 0 で初期化し、
Ti[j] = Ti-1[j] | Ti-1[j - K[i]]

となります。

あとは、i が素数で T[i] が 1 である i の最大値を求めます。


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

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