新人SEの学習記録

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

学習記録:ABC #074 D問題

[学習記録] ABC #074 D問題

できなかったD問題を解いてみました。
プログラムはこちら。
atcoder/Main.java at master · ueriku/atcoder · GitHub

コンテストURL

abc074.contest.atcoder.jp

問題

N個の都市があり,ある都市間は道路で双方向に結ばれている。
どの都市からどの都市へも,必要であれば他の都市を経由することで移動ができる。
N*Nの表Aが与えられ,Ai,jは都市iからjへの最短経路の長さを示すものとする。
このような道路の構造が存在するか判定し,存在する場合はそのような道路の構造のうち,存在する道路の長さの和が最小となるものを求めよ。
存在しない場合は-1を出力せよ。

解答

最短距離と聞いて真っ先にワーシャルフロイド法が思い浮かんだが,今回の問題では既に最短距離(と思われるもの)が与えられている。
まずはこのグラフAを更にワーシャルフロイド法に掛けて,本当に最短距離のグラフなのか確かめる。
続いて道路の長さの和を求める必要があるが,解説を見てもなかなか良くわからなかった。
結果的には,各A[i][j]を足し算していき(A[i][j]とA[j][i]は二重カウントしないようにする),
経由地kをとったときに,A[i][j] == A[i][k] + A[k][j]となるようなkが存在する場合,その道路の長さA[i][j]はカウントしないようにすることで,答えを求めることができた。

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

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            A[i][j] = in.nextInt();
        }
    }

    // グラフAとなる道路の構造が存在しなければtrue
    boolean notExist = false;
    // 答えとなる道路の長さの和(存在しない場合-1)
    long ans = 0;

    // A[i][j]について調べる
    for (int i = 0; i < N; i++) {
        if (notExist) {
            break;
        }
        for (int j = i + 1; j < N; j++) {           
            if (notExist) {
                break;
            }                
            // 道路の長さの和に加える必要がある場合true
            boolean add = true;
            // 各A[i][j]について,経由地kをとった場合を見ていく
            for (int k = 0; k < N; k++) {
                // i == kまたはj == kの場合はカウントしない
                if (i != k && j != k) {
                    // kを経由した際,そちらの方がA[i][j]より短い距離で行けてしまう道が存在する場合,
                    // このグラフAを満たす道路の組み合わせは存在しない                        
                    if (A[i][j] > A[i][k] + A[k][j]) {
                        notExist = true;
                        break;
                    }
                    // kを経由した際の距離がA[i][j]と等しいkが存在する場合,
                    // その距離A[i][j]は答えに加算しない(他の道路の距離を足し合わせることでカウントされるため)
                    else if (A[i][j] == A[i][k] + A[k][j]) {
                        add = false;
                    }
                }
            }
            if (add) {
                ans += A[i][j];
            }
        }   
    }
    // 存在しない場合はansに-1を入れる
    if (notExist) {
        ans = -1;
    }
    out.println(ans);
    out.close();  
} 

参加記録:ABC #074

[参加記録] ABC #074

なるべく毎週参加します。

コンテストURL

abc074.contest.atcoder.jp

結果

忘れていてコンテスト開始から50分後に参加したこともありC問題をギリギリ解けず時間中に解けたのはA,Bのみ。
殘念すぎるorz
コードは以下に格納してます。
atcoder/atcoder-prg/src/abc074 at master · ueriku/atcoder · GitHub

A問題

問題

N*Nのマス目のうちAマスを白色に塗る時,塗られていないマスは何個あるか求めよ。

解答

本来の問題はもうちょっとわかりにくく書いてますが,要するにN*NからAを引いた値を求めるだけ。

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

    out.println(N * N - A);
    out.close();
}

B問題

問題

N個のボールがあり,i番目のボールはx軸の位置xiに存在する。
タイプAのロボットはx軸の位置0に,タイプBのロボットはx軸の位置Kに存在する。
ロボットを使ってボールを回収するとき,各ロボットの移動距離の総和として考えられる最小の値を求めよ。
なお,ロボットの挙動は,ボールの位置まで移動し,ボールを1個回収し,もとの位置まで戻るという挙動になる。

