はじめに
備忘録として。
この問題のポイント
あんまりよくわかっていないので、これはしっかりと理解したい!!
- 考察をしっかりとすること!
- 文字を入れ替えた時に①入れ替えようが入れ替えまいが同じ文字になること、②違う文字列ができること。
- ②違う文字列ができる。でもかぶる文字列があるんじゃない?なら、単純にはできない。
- 今回求めたいのはちょうど 1 回 ある場所の文字とある場所の文字を交換した後の文字列としてあり得るものがいくつあるか求めてください。要するに、あの操作したら、何通りくらい文字作れる?って感じ。
- 例から問題の性質を考察する。考える!そういうテクニックが競プロでは有効!まあ、現実世界でも有効な気がします!
同じ文字になるを考察
- 同じ文字になる。同じ文字を選ぶ選び方は何通りありますか?ということ。だから、
目次
問題と解説まとめ
問題 atcoder.jp
Javaの解答例
このコードをJavaへ変換しました!
提出コード Submission #51356715 - Monoxer Programming Contest 2024(AtCoder Beginner Contest 345)
解説YouTube www.youtube.com
import java.util.*; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); String s = scanner.next(); int n = s.length(); long same = 0; Map<Character, Integer> cnt = new HashMap<>(); for (char c : s.toCharArray()) { cnt.put(c, cnt.getOrDefault(c, 0) + 1); } for (int m : cnt.values()) { same += c2(m); } long diff = c2(n) - same; long ans = diff; if (same > 0) ans++; System.out.println(ans); } private static long c2(long n) { return n * (n - 1) / 2; } }