AtCoder Beginner Contest 181
- A - Heavy Rotation
- B - Trapezoid Sum
- C - Collinearity
- D - Hachi
- E - Transformable Teacher
- F - Silver Woods
コンテスト前のレート:1676
レート通りのパフォーマンスが得られる順位:467位(1500点、53分42秒)
A - Heavy Rotation
思考過程
- 白と黒は交互なので、で分岐。
- 例1より、(余り)の場合に"White"。
import java.util.Scanner; public class Main { public static void main(String[] args) throws Exception { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); sc.close(); if (n % 2 == 0) { System.out.println("White"); } else { System.out.println("Black"); } } }
ここまで0分44秒+0ペナ。242位。
B - Trapezoid Sum
問題
A問題と比べていきなりだいぶめんどくさそうなのが出てきた。
思考過程
- 制約が大きいので、ではなくでやる必要がある。
- ~の和は、台形の面積を求める要領で、。
import java.util.Scanner; public class Main { public static void main(String[] args) throws Exception { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] a = new int[n]; int[] b = new int[n]; for (int i = 0; i < n; i++) { a[i] = sc.nextInt(); b[i] = sc.nextInt(); } sc.close(); long ans = 0; for (int i = 0; i < n; i++) { ans += (long) (a[i] + b[i]) * (b[i] - a[i] + 1) / 2; } System.out.println(ans); } }
ここまで2分42秒+0ペナ。329位。
C - Collinearity
思考過程
- で点の組み合わせを全探索。
- 点が同一直線上にあるかどうかは、の傾きとの傾きが等しいかどうかで判定する。
- をそれぞれ座標、座標の差として、であるかどうかを求めたい。
- 移項して、であるかどうかで判定する。
import java.util.Scanner; public class Main { public static void main(String[] args) throws Exception { Scanner sc = new Scanner(System.in); 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(); } sc.close(); for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { for (int k = j + 1; k < n; k++) { int x1 = x[j] - x[i]; int x2 = x[k] - x[i]; int y1 = y[j] - y[i]; int y2 = y[k] - y[i]; if (x1 * y2 == x2 * y1) { System.out.println("Yes"); return; } } } } System.out.println("No"); } }
ここまで6分39秒+0ペナ。146位。
早解きできるときはできるんだけどな・・・。
D - Hachi
問題
ここからボロッボロ。
正解者数の伸びはそれほど早くはないと思って焦らずやっていたつもりだったが、それで時間かかるにしても限度がある。
思考過程
- とりあえずに現れる各数字の数をカウントしておく。
- が桁の場合、が個の場合のみ。
- が桁の場合、~まで大した数でもないので、場合分けで頑張る。
- が桁以上の場合、下桁の構成だけ考えればよい。下から桁目の偶奇で場合分けする?
- いや、~を構成可能か調べ、構成可能な数がで割り切れれば"Yes"のようにできる。
- などとやっている内に、結局桁以上の場合のロジックで桁や桁の場合もまとめてできそうなので、余計な場合分けを消しにかかる。
- しかし結局、桁数によって探索範囲を絞ることになる。(絞らずにWA喰らうなどした)
import java.util.Scanner; public class Main { public static void main(String[] args) throws Exception { Scanner sc = new Scanner(System.in); char[] s = sc.next().toCharArray(); sc.close(); solve(s); // 上手くいかずにデバッグした跡 // for (int i = 0; i < 1000; i++) { // String si = String.valueOf(i); // System.out.print(i + "\t"); // solve(si.toCharArray()); // } } static void solve(char[] s) { int[] cnt = new int[10]; for (int i = 0; i < s.length; i++) { cnt[s[i] - '0']++; } int start = 1; int end = 10; if (s.length == 2) { start = 11; end = 100; } if (s.length >= 3) { start = 101; end = 1000; } for (int i = start; i < end; i++) { // iに現れる数字の数を調べる int[] a = new int[10]; String si = String.valueOf(i); for (int j = 0; j < si.length(); j++) { a[si.charAt(j) - '0']++; } // Sに含まれる数字より多く必要な数字があればfalse boolean flg = true; for (int j = 0; j < 10; j++) { if (a[j] > cnt[j]) { flg = false; break; } } if (flg) { if (i % 8 == 0) { System.out.println("Yes"); return; } } } System.out.println("No"); } }
ここまで35分45秒+2ペナ。990位。
E - Transformable Teacher
問題
大まかな方針はほぼ一瞬でわかったのに、実装が下手くそ。
思考過程
- をソートし、その中にから個を選んで適切な位置に挿入し、の前から順につずつペアにしていく。ということをやる場合に、からどの個を選べばよいかという問題。
- もソートして、番目を挿入したときの結果を求める。
- の0番目を抜き出して番目を挿入したときの差分を求める。ということをやっていけば、差分を求めるのにを参照する部分が回の合計でで済む。
- しかし、差分を求める計算が偶奇でこんがらがってしまい、実装できそうになかったので、累積和を使うことを考える。
- 大まかにいえば、の挿入位置をとすると、より前まではのようにペアになるので、(偶, 奇)ペアの合計を、より後からは(奇, 偶)ペアの合計を足し、さらにを足す。
- これだけではWAだったので、デバッグしながら、をしたりして添え字ガチャをする。
- 結局、の偶奇と両端の処理が肝であったらしい。
ソースはとりあえず本番時そのままのものを貼っておくが、後半のif文等は多分ぐちゃぐちゃ。
import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] sa = br.readLine().split(" "); int n = Integer.parseInt(sa[0]); int m = Integer.parseInt(sa[1]); sa = br.readLine().split(" "); int[] h = new int[n]; for (int i = 0; i < n; i++) { h[i] = Integer.parseInt(sa[i]); } sa = br.readLine().split(" "); int[] w = new int[m]; for (int i = 0; i < m; i++) { w[i] = Integer.parseInt(sa[i]); } br.close(); Arrays.sort(h); Arrays.sort(w); long[] v1 = new long[n + 1]; long[] v2 = new long[n + 1]; for (int i = 1; i < n; i++) { if (i % 2 == 1) { v1[i] = h[i] - h[i - 1]; } else { v2[i] = h[i] - h[i - 1]; } } for (int i = 2; i <= n; i++) { v1[i] += v1[i - 1]; v2[i] += v2[i - 1]; } long ans = Long.MAX_VALUE; for (int i = 0; i < m; i++) { int idx = Arrays.binarySearch(h, w[i]); if (idx < 0) { idx = ~idx; if (idx > 0) { idx--; } } long val1 = v1[idx]; long val2 = v2[n] - v2[idx]; long val3 = Math.abs(w[i] - h[n - 1]); if (idx < n - 1) { if (idx % 2 == 0) { val3 = Math.abs(h[idx] - w[i]); } else { val2 = v2[n] - v2[idx + 1]; val3 = Math.abs(h[idx + 1] - w[i]); } } long val = val1 + val2 + val3; ans = Math.min(ans, val); } System.out.println(ans); } }
ここまで86分43秒+3ペナ。1037位。
F - Silver Woods
問題
さすがに時間が足りない。
思考過程
- 点の組み合わせを全探索。
- 各組み合わせについて、座標の値がとして、下の壁との距離、上の壁との距離、との距離の内の最大値を求める。
- 上記2の最小値が答え? →例2までしか合わない。
- 例3を紙の上にそれらしくプロットしてみると、他の点が邪魔をして、必ずしも上記2のつの距離の内の最大のところを通れるとは限らないようだった。
ここからあと何分あれば、二分探索+UnionFindにたどり着けたのか・・・。
最終結果:ABCDEの5完、101分43秒、1131位、パフォーマンス1277
レート変動:1676→1642(-34)
Highest-98からこの土日でさらに-80。
次回はパフォ1130未満程度で水色落ち。
今日のような状況で、E問題をスキップしてF問題に挑戦して失敗みたいなことになれば、普通にあり得そう。
10/3に黄パフォを出してほぼHighestまで回復後、この1ヶ月の結果が1勝6敗。内2回は緑パフォ。
最近の緑~水diffが難しすぎる・・・。
7月後半以降まともな精進をしていないので、周りができるようになった結果ならまだいいのだが、ここまでの急落はさすがに自分が落ちているのも合わさっていないとあり得ない気がするので、水diff前後の問題を詰まらず解けるように、あさかつ/くじかつとかに参加していくのがいいのかもしれない。