解答

本来の問題文はもうちょっとわかりにくく書かれていましたが,y軸は無視してOKで,
各ボールについてタイプAからとタイプBからのどちらからの方が近いか求め,その距離の2倍を足していく形になります。

for (int i = 0; i < N; i++) {
    ans += Math.min(x[i], Math.abs(K - x[i])) * 2;           
}

C問題

問題

以下の4つの操作を組み合わせて,砂糖水を作る。

  • ビーカーに水を100 * Aグラム入れる
  • ビーカーに水を100 * Bグラム入れる
  • ビーカーに砂糖をCグラム入れる
  • ビーカーに砂糖をDグラム入れる

各操作は何回行ってもいいし,一回も行わない操作があっても良い。
なるべく濃い砂糖水を作るとき,その砂糖水の質量と溶けている砂糖の質量を求めよ。
ただし,100グラムに溶ける砂糖の量はEグラムまでであり,砂糖を溶け残らせてはいけない。
また,作った砂糖水の質量がFグラムを越えてはいけない。

解答

なんかかっこいい方程式で溶けるんじゃないか?とあれこれ考えていたものの上手くいかず,
結局全通り探索すればいいやと気づいたもののギリギリで撃沈。
一個だけWAになるなーと思っていたら,作れる砂糖水の濃度の最大値が0%だったとき,答えとなる砂糖水の質量が0グラムになってしまってはダメでした。
問題文にもただの水は濃度0%の砂糖水と考えると書いており,砂糖水の質量は少なくとも100*Aグラムじゃないといけないのでした。

// 答えとなる水の量と砂糖の量,砂糖水の濃度。
// 砂糖の量は0グラムになる可能性があるが,水は0グラムだと不正解になる
// Fは100*Aよりは大きいという制限があるので,初期値として100*Aを入れておく
int water = 100 * A;
int sugar = 0;
double noudo = 0.0;
// Eから導出される,答えとなる濃度の最大値。
// これを越えてしまうと不正解。
double maxn = 100.0 * E / (100.0 + E);

// 各操作を何回行うかをi1, i2, i3, i4として全ての場合を求める
for (int i1 = 0; i1 <= F / A * 100; i1++) {
    for (int i2 = 0; i2 <= F / B * 100; i2++) {
        // この組み合わせの時点で総量がFグラムを越えていたらスキップする
        if (i1 * A * 100 + i2 * B * 100 > F) {
            break;
        }
        
        for (int i3 = 0; i3 <= F / C; i3++) {
            // この組み合わせの時点で総量がFグラムを越えていたらスキップする
            if (i1 * A * 100 + i2 * B * 100 + i3 * C > F) {
                break;
            }                    
            
            for (int i4 = 0; i4 <= F / D; i4++) {
                // i1~i4の組み合わせでの水と砂糖の量を計算する                        
                int w = 100 * A * i1 + 100 * B * i2;
                int s = C * i3 + D * i4;
                // Fを越えていたらスキップ
                if (w + s > F) {
                    break;
                }
                // 濃度を求める
                double n = 100.0 * s / (w + s);
                // 濃度がEから求められる最大値を越えておらず,
                // 今までの計算の中での最大値より大きければその答えを保持する
                if (n <= maxn && noudo < n) {
                    noudo = n;
                    water = w;
                    sugar = s;
                }
            }                       
        }
    }           
}

D問題

まったく見れてないので後日解きます。

学習記録: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));
}

学習記録:ABC #071

[学習記録] ABC #071

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

コンテストURL

abc071.contest.atcoder.jp

結果

今回もA〜Dまで解説を見ずに解けた!
ABCをやるより頑張ってARCに挑んだ方が良いか…?

A問題

問題

数直線上の位置a, b, xが与えられる。
xからaとbのどちらが近いか求め,"A"か"B"で出力せよ。

解答

絶対値を使って三項演算子で"A"か"B"を入れた。

    public void calc() {
        int x = in.nextInt();
        int a = in.nextInt();
        int b = in.nextInt();

        String ans = (Math.abs(a - x) < Math.abs(b - x))? "A" : "B"; 
        
        out.println(ans);
        out.close();
    }

