新人SEの学習記録

14年度入社SEの学習記録用に始めたブログです。気づけば社会人3年目に突入。

参加記録:AtCoder Regular Contest 035

[参加記録] AtCoder Regular Contest 035

コンテストURL


Welcome to AtCoder Regular Contest 035 - AtCoder Regular Contest 035 | AtCoder

結果

  • A, B問題の200点
    • Cは何故かWAが取れず・・・と思ったらintをlongにしたらACだったorz

プログラム

A問題
  • おなじみ回文判定。入力文字列Sが回文ならYES, 違うならNOを出力
    • ただし文字*には任意の文字を入れてよい。
  • 解法
    • 文字を1文字目から見ていき、自分と反対側の文字が異なる && どちらも*でない場合回文ではない
public class Main {
    FastScanner in = new FastScanner(System.in);
    PrintWriter out = new PrintWriter(System.out);
 
    public static void main(String[] args) {
        new Main().calc();
    }
    
    public void calc() {
        char[] s = in.next().toCharArray();
        int len = s.length;
        boolean flag = true;    
        
        for (int i = 0; i < len / 2; i++) {
            if (s[i] == s[len - i - 1] || s[i] == '*' || s[len - i - 1] == '*') {
                
            }
            else {
                flag = false;
                break;
            }
        }
 
        if (flag) {
            out.println("YES");
        }
        else {
            out.println("NO");
        }
        
        out.close();
    }
}
B問題
  • N個の問題とそれぞれの問題を解くのに掛かる時間Tiが与えられるとき、以下の2つを出力する(問題は自由な順番で解いてよい)
    • 1)最小のコンテストペナルティ(各問題を解き終わったときのコンテスト開始からの時間の和)
    • 2)最小のコンテストペナルティで問題を解く順番の組み合わせは何通りあるか(1000000007で割った余り)
  • 解法
    • 時間の短い方から解けばよいので時間の入った配列をソートして足していく
    • 組み合わせの方は同じ時間の問題の階乗を掛け合わせていけばOK
package y150307.b;

public class Main {
    FastScanner in = new FastScanner(System.in);
    PrintWriter out = new PrintWriter(System.out);

    public static void main(String[] args) {
        new Main().calc();
    }
    
    public void calc() {
        int N = in.nextInt();

        int[] T = new int[N];

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

        // コンテストペナルティ
        long contPena = 0;
        // 現在の時間
        long curTime = 0;
        // 解放の数
        long numOfSol = 1;
        // 前に見た問題の解くのに掛かる時間(Ti)
        int beforeTi = -1;
        // 解くのに掛かる時間が同じ問題が何問続いているか
        int curNum = 0;
        
        for (int i = 0; i < N; i++) {
            curTime += T[i];
            contPena += curTime;
            
            if (T[i] == beforeTi) {
                curNum++;
            }
            else {
                curNum = 1;
                beforeTi = T[i];
            }
            
            numOfSol = numOfSol * curNum % 1000000007;
        }

        out.println(contPena);
        out.println(numOfSol);
        out.close();
    }
}
C問題
  • ある国にはN個の都市とM本の道路がある
    • 各道路は都市AiとBiを結び、距離Ciを持つ
    • この国に、都市XiとYiを結び距離Ziを持つK本の道路を建設していく
    • 道路を建設するたびに、全都市間の最短経路長の総和Sを出力する
  • 解法
    • 各都市の距離dist[i][j]をワーシャルフロイドで求める
    • 道路を追加するごとに、追加した道路に関係する距離dist[i][j]を更新していく
    • 追加した道路に関係するdist[i][j]は以下の方法で求める
    • dist[i][j] = dist[i][追加した道路が結ぶ都市1] + dist[追加した道路が結ぶ都市2][j] + 追加した道路の距離
    • 総和Sをlongにするだけで通ったorz Cにしては簡単なはずの問題を落としたのは痛いので今後気をつけよう。。。
public class Main {
    FastScanner in = new FastScanner(System.in);
    PrintWriter out = new PrintWriter(System.out);

    public static void main(String[] args) {
        new Main().calc();
    }

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

        int[] A = new int[M];
        int[] B = new int[M];
        int[] C = new int[M];

        for (int i = 0; i < M; i++) {
            A[i] = in.nextInt() - 1;
            B[i] = in.nextInt() - 1;
            C[i] = in.nextInt();
        }

        int K = in.nextInt();

        int[] X = new int[K];
        int[] Y = new int[K];
        int[] Z = new int[K];

        for (int i = 0; i < K; i++) {
            X[i] = in.nextInt() - 1;
            Y[i] = in.nextInt() - 1;
            Z[i] = in.nextInt();
        }

        // 都市iからjまでの距離をdist[i][j]とする
        int[][] dist = new int[N][N];
        int MAX = 999999;

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                dist[i][j] = MAX;
            }
            dist[i][i] = 0;
        }

        for (int i = 0; i < M; i++) {
            dist[A[i]][B[i]] = C[i];
            dist[B[i]][A[i]] = C[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]);
                }
            }
        }

        long s = 0;
        for (int i = 0; i < N - 1; i++) {
            for (int j = i + 1; j < N; j++) {
                s += dist[i][j];
            }
        }

        for (int i = 0; i < K; i++) {
            if (dist[X[i]][Y[i]] <= Z[i]) {
                out.println(s);
                continue;
            }

            dist[X[i]][Y[i]] = Z[i];
            dist[Y[i]][X[i]] = Z[i];

            int[] check = {X[i], Y[i]};

            for (int l = 0; l < N; l++) {
                for (int m = 0; m < N; m++) {
                    dist[l][m] = Math.min(dist[l][m], dist[l][check[0]]
                            + Z[i] + dist[check[1]][m]);
                    dist[l][m] = Math.min(dist[l][m], dist[l][check[1]]
                            + Z[i] + dist[check[0]][m]);
                }
            }

            s = 0;
            
            for (int l = 0; l < N - 1; l++) {
                for (int m = l + 1; m < N; m++) {
                    s += dist[l][m];
                }
            }

            out.println(s);
        }

        out.close();
    }
}