問題文 と 解説
問題文
解説 YouTube
解答例 1
import java.util.*; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int a = scanner.nextInt(); int b = scanner.nextInt(); int w = a + b; List<Integer> d = new ArrayList<>(); for (int i = 0; i < n; i++) { int value = scanner.nextInt(); d.add(value % w); } d.sort(Comparator.naturalOrder()); for (int i = 0; i < n; i++) { d.add(d.get(i) + w); } for (int i = 0; i < n; i++) { int l = d.get(i); int r = d.get(i + n - 1); if (r - l + 1 <= a) { System.out.println("Yes"); return; } } System.out.println("No"); } }
メモ
今回の問題の解法
予定の数直線があって、(何日後に予定があるかの数直線)、その上を休日のブロックが移動していくイメージです!
問題に周期性が入っている場合は、大体、割り算の余りを使うよ!今回だったら、%になっている部分がそう! 1週間が7日だとすると、2日目と9日目の曜日は一緒ですよね。例えば、2日目が5月2日で火曜日だとすると、九日目は5月9日の火曜日ですよね。
ちなみに9を1週間の日数、7で割ってしまったら、余りは2になります。2を7で割ると、余りは2になるんです。そう、2日目と9日目の余りは一緒なんです。
要するに、一週間の日付で割ってしまえば、何日先だろうとあまり関係がないんです!曜日の観点で言えば。
あと、周期性がある問題の場合は、2周させるっていう手がよく使われます。これは、うまく説明できないので、ぜひ、上記の解説動画を見てください!C問題を説明してくれているときにこの概念が出ます。
頻出なようですので、ぜひこの機会に学んでみてはいかかでしょうか。
私も現在進行形で勉強させていただいています!
細かいコードの説明をしていきたい 学ぶところが今回の問題、とても多かった。飛躍しそう。コードって小さなコードに分かれますよね。今まで自分が使ってこなかった考え方、書き方がたくさんされていて、身に着けたら幅が広がりそう。いや、より深く力が手に入りそう。この武器、欲しい。
最後のfor
はw
じゃなくてn
回、回すのだ。その理由は、、予定分だけ回したら、全部の予定の組み合わせをカバーできるからですね。紙に書き出したらわかりやすいかもですね。
この問題で初めてイメージトレーニングをしました!結構いいですね。 イメトレのコツは、、①静かな場所。(邪魔が入りにくい場所。)。②目を瞑る。(余計な情報が入ってこない。)➂自分が過去解いたことがある問題。(知らないものはイメージしようがない。)、④習慣化。←これはメンタリストDaiGoさんのDラボと小さな習慣やアトミックハビッツという本を読んでだら習得可能。
以上、備忘録でした。
解答例 2
import java.util.*; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int a = scanner.nextInt(); int b = scanner.nextInt(); int w = a + b; List<Integer> d = new ArrayList<>(); for (int i = 0; i < n; i++) { int value = scanner.nextInt(); d.add(value % w); } d.sort(Comparator.naturalOrder()); for (int i = 0; i < n; i++) { d.add(d.get(i) + w); } for (int i = 0; i < d.size() - 1; i++) { if (d.get(i + 1) - d.get(i) >= b + 1) { System.out.println("Yes"); return; } } System.out.println("No"); } }