B問題

問題

英小文字からなる文字列Sが与えられる。
Sに現れない英小文字について,アルファベット順で小さいものを求めよ。ただし,Sに全ての英小文字が現れる場合は"None"を出力せよ。

解答

各小文字についてフラグを管理する方法もあると思うが(そっちの方がわかりやすかった気がする),
配列をソートしてごちゃごちゃやってしまった。

    public void calc() {
        String S = in.next();
        char[] carray = S.toCharArray();
        Arrays.sort(carray);
        String alphabet = "abcdefghijklmnopqrstuvwxyz";
        int index = 0;
        String ans = "None";
        
        for (char c : alphabet.toCharArray()) {
            if (index >= carray.length || carray[index] != c) {
                ans = c + "";
                break;
            }
            while (index < carray.length && carray[index] == c) {
                index++;
            }
        }

        out.println(ans);
        out.close();
    }

C問題

問題

N個の棒について,長さAiが与えられる。
これらの棒から異なる4本を選び,長方形を作る時,最大の面積になる長方形の面積を求めよ。

解答

Mapに棒の長さとその長さの棒の本数を入れてソート。
棒を長い順に見ていって,2本以上あればそれを使う,という感じで作った。
もっとも長い棒が4本ある場合,縦も横も同じ長さの棒を使えることを最初失念していてエラーになった。
また,Aiが10^9以下と大きいので,面積を求めるときはBigDecimalなりを使わないとダメ。

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

        for (int i = 0; i < N; i++) {
            A[i] = in.nextInt();
        }
        
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        
        for (int i = 0; i < N; i++) {
            map.put(A[i], map.getOrDefault(A[i], 0) + 1);
        }
        
        Object[] mapkey = map.keySet().toArray();
        Arrays.sort(mapkey);

        int w = 0;
        int h = 0;
        
        for (int i = mapkey.length - 1; i >= 0; i--) {
            int key = (int)mapkey[i];
            int num = map.get(key);
            if (num >= 4 && w == 0) {
                w = key;
                h = key;
                break;
            }
            else if (num >= 2 && w == 0) {
                w = key;
            }
            else if (num >= 2 && w != 0) {
                h = key;
                break;
            }
        }        
        
        BigDecimal width = new BigDecimal(String.valueOf(w));
        BigDecimal height = new BigDecimal(String.valueOf(h));
        BigDecimal ans = width.multiply(height).stripTrailingZeros();
        
        out.println(ans.toPlainString());
        out.close();
    }

D問題

問題

2×Nのマス目があり,このマス目にN個のドミノを敷き詰める。
ドミノは1×2の大きさで,マス目に縦または横に配置できる。
ドミノの敷き詰め方は文字列S1, S2で与えられ,それぞれ異なる英字で以下のように示される。

xaa
xbb

このとき,左端にはドミノが縦に,その次にはドミノが横になって上下に配置されていることを示す。
これらのドミノを3色で塗り,接しているドミノは異なる色で塗り分けるようにするとき,塗り方が何通りあるかをmod 1000000007で求めよ。

解答

複雑で投げ出しそうになったが,左端からドミノを見ていくと,縦にドミノを1つ置くか,横にドミノを上下2つで並べるかの2通りしかない。
左から順に見ていき,塗り分けられるパターンが何通りあるかを掛けていけば良い。
一番左端が縦ドミノの場合は3通り,横ドミノの場合は6通りの塗り分け方が存在する。
その次からは,左隣りのドミノが縦か横かと,自分自身が縦か横かの4パターンで塗り分け方が何通りあるか異なる。

  • 縦 -> 縦:2通り
  • 縦 -> 横:2通り
  • 横 -> 縦:1通り
  • 横 -> 横:3通り

