スポンサーサイト

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

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

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




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




錬金マスター

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

パソコン甲子園2009予選 問題07 錬金マスター

問題はこちら

レシピの連鎖にサイクルが無いので、再帰で最小コストを求めることができます。

問題の仕様は残念ながら簡単化されていて(難易度調整のためでしょう)、サイズが小さく、作るものも1つ、1つのアイテムを作るレシピはたかだか1つしかないので、メモする(動的計画法にする)必要もないようです。

以下のプログラムは1つのアイテムが複数のレシピを持てるようにしてあります。

名前、値段、レシピのリストを持つ Item クラスを作ります。
getCost( stirng name ) で名前が nameである アイテム item を作る最小のコストを求めます。
最小のコストは以下のうち小さい方になります:
  • item のコスト
  • item を作るレシピの中でコストが最小のものであるコスト

この問題の仕様ではレシピが1つしかないので、以下のうち小さい方を選べばよい:
  • item のコスト
  • item をレシピで作る(ある場合は)コスト


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

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




高校生一人旅 ~青春の片道切符編~

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

パソコン甲子園2009予選 問題06 高校生一人旅 ~青春の片道切符編~

問題はこちら

グラフの最短経路(コスト)を求める問題です。残念ながら典型的な問題です。
ワーシャルフロイドが想定解法なのかもしれませんが、 ダイクストラのアルゴリズムで解きました。

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

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




難儀な人たちが座る椅子

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

パソコン甲子園2009予選 問題05 難儀な人たちが座る椅子

問題はこちら

面倒なシミュレーションの問題です。

A, B, C, D それぞれの国の人の座り方をシミュレートする関数、setLeft, setB, setC, setD を素直に作りました。

椅子の状態を保持する配列(ここでは配列C)の先頭と末尾に番兵として'X'などを入れておくと実装が楽になるかと思います。

setD で使う getDist(int p, int d) は、p 番目の椅子から d 方向 (正が右、負が左)への空席の数を返します。

問題原文にある、椅子のサイズは大きすぎると思うのですが・・・ミスプリントでしょうね(AOJでは修正されています)。

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

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




芸術家品川のピンチ

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

パソコン甲子園2009予選 問題04 芸術家品川のピンチ

問題はこちら

少し面倒なサイコロ(立方体)回転シミュレーションの問題です。

x軸、y軸、z軸を中心に回転させるメソッドを定義した Cubeクラスを作り、 与えられたサイコロの中でユニークなものの数を数えます。

サイコロiとサイコロjが等しいかどうかは、 サイコロjの向きを固定し、サイコロiを回転させて、全ての向き(24通り)についてjと比較し、1つでも一致すれば、等しいと判断します。

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

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




最大公約数-ユークリッドの互除法

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

パソコン甲子園 2009 予選 問題03 最大公約数-ユークリッドの互除法

問題はこちら

参加ついでにユークリッドのアルゴリズムを習得しましょう、という問題です。
説明されている通りに実装します。「X >= Y になるように」という条件を忘れずに。

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

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




野球大会

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

パソコン甲子園2009予選 問題02 野球大会

問題はこちら

ソート(初等的なアルゴリズムでも可)を実装させる問題です。
比較演算子を定義した Team クラスを作り、ソートしました。
(慣れない場合は、基準を変えてソートを2回行えば良い。)

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

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




十日市での人気の出典は

2009.09.07 21:54  パソコン甲子園 2009

パソコン甲子園2009予選 問題01 十日市での人気の出典は

問題はこちら

プログラミングの基礎知識を問う問題です。 最初に A を最大値としておき、残り4人分を読み込んで最大値を更新していくという感じに書きました。

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

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

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