新人SEの学習記録

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

学習記録:ABC #070

[学習記録] ABC #070

引き続きAtCoder Beginner Contestの過去問を解いてます。

コンテストURL

abc070.contest.atcoder.jp

結果

D問題だけ解説を見ないと解けず。。
コードは以下に格納してます。
atcoder/atcoder-prg/src/abc070 at master · ueriku/atcoder · GitHub

A問題

問題

3桁の整数Nが与えられる。
Nが回文数(逆に並べても元の数と同じ数になる)の場合"Yes", そうでない場合"No"を出力せよ。

解答

100の桁(N / 100の整数値)と1の桁(100で割った余りを10で割った余り)が等しければYes。

public void calc() {
    int N = in.nextInt();

    String ans = (N / 100 == (N % 100) % 10)? "Yes" : "No";
        
    out.println(ans);
    out.close();
}

B問題

問題

AliceはA秒後からB秒後までスイッチを押し,BobはC秒後からD秒後までスイッチを押す。
ふたりともスイッチを押していた秒数を求めよ。

解答

色々条件分岐で出した。解説を見るともっと簡単に求められる模様。
重複してなければ0秒,重複していればmin(B, D) - max(A, C)で良いとのこと。

int calcTime(int A, int B, int C, int D) {
    // C <-> DがA <-> Bの範囲と重複しない場合
    if (B <= C || D <= A) {
        return 0;
    }

    // CがAより小さい場合
    if (C < A) {
        // DがB以下なら,A<->Dが重複範囲となる
        if (D <= B) {
            return D - A;
        }
        // DがBより大きければ,A<->Bが重複範囲となる
        else {
            return B - A;
        }
    }
    // 残るケースはCがAとBの間にある場合のみ
    else {
        // DがB以下なら,C<->Dが重複範囲となる
        if (D <= B) {
            return D - C;
        }
        // DがBより大きければ,C<->Bが重複範囲となる
        else {
            return B - C;
        }   
    }
}

C問題

問題

N個の整数T1...TNの最小公倍数を求めよ。

解答

T1とT2の最小公倍数を求め,その値とT3の最小公倍数を…と求めていけば良い。
ユークリッドの互除法で最大公約数を求め,それを使って最小公倍数を求める。
割り算の順序を間違えると桁が溢れてしまったりするので注意。

// 最小公倍数を求める
private long lcm(long a, long b) {
    // gcdでの割り算を先にすることで桁あふれを防ぐ
    return a / gcd(a, b) * b;
}

// 最大公約数を求める
private long gcd(long a, long b) {
    if (a > b) {
        return gcd(b, a);
    }
    while (a != 0) {
        long tmp = a;
        a = b % a;
        b = tmp;
    }
    return b;
}

public void calc() {
    int N = in.nextInt();
    long[] T = new long[N];

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

    long ans = 1;
    
    for (int i = 0; i < N; i++) {
        ans = lcm(ans, T[i]);
    }
    
    out.println(ans);
    out.close();
}

D問題

問題

N頂点の木が与えられる。辺はN-1本あり,頂点aiとbiを距離ciで繋ぐ。
質問がQ個与えられ,それぞれについて頂点xiと頂点yiが示される。
また,加えて頂点Kが与えられる。
このとき,各質問について,頂点xiから頂点Kを経由し,頂点yiまで移動する場合の最短距離を求めよ。

解答

ワーシャルフロイド法を使ったところ,longのN*N二次元配列のせいでMLEになってしまった。
そもそも任意の2頂点を繋ぐ辺は1本しか無いので,全通り探索するのはちょっと無駄が多い。
解説と以下のブログ記事を読んで,深さ優先探索で書いてみた。
AtCoder Beginner Contest 070 /解説 - 絶賛工事中

木構造Javaで表すのをどうすれば良いか迷っていたが,上の記事ではTreeMapのArrayListで表現していた。
Listのi番目に入っているMapには,町iから伸びている道の情報が入っている。
MapのKeyが道の続いている町で,Valueは距離を示している。
このMapを,町Kから深さ優先探索していき,町Kから他の町への最短距離を計測する。
最終的に求めるのは,町Kからxiへの最短距離と,yiへの最短距離になる。

// 木構造を表すリスト。
// i番目のリストに入っているMapは,町iから伸びる辺を著す。 
// MapのKeyは辺が続く町で,Valueは距離を示す。
ArrayList<TreeMap<Integer, Long>> treeList = new ArrayList<TreeMap<Integer,Long>>();
// dist[i]: 町iから町Kへの最短距離
long[] dist;

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

    for (int i = 0; i < N-1; i++) {
        a[i] = in.nextInt() - 1;
        b[i] = in.nextInt() - 1;
        c[i] = in.nextLong();
    }
    
    int Q = in.nextInt();
    int K = in.nextInt() - 1;
    int[] x = new int[Q];
    int[] y = new int[Q];

    for (int i = 0; i < Q; i++) {
        x[i] = in.nextInt() - 1;
        y[i] = in.nextInt() - 1;
    }

    // treeListの初期化
    for (int i = 0; i < N; i++) {
        treeList.add(new TreeMap<Integer, Long>());
    }
    
    // 道の情報をtreeList(の中のMap)に入れていく
    for (int i = 0; i < N-1; i++) {
        treeList.get(a[i]).put(b[i], c[i]);
        treeList.get(b[i]).put(a[i], c[i]);
    }
    
    dist = new long[N];
    // 各点からKへの距離を求める
    dfs(-1, K, 0);
    
    for (int i = 0; i < Q; i++) {
        out.println(dist[x[i]] + dist[y[i]]);
    }
         
    out.close();
}

// 町Kから順に深さ優先探索を実施して,Kから各町への最短距離を求める
// 引数によって,前の町はfrom,現在の町はtoであり,ここまで距離len掛かっていることを表す。
// 町Kから現在地toまでの距離dist[to]を距離lenで初期化し,
// 次の町への道をtreeListから取得して再帰を行う。
// 再帰を行う際に町fromへ戻ってしまうと無限ループに陥るので,その前に来た道を除外している。
void dfs(int from, int to, long len) {
    // toへの距離をlenで初期化
    dist[to] = len;
    // K番目の町から伸びた道の情報が入ったMapを取得
    TreeMap<Integer, Long> map = treeList.get(to);
    // 来た道を消す(探索から除外する)
    map.remove(from);
    // 次の町toに着いたものとし,そこから再度dfsする。
    // その際,今来た町toをfromとし,fromから続く道をMapから取り出して,次の町とそこまでの距離を計算する
    map.forEach((k, v) -> dfs(to, k, len+v));
}