これらの値を,左端のドミノから掛け算していけばOK。
なお,答えはmod 1000000007で求める必要があるので,掛け算の度にmodを求めておく。
その際,Javaのintだと一時的にintの最大値を越えてしまう可能性があるのでlongにしておくこと。

    public void calc() {
        int N = in.nextInt();
        char[] S1 = in.next().toCharArray();
        char[] S2 = in.next().toCharArray();
        final int MOD = 1000000007;

        long ans = 0;
        // 左横のドミノが縦向きならtrueをとる
        boolean portrait = false;
        
        // S1について1文字ずつ見ていく
        for (int i = 0; i < S1.length; i++) {
            char c = S1[i];

            // ドミノが縦向きなら
            if (c == S2[i]) {
                if (i == 0) {
                    // 左端のドミノが縦向きなら最初の塗り方は3通り
                    ans = 3;
                }
                else {
                    if (portrait) {
                        // 縦 -> 縦なら*2通りする
                        ans = ((ans % MOD) * 2) % MOD;
                    }
                    else {
                        // 横 -> 縦なら1通りしかないので何もしない
                    }
                }
                // 前のドミノを縦向きにする
                portrait = true;
            }
            // ドミノが横向きなら
            else {
                if (i == 0) {
                    // 左端のドミノが横向きなら最初の塗り方は6通り
                    ans = 6;
                }               
                else {
                    if (portrait) {
                        // 縦 -> 横なら*2通りする
                        ans = ((ans % MOD) * 2) % MOD;
                    }
                    else {
                        // 横 -> 横なら*3通りする
                        ans = ((ans % MOD) * 3) % MOD;                        
                    }
                }
                // 前のドミノを横向きに設定して1つ多く進む
                portrait = false;
                i++;
            }
        }

学習記録:ABC #072

[学習記録] ABC #072

今日から時間のある日はAtCoderのBeginner Contestの過去問題をやってみることにしました。
まずはABC #072から。

コンテストURL

abc072.contest.atcoder.jp

結果

A〜Dまで解説を見ずに解けた!

A問題

問題

砂時計に入っている砂の重さX[g]と,時間t[秒]が与えられる。
1秒間に1g砂が落ちるとして,t秒後に何gの砂が砂時計の上側に残っているか求めよ。

解答

Xよりtが大きければ0を返すように,三項演算子を使ってみた。

    public void calc() {
        int X = in.nextInt();
        int t = in.nextInt();
        
        int ans = (X - t > 0)? X - t: 0;
        
        out.println(ans);
        out.close();
    }

B問題

問題

文字列sが与えられる。
前から数えて奇数文字目だけ抜き出して作った文字列を求めよ。

解答

char型の配列にして,indexが(0オリジンなので)偶数の文字だけ出力した。

    public void calc() {
        String s = in.next();
        char[] carray = s.toCharArray();
        
        for (int i = 0; i < carray.length; i = i + 2) {
            out.print(carray[i]);
        }
        out.println();
        out.close();
    }

C問題

問題

長さNと整数列a1...aNが与えられる。
各aiについて1を足す or 1を引く or 何もしないの3つの操作からどれか一つを選んで行う。
上手く操作を行い,ある整数Xの個数を最大化したとき,この個数を求めよ。

解答

結局,各aiに1を足した時と1を引いた時と何もしなかったときで,他のaiには影響がないので,
全てのaiに+1, -1, +-0したときの個数を計算して一番大きい値を出せば良い。

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

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

        // 整数XをKeyにし,その個数をValueとするMap
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        
        for (int i = 0; i < N; i++) {
            // 各aiについて何もしない, +1, -1したときの個数を入れていく
            map.put(a[i], map.getOrDefault(a[i], 0) + 1);
            map.put(a[i] + 1, map.getOrDefault(a[i] + 1, 0) + 1);
            map.put(a[i] - 1, map.getOrDefault(a[i] - 1, 0) + 1);
        }

        int ans = 0;
        
        for (Map.Entry<Integer, Integer> e: map.entrySet()) {
            // 一番大きいValue = 個数を求める
            ans = Math.max(e.getValue(), ans);
        }
        
        out.println(ans);
        out.close();
    }

D問題

問題

N個の整数からなる順列p1, ... pNが与えられる。
隣り合う二つの数を選んでスワップし,全てのpiに対して,i != piとなるようにしたい。
必要なスワップ操作の最小回数を求めよ。

解答

