taiPyのお悩み解決ブログ

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

Javaの解答例：学習記録：C - Colorful Beans , トヨタ自動車プログラミングコンテスト2024#4（AtCoder Beginner Contest 348）

はじめに

この問題のポイント

  • 愚直にやると、メモリの制限と制限時間に間に合わなくなるかも。
  • 配列を用意する時にもメモリの要領を確保しないといけないからね。小さいなら問題ないけど、大きいならちょっと。キャリーケースに分厚いニットを入れるとほかの者がいれられないのに似ている。
  • だから、連想配列を使うよ。
  • 最小値の最大化は二分探索を使うらしい。
  • 解法が分かっていただけに悔しかった問題。でも実装できないんですよねー。
  • これをきっかけに連想配列の使い方をマスターしよう！

目次

問題と解説

問題 atcoder.jp

解説 atcoder.jp

YouTube youtu.be

解答例

公式の解答を私なりに、Javaに変換

import java.util.*;

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

        Map<Integer, Integer> mininumTaste = new HashMap<Integer, Integer>();


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

        for (int i = 0; i < N; i++) {
            if (mininumTaste.containsKey(c[i])) {
                mininumTaste.put(c[i], Math.min(mininumTaste.get(c[i]), a[i]));
            } else {
                mininumTaste.put(c[i], a[i]);
            }
        }

        int ans = -1;
        for (int i : mininumTaste.keySet()) {
            ans = Math.max(ans, mininumTaste.get(i));
        }

        System.out.println(ans);

        sc.close();
    }
}

ほかの解答例

なるほど、解法の部分をsolve()としてmain()の外に出しているのですね。参考になります。

atcoder.jp

import java.util.*;
import java.io.*;

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

        int[] a = new int[n];
        int[] c = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
            c[i] = sc.nextInt();
        }

        System.out.println(solve(n, a, c));
    }

    static String solve(int n, int[] a, int[] c) {
        HashMap<Integer, Integer> cmin = new HashMap<>();
        for(int i=0; i<n; i++) {
            cmin.put(c[i], Math.min(a[i], cmin.getOrDefault(c[i], Integer.MAX_VALUE)));
        }
        int result = 0;
        for(Integer ai: cmin.values()) {
            result = Math.max(result, ai);
        }

        return String.valueOf(result).trim();
    }
}

所感

ほかの人のコードを見るの面白いですね！ なんか、こう、めちゃくちゃ長いのから、普通にきれいなものまでたくさんありますね。あと、テクニック満載なものもあって、見ていて面白い。

Javaの解答例：B - Farthest Point, トヨタ自動車プログラミングコンテスト2024#4（AtCoder Beginner Contest 348）

はじめに

自分用の備忘録。

メモ、ポイント

  • 問題文を読むこと。違う距離の出し方をしていて、それが要因で答えが違ったんですよね。
  • マイクロブレイク。詰まった時ほど休んでいこう。
  • 普通に、寝坊。30か40分遅れての参加で焦りが。。もう少し前に仮眠をとるか。

目次

問題と公式の解説

問題 atcoder.jp

解説 atcoder.jp

自作の解答例

コメントアウトしている、printはあれです。デバック用です。

import java.util.*;

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

        // input
        int N = sc.nextInt();
        int[] X = new int[N];
        int[] Y = new int[N];
        for (int i = 0; i < N; i++) {
            X[i] = sc.nextInt();
            Y[i] = sc.nextInt();
        }
        // process

        for (int i = 0; i < N; i++) {
            // distance
            int ans = 0;
            int tempX = X[i];
            int tempY = Y[i];
            double tempDistance = 0;
            // max?
            for (int j = 0; j < N; j++) {
                // d = Math.sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1))
                double distance =  Math.sqrt((tempX - X[j]) * (tempX - X[j]) + (tempY - Y[j]) * (tempY - Y[j]));
                // int distance = Math.abs(tempX - X[j]) + Math.abs(tempY - Y[j]);
                // System.out.println("tempDistance" + tempDistance);
                // System.out.println("distance" + distance);
                // System.out.println(j);
                if (distance > tempDistance) {
                    tempDistance = distance;
                    ans = j + 1;
                }
            }
            // output
            System.out.println(ans);

        }
        
        sc.close();
    }
}

公式をJavaに変換

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] x = new int[n];
        int[] y = new int[n];
        for (int i = 0; i < n; ++i) {
            x[i] = scanner.nextInt();
            y[i] = scanner.nextInt();
        }

        for (int i = 0; i < n; ++i) {
            int max_dist = 0; //距離の2乗の最大値
            int idx = -1;     //距離が最大になる点の番号(0-indexed)
            for (int j = 0; j < n; ++j) {
                int dist = (x[i] - x[j]) * (x[i] - x[j]) +
                           (y[i] - y[j]) * (y[i] - y[j]); // 点i,jの距離の2乗
                if (max_dist < dist) {
                    // 距離の最大値が更新された場合
                    max_dist = dist;
                    idx = j;
                }
            }
            System.out.println(idx + 1);
        }
    }
}

