猫でもわかるWebプログラミングと副業

本業エンジニアリングマネージャー。副業Webエンジニア。Web開発のヒントや、副業、日常生活のことを書きます。

AOJ 1295: Cubist Artwork

はじめに

問題文概訳

国際ピカソニアンキュビズムセンターは、ピカソによって建てられた、 スペインにあるキュビズム絵画に関する国際美術館である。 ここでは、美術館の正面に飾るモニュメントのコンテストを開催している。 モニュメントは、地面から積み上げられたキューブの集まりからなっている。 このモニュメントは、正面から見る場合と横から見る場合では見た目がかわり、 それが客の興味を引きつけるようになっている。

モニュメントは、キューブの集まりで、キューブの1辺は1フィートである。 地面は1フィートの方眼のようになっており、その平らな地面の上にモニュメントは建っている。 モニュメントのキューブは、地面の方眼に合わせるように配置されているか、 すでにあるキューブの上にピッタリと合わさるように配置されている。 キューブがずれるたような配置はされていない。

あなたは審査員の一人である。 審査基準にはモニュメントのクオリティだけでなく、 モニュメントを設置するコストも含まれる。 あなたの仕事は、それぞれのモニュメントに対して、設置コストを計算することだ。 コストはキューブの数だけかかる。 そのため、最小のキューブ数を求めて欲しい。

それぞれのモニュメントは、図のように正面から見た(平面の)図と、横から見た(平面の)図がある

(図は原文のものを参照してください)

図に対する立体的なモニュメントの作り方は、図のようにいくつか考えられる

左のようにモニュメントを作成すると、キューブは16個だがこれは最適ではない。 右のように作成するとキューブは13個でいい。

キューブの列を変更すると、横の図には変化がないが、正面からの図は変わる。 行を変更した場合は逆である。

もう一つ、図2のような例を挙げる。 これはキューブ13個で実現できる。これは図1のモニュメントをうまく変更することで実現できる。

入力

入力はいくつかのデータセットからなる。 入力の終わりは2つの0で与えられる。それぞれのデータセットのフォーマットは以下の通りである。

 w, d は地面の方眼の列と行であり、 1 \leq w \leq 10, 1 \leq d \leq 10 である。 次の行は正面からの図、その次は横からの図である。 左から右へ順番に、それぞれの高さhが与えられる。  1 \leq h \leq 20 である。

出力

モニュメント作成に必要な最小のキューブ数を一行で出力せよ。

解法

テストケース

5 5
1 2 3 4 5
3 3 3 4 5

を用いて説明する。

まず正面からの図を見ると、1+2+3+4+5 で15個のキューブが最低必要であることがわかる。

続いて横からの図を見る。この中で{3, 4, 5}の部分は、正面からの図で作った{3, 4, 5}の部分をうまく使いまわせば良いので、{3, 3} の部分だけは新しく作ればよい。よって、解答は15 + 3 + 3 = 21 である。実はこれだけで答えが出る。

実装においては、cnt[i] = 正面から見た時の高さiの列の数 として記録しておき、横を見ていくときに、cnt[i] を超えたら新しくキューブを積み重ねる、といった実装になっている。

実装

  • 入出力については自作クラスを使っているが、問題文に示された通りに入力を読んでいるだけである。
class Main extends MyUtil{
    // public static Graph g;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        while(true){
            int w = readIntMap(0);
            int h = readIntMap(1);
            if(w == 0 && h == 0) break;
            
            int[] hw = readIntMap();
            int[] hd = readIntMap();
            
            int[] cnt = new int[21];
            
            int ans = 0;
            for(int i : hw){
                ans += i;
                cnt[i]++;
            }
            
            for(int i : hd){
                if(cnt[i] <= 0) ans += i;
                cnt[i]--;
            }
            
            System.out.println(ans);
        }
    }
}