左端から見ていって,pi == iとなる数があったら,その右隣と入れ替えればOK。
最初は一番右端がpi == iとなっているときに入れ替えるのを忘れていた。

    public void calc() {
        int N = in.nextInt();
        int[] p = new int[N + 1];

        for (int i = 1; i <= N; i++) {
            p[i] = in.nextInt();
        }

        int ans = 0;
        
        // 右隣と入れ替える(配列の長さを越えないように注意)
        for (int i = 1; i < N; i++) {
            if (p[i] == i) {
                int tmp = p[i];
                p[i] = p[i+1];
                p[i+1] = tmp;
                ans++;
            }
        }
        
        // 一番右端の数字を入れ替える場合
        if (p[N] == N) {
            ans++;
        }
        
        out.println(ans);
        out.close();
    } 

参加記録:ABC #073

[参加記録] ABC #073

コンテストURL

abc073.contest.atcoder.jp

結果

A,B,C解答したもののD問題はできず。

プログラム

A問題

二桁の整数Nに,9が含まれたらYesを,そうでなければNoを返す。

色々方法はあると思いますが,文字列にして9が含まれているかを検索しました。

    public void calc() {
        int N = in.nextInt();
        String ans = "No";
        

        if (Integer.toString(N).contains("9")) {
            ans = "Yes";
        }
        
        out.println(ans);
        out.close();
    }
B問題

劇場にN組の団体が来て,l[i]〜r[i]までの連番の席が埋まっている。劇場には何人座っているか求めよ。

愚直にr[i] - l[i] + 1の和を求めました。
解説ではr[i]の和からl[i]の和を引いて,Nを足せば良いとやっていました。なるほどー。

    public void calc() {
        int N = in.nextInt();
        int[] l = new int[N];
        int[] r = new int[N];
        int sum = 0;

        for (int i = 0; i < N; i++) {
            l[i] = in.nextInt();
            r[i] = in.nextInt();
            sum += r[i] - l[i] + 1;
        }

        out.println(sum);
        out.close();
    }
C問題

N個の数字が順番に与えられ,最初は何も書いていない紙に書いていく。
与えられた数字が紙に書いてあれば紙から数字を消し,なければその数字を紙に追加していく。
最後に紙にかかれている数字がいくつあるか求めよ。

最初は愚直にListに入れて追加する度に検索していましたが,時間オーバー。
HashMapのことを思い出してそちらに変えました。
与えられた数字と,今まで数字が与えられた個数をMapに入れていき,最後に個数が奇数の数字を数えればOK。

    public void calc() {
        int N = in.nextInt();
        HashMap<Integer, Integer> A = new HashMap<Integer, Integer>();

        for (int i = 0; i < N; i++) {
            int a = in.nextInt();
            // 与えられた数字をMapに追加し,値に今まで出てきた個数を入れる
            A.put(a, A.getOrDefault(a, 0) + 1);
        }
        
        int ans = 0;
        
        for (Map.Entry<Integer, Integer> e: A.entrySet()) {
            // Valueが奇数のKeyの数を数える
            if (e.getValue() % 2 == 1) {
                ans++;
            }
        }
        
        out.println(ans);
        out.close();
    }
D問題

N個の町があり,M本の双方向移動な道で結ばれている。R個の町r1,r2,...rRを訪れるとき,その最短移動距離を求めよ。
なお,M本の道については,それぞれ町Aiから町Biを結んでおり,距離Ciであることがわかっている。