参考文献

todo 必要あれば、追加。

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();
    }
}

参考文献

Javaの解答例と記録：A54, Map, 競技プログラミングの鉄則

はじめに

自分用の備忘録。

目次

問題

atcoder.jp

問題のポイント

  • 連想配列を使うこと
  • 入力値には2つのタイプがあるので、それを処理する。例えば　今回の場合は、１と２の場合がある。１．1 tanaka 49　２．2 tanaka

連想配列を試すのにいい教材だなって思いました。基礎が固まった気がします。

今回の問題のイメージ。インプットを配列に格納するときのイメージ。

自分がミスしたところ 2024年4月9日

今回は、配列に格納せずにそのままプログラムを書いた。（解答例その2を参照）。一回、if分の前でしっかりと受け止めてやらないといけない。愛で包み込む。

文法的な話をします。1つ目のifの後に２つ目のifに行くわけですが、まあ、そうすると入力値受けすぎ、あれ、おれ、こいつと型合わないんですけど、みたいな事態が起こる。下記に誤った例を書いておきます。

誤った例

            if (sc.nextInt() == 1) {
                map.put(sc.next(), sc.nextInt());
            }

            if (sc.nextInt() == 2) {
                int temp = map.get(sc.next());
                System.out.println(temp);
            }
        }

正しい方

// ここで入力値を受け取っちゃいます
            int intTemp = sc.nextInt();

// 受け取った値をもとに判別します！
            if (intTemp == 1) {
                map.put(sc.next(), sc.nextInt());
            }

            if (intTemp == 2) {
                int temp = map.get(sc.next());
                System.out.println(temp);
            }

Query Type : 1, 1, 2
Query x       : tanaka, suzuki, tanaka
Query y       : 49, 50, (Query Typeが2だから何もないよ。出力せよ)

問題の解答例

import java.util.*;

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

        // インプットを処理します。
        int Q = sc.nextInt();
        // 入力を入れる配列を用意！今回はだいたいQくらいの箱を用意してあげるとよき
        int[] queryType = new int[Q + 1];
        String[] x = new String[Q + 1];
        int[] y = new int[Q + 1];
        // じゃあ、今からインプットされた情報を配列に入れていくよー
        for (int i = 1; i <= Q; i++) {
            // 今回クエリのタイプが２つあったよね。それを識別するのに大切
            queryType[i] = sc.nextInt();
            // じゃあ、クエリのタイプが1の場合は、ｘとｙに入れよ！
            if (queryType[i] == 1) {
                x[i] = sc.next();
                y[i] = sc.nextInt();
            }
            // じゃあ、クエリのタイプが2の場合は、こう入れよ！
            if (queryType[i] == 2) {
                x[i] = sc.next();
            }
        }

        // ここで連想配列を用意
        Map<String, Integer> scoreMap = new HashMap<String, Integer>();
        // 処理を進めていくよ
        for (int i = 1; i <= Q; i++) {
            // もしクエリのタイプが1の場合は、値を格納せよ。putだ！
            if (queryType[i] == 1) {
                // KeyとValueで指定してあげるよ。田中君の点数は100点満点、的なイメージ。
                scoreMap.put(x[i], y[i]);
            }

            // もし、タイプが2なら出力せよ！
            if (queryType[i] == 2) {
                System.out.println(scoreMap.get(x[i]));
            }
        }

        sc.close();
    }
}

解答例その2

import java.util.*;

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

        Map<String, Integer> map = new HashMap<String, Integer>();

        int q = sc.nextInt();

        for (int i = 0; i < q; i++) {
            int intTemp = sc.nextInt();

            if (intTemp == 1) {
                map.put(sc.next(), sc.nextInt());
            }

            if (intTemp == 2) {
                int temp = map.get(sc.next());
                System.out.println(temp);
            }
        }


        sc.close();
        }

}

参考文献

https://atcoder.jp/contests/tessoku-book/tasks/tessoku_book_bb

Javaの回答例：C - One Time Swap , モノグサプログラミングコンテスト2024（AtCoder Beginner Contest 345）

はじめに

自分用の備忘録。今回のC問題は難しかったな。

目次

memo

考察テクニックの一つとして例から考える方法がある。具体的には、例から手を動かしながら答えを算出することで、問題の法則性が見え、その結果、工夫して解くことができる。

