taiPyのお悩み解決ブログ

日々の発見をまとめます！

Javaの解答例：学習記録：A37 - Travel 2 , 競技プログラミングの鉄則

はじめに

自分用の備忘録。

ポイント

部分に分解して、答えへの寄与度を求める。イメージは、モテる男性の特徴を知性、ユーモア、外見、年収に分解して、モテに対してどれくらいモテに重要なのかを求めるのと近いね。

問題

A37 - Travel 2 , https://atcoder.jp/contests/tessoku-book/tasks/tessoku_book_ak

ALGO 市には N 個の駅と M 個のバス停があり、下図のように道路で結ばれています。 すべての組 (i,j) に対して「駅 i からバス停 j までの所要時間」を足した値はいくつですか？

解答例

import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // 入力
        int N = sc.nextInt();
        int M = sc.nextInt();
        long B = sc.nextLong();
        long[] A = new long[N + 1];
        long[] C = new long[M + 1];
        for (int i = 1; i <= N; i++) A[i] = sc.nextLong();
        for (int j = 1; j <= M; j++) C[j] = sc.nextLong();

        // 答えの計算
        long Answer = 0;
        for (int i = 1; i <= N; i++) Answer += A[i] * M;
        Answer += B * N * M;
        for (int j = 1; j <= M; j++) Answer += C[j] * N;

        // 出力
        System.out.println(Answer);
    }
};

自分が書いた間違えたコード

マジでどこが間違っているかわからん。将来の私よ、頼んだ。

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // インプットを格納していきまーす。
        int N = sc.nextInt();
        int M = sc.nextInt();
        int B = sc.nextInt();

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

        // ここ少し忘れていて、ぜんぜん応え合わないじゃん、ってなって焦った。
        for (int i = 0; i < A.length; i++) {
            A[i] = sc.nextInt();
        }

        for (int i = 0; i < C.length; i++) {
            C[i] = sc.nextInt();
        }

        // トリマBの時間を求めるで。
        /* BはNとMの組み合わせ分あるから、次の式で求める。
         * 理由：どこから出発しようとも絶対に通るからね。
         */
        int BTime = B * N * M;

        // Aの時間、（図で言うなら左）の時間を求めるで。
        /* 左の時間全部足して、右の数かけてやる感じ。
         * 中学校で学んだ分配法則使うで。
         */
        int ATime = 0;
        for (int i = 0; i < N; i++) {
            ATime += A[i];
        }
        // System.out.println(ATime);
        // 上記のコメントは、「え？答え合わないじゃん、どこ間違ってるの？」って軽くデバックした時の名残
        ATime = ATime * M;

        int CTime = 0;
        for (int i = 0; i < M; i++) {
            CTime += C[i];
        }
        // System.out.println(CTime);
        // 上に同じ。
        CTime = CTime * N;

        // じゃあ、全部足して、出力するで。
        System.out.println(ATime + BTime + CTime);

        // ほな、さいなら
        sc.close();
    }
}

参考文献