一番簡単な A問題でまさかの WA（不正解：Wrong Answer）。ABC 367 で大惨敗したので反省文を書きます。D問題までです。
A – Shout Everyday
AtCoder 王国の住民は A 時になるとたこ焼きへの愛を叫ぶことになっています。
AtCoder 王国に住む高橋君は毎日 B 時に就寝し C 時に起床します。高橋君は、起きているときはたこ焼きへの愛を叫ぶことができ、寝ているときは叫ぶことができません。高橋君が毎日たこ焼きへの愛を叫ぶことができているか判定してください。ただし、一日は 24 時間であり、高橋君が寝ている時間は 24 時間未満であるとします。
入力されるデータ
A B C
（ただし 0 ≦ A, B, C ≦ 23, A, B, C は相異なる）
C（起床時刻）＜ B（就寝時刻）であれば C ＜ A ＜ B であるかどうかを調べればよいのですが、B ＜ C の場合もあるのでその場合は B に 24を足してから C ＜ A ＜ B かどうかを調べればよいのではないかと思ったのですが、まさかの WA（不正解：Wrong Answer）。
A に対しても 24 を足さなければならない場合があることを失念していました。なぜWAになったのかわからず慌ててしまい、終了10分前になってきがついて修正できたものの、完全に調子を乱されトホホな結果になってしまいました。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
using System; using System.Linq; class Program { static void Main() { int A, B, C; { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); A = vs[0]; B = vs[1]; C = vs[2]; } if (B < C && A < B) // これを失念していた！ A += 24; if (B < C) B += 24; if (C < A && A < B) Console.WriteLine("Yes"); else Console.WriteLine("No"); } } |
このような場合分けに自信がない場合はこんな方法もあります。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
class Program { static void Main() { int A, B, C; { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); A = vs[0]; B = vs[1]; C = vs[2]; } int time = C; // 起床時刻からスタート bool ok = false; while (true) { time++; time %= 24; // 24時をすぎたら 0時に if(time == B) // 就寝時刻になったら終了 break; if (time == A) // 起きている時間に A になったらたこ焼きへの愛を叫ぶことができる ok = true; } if (ok) Console.WriteLine("Yes"); else Console.WriteLine("No"); } } |
B – Cut .0
実数 X が小数点以下第 3 位まで与えられます。
実数 X を以下の条件を満たすように出力してください。
小数点以下の部分について、末尾に 0 を付けない
末尾に過剰な小数点を付けない
（例：12.340 なら 12.34, 3.000 なら 3 と出力する）入力されるデータ
0 ≦ X ≦ 100
X は小数点以下第 3 位まで与えられる
これは C# なら簡単な問題です。入力を double型で受取りそのまま出力すれば小数点以下の余分な 0 や小数点がない状態で出力されます。
|
1 2 3 4 5 6 7 8 9 10 |
using System; class Program { static void Main() { double d = double.Parse(Console.ReadLine()); Console.WriteLine(d); } } |
C – Enumerate Sequences
以下の条件を満たす長さ N の整数列を辞書順で小さい方から順に全て出力して下さい。
i 番目の要素は 1 以上 R_i 以下
総和が K の倍数入力されるデータ
N K
R_1 R_2 … R_N
（ただし 1 ≦ N ≦ 8, 2 ≦ K ≦ 10, 1 ≦ R_i ≦ 5 ）
N と R_i の値が両方とも小さいので i 番目の要素は 1 以上 R_i 以下の整数列すべてを求めてから 総和が K の倍数 かどうかを調べるという方法を取りました。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
using System; using System.Collections.Generic; using System.Linq; class Program { static void Main() { int N, K; { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); N = vs[0]; K = vs[1]; } int[] R = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); List<List<int>> lists = new List<List<int>>(); lists.Add(new List<int>()); for (int i = 0; i < N; i++) { int r = R[i]; List<List<int>> temp = new List<List<int>>(); foreach (var list in lists) { for (int k = 0; k < r; k++) { List<int> list2 = new List<int>(list); list2.Add(k + 1); temp.Add(list2); } } lists = temp; } foreach (var list in lists) { if (list.Sum() % K == 0) Console.WriteLine(string.Join(" ", list)); } } } |
D – Pedometer
湖の周りに N 個の休憩所があります。休憩所には時計回りに 1, 2, …, N の番号が付いています。休憩所 i から休憩所 i + 1 まで時計回りに歩くには A_i 歩かかります。ただし休憩所 N + 1 は休憩所 1 を指します。
休憩所 s から休憩所 t ( s ≠ t ) まで時計回りに歩くのにかかる最小の歩数は M の倍数でした。(s, t) の組として考えられるものの数を求めてください。
入力されるデータ
N M
A_1 A_2 … A_N
（ただし、2 ≦ N ≦ 2×10^5
1 ≦ A_i ≦ 10^9, 1 ≦ M ≦ 10^6）
剰余を使った問題かな？と思ったのですが、他の問題で時間を浪費していて実質タイムオーバー。
まず累積和を求めます。sums[i + 1] には A[0]（＝ A_1） から A[i] までの総和を格納します。そして mods に sums を M で割ったときの剰余を格納します。あとは mods[i] と同じ値が mods[i + 1] から mods[i + N – 1] までに何個あるかを数えます。
そのためには i = 0 のとき mods[0] から mods[N – 1] を辞書に格納して i をインクリメントしたら mods[i – 1] を減算して mods[i – 1 + N] を辞書に追加します。dic[mods[i]] をみれば mods[i] から mods[i + N – 1] までに何個あるかわかるのでここから 1 を引くことで、mods[i] と同じ値が mods[i + 1] から mods[i + N – 1] までに何個あるかを求めることができます。これを足し合わせたものが答えです。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 |
using System; using System.Collections.Generic; using System.Linq; class Program { static void Main() { int N, M; { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); N = vs[0]; M = vs[1]; } int[] A = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); long[] sums = new long[A.Length * 2 + 1]; for (int i = 0; i < N; i++) sums[i + 1] = sums[i] + A[i]; for (int i = 0; i < N; i++) sums[i + 1 + N] = sums[i + N] + A[i]; long[] mods = new long[sums.Length]; for (int i = 0; i < sums.Length; i++) mods[i] = sums[i] % M; Dictionary<long, int> dic = new Dictionary<long, int>(); long ans = 0; for (int i = 0; i < N; i++) { if(!dic.ContainsKey(mods[i])) dic.Add(mods[i], 1); else dic[mods[i]]++; } ans += dic[mods[0]] - 1; for (int i = 1; i < N; i++) { dic[mods[i - 1]]--; if (!dic.ContainsKey(mods[i - 1 + N])) dic.Add(mods[i - 1 + N], 1); else dic[mods[i - 1 + N]]++; ans += dic[mods[i]] - 1; } Console.WriteLine(ans); } } |
