新人SEの学習記録

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

参加記録: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年ぶりの参加でした。
ぼちぼち復活していきたいです。
買っただけで積んでるプロコン関係の本もあるので読み直そう・・・