新人SEの学習記録

14年度入社SEの学習記録用に始めたブログです。もう新人じゃないかも…

学習記録:ABC #069

[学習記録] ABC #069

いつも通り過去問を解いてみました。
なんとか解説を見ずに4問解けた!(所要時間1時間くらい)

プログラムはこちら。
atcoder/atcoder-prg/src/abc069 at master · ueriku/atcoder · GitHub

コンテストURL

abc069.contest.atcoder.jp

A問題

問題

東西にn本,南北にm本の通りがある。
東西南北を通りに囲まれた最小の領域を街区と呼ぶ時,街区が何個あるか求めよ。

解答

(n-1)*(m-1)を求めるだけ。

int n = in.nextInt(), m = in.nextInt();
System.out.println((n-1) * (m-1));

B問題

問題

3文字以上の文字列sが与えられる。
"internationalization"を"i18n"と略すように,同様の規則で文字列sを略したものを求めよ。

解答

sの先頭文字とsの文字列長-2,sの末尾文字をくっつけたものを出力すればOK。

char[] s = in.next().toCharArray();
String ans = "" + s[0] + (s.length-2) + s[s.length-1];
System.out.println(ans);

C問題

問題

長さNの数列a(a1, ... aN)が与えられる。
aの要素を自由に並べ替え,全ての隣り合うai, ai+1の積が4の倍数に出来る時"Yes",出来ない場合"No"を出力せよ。

解答

4の倍数の個数と,2の倍数(4の倍数を除く)の個数が大事なところまではわかった。
そこから色々と条件分岐を考えて解答。
解説を見たらもっと簡略化できたもよう。

String ans = "No";

// 4の倍数の個数と2の倍数の個数が特定の条件を満たすときに"Yes"になる
if (N % 2 == 0) {
    if (divisibleBy4 + divisibleBy2 / 2 >= N / 2) {
        ans = "Yes";
    }
}
else {
    if (divisibleBy4 + (divisibleBy2 - 1) / 2 >= N / 2) {
        ans = "Yes";
    }
}

D問題

問題

H * Wのマス目がある。これをN個の色で塗り分ける。
ただし,色iで塗られたマス目は全て隣り合っている必要がある。
また,色iで塗れるマス目の個数は,配列a(a1, ... aN)で与えられる。
このとき,条件を満たす塗り方を一つ求めよ。

解答

色を順番にマス目に塗っていくことになるが,横一列や縦一列に塗ろうとすると,
折り返しのときに色が隣り合わずに途切れてしまう可能性がある。
それなら渦巻状に塗っていけば良いんじゃないか?という発想で解答できた。
解説を見たら渦巻状で無くても,右に塗っていって端まで来たら一段下がって左へ・・・という塗り方で良かったorz
途中で上がったり下がったりと余計な苦労をしてしまった。。

// H, W, N, aについては取得済

int[][] ans = new int[H][W];

// 1 = 下/右方向 -1 = 上/左方向 0 = 移動しない
int dirH = 1;
int dirW = 0;
// h, wの初期値
int height = -1;
int width = 0;

// 各色について順番に塗っていく
for (int color = 0; color < N; color++) {
    // 色の数a[color]だけ塗りつぶしていく
    for (int i = 0; i < a[color]; i++) {
        // 次のマスへ移動
        height += dirH;
        width += dirW;
        
        // H * Wのマス目を越えてしまっている,もしくは移動先が既に塗られている場合
        if (height < 0 || height >= H || width < 0 || width >= W || ans[height][width] != 0) {
            // 移動する前に戻る
            height -= dirH;
            width -= dirW;
            // 向きを変える(下 -> 右 -> 上 -> 左の順に向きを変えていく)
            if (dirH == 0) {
                dirH = -dirW;
                dirW = 0;
            }
            else {
                dirW = dirH;
                dirH = 0;                        
            }
            // 今回のループでは何も塗らなかったので回数も戻す
            i--;
        }
        // 普通に濡れる場合
        else {
            // マス目を塗りつぶす(色は1オリジンなので1足す)
            ans[height][width] = color + 1;
        }
    }
}

for (int i = 0; i < H; i++) {
    for (int j = 0; j < W; j++) {
        out.print(ans[i][j] + " ");                
    }
    out.println();
}