最短距離と聞いてワーシャルフロイド法とかあったな,と思い出して書いてみた。
各町間の最短距離はわかったものの,後は町の訪れる順番を再帰で書けずに時間終了。

    int N,M,R;
    int[] r,A,B,C;
    boolean[] done;
    int[][] dist;
    int ans;
    
    public void calc() {
        N = in.nextInt();
        M = in.nextInt();
        R = in.nextInt();
        r = new int[R];
        A = new int[M];
        B = new int[M];
        C = new int[M];

        // rの表す町番号は配列に入れる都合上-1しておく
        for (int i = 0; i < R; i++) {
            r[i] = in.nextInt() - 1;
        }

        // 先程のrと同様,AとBは-1しておく
        for (int i = 0; i < M; i++) {
            A[i] = in.nextInt() - 1;
            B[i] = in.nextInt() - 1;
            C[i] = in.nextInt();
        }
        
        // ワーシャルフロイド法で全頂点間の最短距離を求める
        dist = new int[N][N];        
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                // ここで初期値を適切な値にしないと後々の計算でおかしくなるので注意
                // 大きすぎると道のない町と町の間での距離計算で桁があふれてしまう
                // 小さすぎると道がないのにも関わらず町から町へと移動してしまう可能性がある
                dist[i][j] = 99999999;
            }
            dist[i][i] = 0;  
        }        
        for (int i = 0; i < M; i++) {
            // 道のある町間での距離を入れる
            // 町と町の間に複数の道がある場合があるため,一番短い距離の道のみ考慮する
            dist[A[i]][B[i]] = Math.min(C[i], dist[A[i]][B[i]]);
            dist[B[i]][A[i]] = dist[A[i]][B[i]];
        }              
        for (int k = 0; k < N; k++) {
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }

        // ここの探索が書けなかった
        
        out.println(ans);
        out.close();
    }

再帰の書き方を完璧に忘れていましたが,解説を読んで以下のような感じで深さ優先探索ができた。

    /**
     * 深さ優先探索を行う
     * @param curNum 現在訪れた町の数
     * @param curTown 今訪れている町
     * @param d 今まで歩いてきた距離
     */
    private void dfs(int curNum, int curTown, int d) {
        // out.println("curNum: " + curNum + " curTown: " + curTown + " d: " + d);
        // 最後の町にたどり着いたら
        if (curNum == R) {
            // 答えを更新
            if (ans > d) {
                ans = d;
            }
            return;
        }
        
        // まだ訪れていない町を訪問
        for (int i = 0; i < R; i++) {
            // 訪れていなければ
            if (!done[i]) {
                // 訪れたことにする
                done[i] = true;
                
                // これが訪れた最初の町なら,距離dは0で次に進む
                if (curTown == -1) {                    
                    dfs(curNum+1, i, 0);
                }
                // 最初の町でなければ,今までの距離dと,次の町への距離を加える
                // 次の町への距離は,現在の町r[curTown]から,次の町r[i]への最短距離distになる
                else {
                    dfs(curNum+1, i, d+dist[r[curTown]][r[i]]);                
                }
                
                done[i] = false;
            }
        }   
    }

感想

業務などで忙しく,ABC #016以来の1年ぶりの参加でした。
ぼちぼち復活していきたいです。
買っただけで積んでるプロコン関係の本もあるので読み直そう・・・

学習記録:ゼロから作るDeepLearning

3章:ニューラルネットワーク(続き)

出力層の設計

ソフトマックス関数

機械学習の問題は,分類問題(データがどのクラスに属するか)と回帰問題(ある入力データから数値の予測を行う)に大別できる。
一般的に,回帰問題では恒等関数を,分類問題ではソフトマックス関数を用いる。

前述したとおり,恒等関数は入力をそのまま出力する。一方,ソフトマックス関数は次の式で表される。
yk = exp(ak) / ∑exp(ai)

ソフトマックス関数の実装は以下のとおり。

import numpy as np

def softmax(a):
    exp_a = np.exp(a)
    sum_exp_a = np.sum(exp_a)
    return exp_a / sum_exp_a

a = np.array([0.3,2.9,4.0])
print(softmax(a))

この実装には欠陥があり,それは指数関数の計算結果が非常に大きな値になってしまう可能性がある点である。
これによる数値のオーバーフローを防ぐため,分子・分母の指数関数expの中で,定数C(一般には入力信号の最大値)をマイナスするのが一般的である。

def softmax(a):
    c = np.max(a)
    exp_a = np.exp(a-c)   # ここでCを引いておく
    sum_exp_a = np.sum(exp_a)
    return exp_a / sum_exp_a     # 結果は変わらない

さて,このソフトマックス関数には,出力が0から1.0の間の実数になり,総和が1になるという特徴がある。