あとは、普通にSetやHashSetにいれようとすると、制限時間オーバーしちゃうよ。ダカラ工夫必要。はじめに実装したとき、私も制限時間オーバーしちゃったので、アレ？ってなっちゃいましたね。

解法は　（ここに自分が勉強したことを書いてね！）

入れ換えて同じ文字になる場合は、考慮ない。ダカラ、同じ文字になる場合と同じ文字にならない場合とで分けて考える。

問題と解説

問題

atcoder.jp

公式解説

atcoder.jp

ユーザー解説

atcoder.jp

こんな方法があるんだって、目から鱗でした。

Youtube解説

www.youtube.com

解答例

import java.util.Scanner;
import java.util.HashMap;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String S = scanner.nextLine();
        int N = S.length();
        HashMap<Character, Integer> count = new HashMap<>();

        for (char c : S.toCharArray()) {
            count.put(c, count.getOrDefault(c, 0) + 1);
        }

        long ans = (long) N * N;
        for (int x : count.values()) {
            ans -= (long) x * x;
        }
        ans /= 2;

        if (count.values().stream().anyMatch(x -> x > 1)) {
            ans++;
        }

        System.out.println(ans);
    }
}

【随時更新】Visual Studio のお役立ちショートカット集

はじめに

自分用の備忘録。

ショートカット一覧

「Shift+Alt+a」・・・複数行コメント、コメントブロック、複数行にわたる説明を書きたいなー

Java

/*
* これはブロックコメントです。
* 複数行にわたる説明を書くことができます。
*/

Python

"""
これはブロックコメントです。
複数行にわたる説明を書くことができます。
"""

こういう使い方もできます

HashSet<Long> /* set = new HashS */et<Long>();
// 行の中にコメントを挿入！

「Ctrl + X」・・・切り取り。行ごと切り取ってくれます。なので、いちいち、マウス使って範囲を選択して、切り取ってというマウス使って範囲を選択という行為をしなくても大丈夫。

Javaの解答例：C - A+B+C, トヨタ自動車プログラミングコンテスト2024#3（AtCoder Beginner Contest 344）

はじめに

問題文と公式の解答

atcoder.jp

atcoder.jp

メモ

事前に計算しておくことがコツ。制約から問題の性質を考えることもできるよねー。今思うのはとりあえず色々な道具知っていき、これは？あれ試せるかな？って一つずつ試して行ったらどうにかなる気がする。

ステップ

  1. まずは入力値を受け取る
  2. 事前に計算した後に(3重for)、ぶちこみたい箱を用意する
  3. では実際に計算して計算結果をここにぶち込む
  4. その箱の中にエックスはあるかいと問う。

解答例　Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        long[] A = new long[N];
        for (int i = 0; i < A.length; i++) {
            A[i] = sc.nextInt();
        }

        int M = sc.nextInt();
        long[] B = new long[M];
        for (int i = 0; i < M; i++) {
            B[i] = sc.nextInt();
        }

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

        int Q = sc.nextInt();
        long[] X = new long[Q];
        for (int i = 0; i < Q; i++) {
            X[i] = sc.nextInt();
        }


        // pre
        HashSet<Long> pre = new HashSet<Long>();

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                for (int j2 = 0; j2 < L; j2++) {
                    long temp = A[i] + B[j] + C[j2];
                    pre.add(temp);
                }
            }
        }


        for (int i = 0; i < Q; i++) {
            // System.out.println(i);

            // process
            for (int j = 0; j < pre.size(); j++) {
                if (pre.contains(X[i])) {
                    System.out.println("Yes");
                    break;
                } else {
                    System.out.println("No");
                    break;
                }
            }
        }

        
    }
}

解答例　２　公式をJaavに変換

memo

回答零2のほうで面白いなと思ったポイントは、ストリング型に格納してからスプリットを使って文字を数字に直してるところ！考え方は上のやつと一緒。

#include <iostream>
#include <vector>
#include <bitset>

int main() {
    using namespace std;

    unsigned N, M, L;
    cin >> N;
    vector<unsigned> A(N);
    for (auto &&a : A)
        cin >> a;
    cin >> M;
    vector<unsigned> B(M);
    for (auto &&b : B)
        cin >> b;
    cin >> L;
    vector<unsigned> C(L);
    for (auto &&c : C)
        cin >> c;

    // 連続する 3e8 + 1 bit を用意して
    // A[i] + B[j] + C[k] として出現する値かどうかを管理
    bitset<300000001> possible;
    for (const auto a : A)
        for (const auto b : B)
            for (const auto c : C)
                possible[a + b + c] = true;

    unsigned Q;
    cin >> Q;
    for (unsigned i = 0, x; i < Q; ++i) {
        cin >> x;
        cout << (possible[x] ? "Yes" : "No") << endl;
    }

    return 0;
}