fc2ブログ



土地分割

2010.01.21 20:30  ACM/ICPC 2009

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


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

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



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

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




Discrete Speed

2009.07.09 22:48  ACM/ICPC 2009

Discrete Speed
ダイクストラのD。
「現在の場所、前にいた場所、速度」のノードでグラフを作りました。

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

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




Verbal Arithmetic

2009.07.09 22:40  ACM/ICPC 2009

Verbal Arithmetic
バックトラックで解いてみました。 適当な枝刈りをすれば手元で10秒くらいorz。

優れた解法はlaycurseさんのブログを参照。

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

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




How Many Islands?

2009.07.09 22:34  ACM/ICPC 2009

How Many Islands?
パソコン甲子園に同じような問題が出題されていたような...

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

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




Next Mayor

2009.07.09 22:30  ACM/ICPC 2009

Next Mayor

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

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




ACM-ICPC 国内予選 2009

2009.07.09 22:26  ACM/ICPC 2009

番号問題難易度
A Next Mayor
B How Many Islands?
C Verbal Arithmetic ★★☆
D Discrete Speed ★★★
E Cards ★★★☆
F Tighten Up! ★★★★☆

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

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