a = np.array([0.3,2.9,4.0])
print(softmax(a))
print(np.sum(softmax(a)))
% python softmax.py
[ 0.01821127  0.24519181  0.73659691]
1.0

この性質から,ソフトマックス関数の出力を確率として解釈することができる。
例えば上記の例なら,y[2]の確率が73%で一番高いので,y[2]のクラスである,といった判断ができることになる。
ただし,ソフトマックス関数の適用前後における値の大小関係は変わらない(上の例だと適用前はa[2]が一番大きく,適用後も2番目の要素であるy[2]が一番大きい)ので,一般的には出力層のソフトマックス関数は省略することが多い(指数関数の計算にはそれなりの計算資源を食うため)。

手書き数字認識

機械学習の手順は学習と推論の2フェーズに分けられる。
学習フェーズでモデルを学習し,推論フェーズでモデルを使って未知のデータに対して推論を行う。
ここでは,学習済のパラメータを使って,ニューラルネットワークの推論処理を実装してみる。

MNISTデータ・セット

MNISTは機会学習の分野で有名なデータセットで,0から9の数字画像(28x28ピクセル)で構成され,訓練画像とテスト画像が用意されている。
MNIST画像を表示する実装は以下になる。

import sys, os
sys.path.append(os.pardir)
import numpy as np
from dataset.mnist import load_mnist
from PIL import Image

def img_show(img):
    pil_img = Image.fromarray(np.uint8(img))
    pil_img.show()

(x_train, t_train), (x_test, t_test) = \
    load_mnist(flatten=True, normalize=False)

img = x_train[0]
img = img.reshape(28,28)
img_show(img)

本書のサンプルプログラム中のdataset/mnist.pyにあるload_mnist関数により,MNISTデータのダウンロードから画像データのNumPy配列への変換を一気に行うことができる。
画像の表示にはPILモジュールを使っており,訓練画像の1枚目(「5」の画像)を表示している。
なお,load_mnist関数でflatten=Trueを指定していると,画像がNumPy配列に1次元で格納されるため,もとの28x28のサイズにreshapeしてから表示をする必要がある。

推論処理

このMNISTデータセットに対して推論処理を行うニューラルネットワークを実装する。
入力層は784個(画像サイズが28x28のため),出力層は10個(0〜9)のニューロンで構成する。
隠れ層は二つとし,それぞれ50個と100個のニューロンを持つものとする(ここの個数は任意に設定できる)。

# MNISTデータを取得する                                                              
def get_data():
    # flatten: 入力画像を1次元に配列にする(Falseなら1x28x28の3次元配列)              
    # normalize: 入力画像を0〜1の値に正規化する(Falseなら0〜255)                     
    # one_hot_label: 正解のラベルだけ1の配列にする(Falseなら2,7など正解の値が入る)   
    (x_train, t_train), (x_test, t_test) = \
         load_mnist(flatten=True, normalize=True, one_hot_label=False)
    return x_test, t_test

# 学習済の重みパラメータ(sample_weight.pkl)を使ってネットワークを初期化する          
# このファイルには重みとバイアスがディクショナリ型の変数として保存されている         
def init_network():
    with open("sample_weight.pkl", "rb") as f:
        # pickle(実行中のオブジェクトをファイルとして保存する機能)を使う             
        network = pickle.load(f)

    return network

def predict(network, x):
    W1, W2, W3 = network['W1'], network['W2'], network['W3']
    b1, b2, b3 = network['b1'], network['b2'], network['b3']

    a1 = np.dot(x, W1) + b1
    z1 = sigmoid(a1)
    a2 = np.dot(z1, W2) + b2
    z2 = sigmoid(a2)
    a3 = np.dot(z2, W3) + b3
    y = softmax(a3)

    return y

x, t = get_data()
network = init_network()

accuracy_cnt = 0 # 正解数                                                            
for i in range(len(x)):
    # 予測する                                                                       
    y = predict(network, x[i])
    # 配列yの中で最大の(最も確率の高い)インデックスを取得                            
    p = np.argmax(y)
    # pが正解(t[i])と等しければ正解数を増やす                                        
    if p == t[i]:
        accuracy_cnt += 1

