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