新人SEの学習記録

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

学習記録:ABC #067

[学習記録] ABC #067

またまた引き続き過去問の学習。
相変わらずD問題は解説を見ないとダメ。。

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

コンテストURL

abc067.contest.atcoder.jp

A問題とB問題は簡単だったので省略。

C問題

問題

N枚のカードの山があり,上からi番目のカードには整数aiが書かれている。
すぬけ君がこのカードの山の上から何枚かカードを取ったとき,取ったカードに書かれた数の総和をx,残りのカードに書かれた数の総和をyとし,|x-y|としてありうる値の最小値を求めよ。

解答

上手いことやろうとして結構WAを連発してしまった。
愚直に|x-y|を毎回計算するようにして,その最小値をそのまま出すようにしてACにできた。

for (int i = 0; i < N; i++) {
    a[i] = in.nextLong();
    sum += a[i];
}

// まずは1枚目のカードを引いた状態にする
// 現在の引いたカードの合計値はa[0]
long snuke = a[0];
// 現在の|x - y|はsum - 一番上のカードの値*2
long cur = Math.abs(sum - snuke * 2);
// 答えとなる|x - y|の最小値
long ans = cur;

// 両者とも1枚は引かないといけないので,iは1〜N-2でループさせる
for (int i = 1; i < N - 1; i++) {
    // 新たにa[i]を引く
    snuke += a[i];
    // 現在の|x - y|を計算
    cur = Math.abs(sum - snuke * 2);
    // 答えを更新
    ans = Math.min(ans, cur);
}

D問題

問題

1からNまでの番号のついたN個のマス目があり,マス目はN-1本の道でつながれている。
i番目の道はai番のマスとbi番のマスを繋げており,どの2つのマスも隣接するマスを辿って必ずたどり着くことができる。
はじめに1番のマスは黒く,N番のマスは白く塗られている。
先手のフェネックは黒いマスから隣接した何も塗られていないマスを1つ選んで黒く塗り,後手のすぬけくんは白く塗られたマスから隣接した何も塗られていないマスを1つ選んで白く塗る。
手番のプレイヤーがマスに色を塗れなかったとき敗者となる。フェネックとすぬけくんが最適に行動したときの勝者を出力せよ。

解答

木構造が毎回苦手。。
まずは1番のマスからN番のマスへの最短パスを塗っていくのが最適戦術だと思いつくことが必要。
続いて,その場合には,あるマスについて1番のマスからの距離がN番のマスからの距離が近い場合,そのマスは黒く塗れることがわかる。(解説を読むまでわからなかった。。)
その1番マスおよびN番マスからの距離だけを見て黒か白か判定して,黒の方が多ければフェネックの,白の方が多ければ(+同数なら)すぬけくんの勝ちとなる。

// 木構造を表すリスト。
// i番目のリストには,マスiから伸びている道が続くマス目の番号が入る
List<List<Integer>> treeList;
// 深さ優先探索で使うフラグ配列。マス目iが既に通ったか否かを表す
boolean[] done;
// マス1から他のマスへの距離およびマスNから他のマスへの距離
int[] dist1, distN;    

public void calc() {
    int N = in.nextInt();
    int[] a = new int[N-1], b = new int[N-1];

    // treeListの初期化
    treeList = new ArrayList<List<Integer>>();
    for (int i = 0; i < N; i++) {
        treeList.add(new ArrayList<Integer>());
    }

    for (int i = 0; i < N-1; i++) {
        a[i] = in.nextInt() - 1;
        b[i] = in.nextInt() - 1;
        treeList.get(a[i]).add(b[i]);
        treeList.get(b[i]).add(a[i]);
    }
    
    done = new boolean[N];
    dist1 = new int[N];
    distN = new int[N];
    
    // マス1からの深さ優先探索
    dfs(0, 0, dist1);
    // マスNからの深さ優先探索(フラグも初期化)
    Arrays.fill(done, false);
    dfs(N-1, 0, distN);
    
    // フェネックとsnukeが穫れるマス目の数
    int fennec = 0, snuke = 0;    
    for(int i = 0; i < N; i++) {
        // マス1からの方が近ければフェネックが取れる
        if (dist1[i] <= distN[i]) {
            fennec++;
        }
        else {
            snuke++;
        }
    }
    
    // snukeが取れるマス目がフェネックと同数以上ならsnukeの勝ち
    String ans = "Fennec";        
    if (snuke >= fennec) {
        ans = "Snuke";
    }
    
    out.println(ans);
    out.close();
}

void dfs(int to, int len, int[] dist) {
    if (done[to]) {
        return;
    }
    done[to] = true;
    dist[to] += len;
    treeList.get(to).forEach(next -> dfs(next, len+1, dist));             
}