# 正解率を精度として出力                                                             
print("Accuracy: " + str(float(accuracy_cnt) / len(x)))
% python neuralnet_mnist.py
Accuracy: 0.9352

この結果は,93.52%正しく分類できた,ということを表す。
今後ニューラルネットワークの構造や学習方法を工夫することで,99%以上の精度を目指す。

学習記録:ゼロから作るDeepLearning

3章:ニューラルネットワーク(続き)

多次元配列の計算

まずはNumPyによる多次元配列の計算について学ぶ。
2次元配列=行列の内積を計算してみる。内積の計算にはdot関数を使う。

>>> A = np.array([[1,2],[3,4]])
>>> B = np.array([[5,6],[7,8]])
>>> np.dot(A,B)
array([[19, 22],
       [43, 50]])

なお,当然内積の計算ができるように,行列Aの1次元目と行列Bの0次元目の次元数は一致している必要がある。
では,続いてNumPy行列を使ってニューラルネットワークの実装を行う。
今回はバイアスと活性化関数は省略し,重みだけあるものとする。

>>> X = np.array([1,2])
>>> W = np.array([[1,3,5],[2,4,6]])
>>> Y = np.dot(X,W)
>>> print(Y)
[ 5 11 17]

この例では,入力x1とx2があり,出力はy1,y2,y3がある。
x1からy1〜3への重みがw1で,x2からy1〜3への重みがw2で表されている。

3層ニューラルネットワークへの実装

それでは実践的なニューラルネットワークの実装を行う。
ここで実装するのは3層のニューラルネットワークで,入力層は2つ,続いて3つ -> 2つの隠れ層があり,出力層は2つのニューロンから構成される。

入力層を1 x 2の行列X,重みを2 x 3の行列W,バイアスを1 x 3の行列Bとして表すと,
第1層(1つ目の隠れ層)の1 x 3行列Aは次のように表される。

import numpy as np

X = np.array([1.0, 0.5])
W1 = np.array([[0.1,0.3,0.5],[0.2,0.4,0.6]])
B1 = np.array([0.1,0.2,0.3])

A1 = np.dot(X, W1) + B1
print(A1)
% python 3layer_nn.py
[ 0.3  0.7  1.1]

続いては第1層の活性化関数を見ていく。
隠れ層での重み付き和aに対し,h()で表される活性化関数により,出力zが得られる。
ここでは活性化関数としてシグモイド関数を使うことにし,出力zはそのまま次の第2層への入力になるので,
第1層目から2層目への実装は次のようになる。

import matplotlib.pylab as plt

def sigmoid(x):
    return 1 / (1 + np.exp(-x))

Z1 = sigmoid(A1)
W2 = np.array([[0.1,0.4],[0.2,0.5],[0.3,0.6]])
B2 = np.array([0.1,0.2])

A2 = np.dot(Z1, W2) + B2
print(A2)
% python 3layer_nn.py
[ 0.3  0.7  1.1]
[ 0.51615984  1.21402696]

ここまでは先程の実装とほぼ同じで,このA2が第2層(2つ目の隠れ層)への入力になる。
ここでの第2層での活性化関数も同様にシグモイド関数を使うと,Z2はsigmoid(A2)となり,これが最後の出力層への入力となるところも同じである。

出力層の実装もここまでとほぼおなじだが,最後の活性化関数だけが異なる。

def identity_function(x):
    return x

Z2 = sigmoid(A2)
W3 = np.array([[0.1,0.3],[0.2,0.4]])
B3 = np.array([0.1,0.2])

A3 = np.dot(Z2, W3) + B3
Y = identity_function(A3)

print("Y: ")
print(Y)
% python 3layer_nn.py
[ 0.3  0.7  1.1]
[ 0.51615984  1.21402696]
Y: 
[ 0.31682708  0.69627909]

出力層の活性化関数として,identity_function()を使用している。
上の例では,入力をそのまま出力する恒等関数を使っている。出力層の活性化関数はσ()で表し,中間層のh()とは異なることを示す。
なお,σ()は解く問題の性質に応じて決める。回帰問題では恒等関数,2クラス分類問題ではシグモイド関数…といった決め方になる。