AtCoder Beginner Contest 182
コンテスト前のレート:1642
レート通りのパフォーマンスが得られる順位:679位(1500点、46分58秒)
A - twiblr
思考過程
- からを引く。
- 答えがマイナスにならないかと思ったが、制約でそれはないことを確認。
import java.util.Scanner; public class Main { public static void main(String[] args) throws Exception { Scanner sc = new Scanner(System.in); int a = sc.nextInt(); int b = sc.nextInt(); sc.close(); int m = 2 * a + 100; System.out.println(m - b); } }
ここまで0分44秒+0ペナ。69位。
B - Almost GCD
思考過程
- となるでは割り切れないので、を全部試したい。
- 各で毎回個調べてカウントしていても、ループ回数は全体で程度なので間に合う。
- 毎回答えとカウント結果のmaxを取れば・・・と思ったら、出力は最大のGCD度ではなくそれを満たす値だったので、max関数ではなく、maxとansを持ちつつif文で処理する。
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]; for (int i = 0; i < n; i++) { a[i] = sc.nextInt(); } sc.close(); int max = 0; int ans = 0; for (int k = 2; k <= 1000; k++) { int cnt = 0; for (int j = 0; j < n; j++) { if (a[j] % k == 0) { cnt++; } } if (cnt > max) { max = cnt; ans = k; } } System.out.println(ans); } }
ここまで3分19秒+0ペナ。151位。
C - To 3
問題
※入力を、の桁数をとして記述。
思考過程
- ということは、で間に合いそうなので、bit全探索を行う。
- 残す桁の各桁の和がの倍数の場合のみ、残す桁数のminを取っていく。
import java.util.Scanner; public class Main { public static void main(String[] args) throws Exception { Scanner sc = new Scanner(System.in); String s = sc.next(); sc.close(); int n = s.length(); int n2 = 1 << n; int ans = 20; for (int i = 1; i < n2; i++) { int sum = 0; int cnt = n; // 消す桁数 for (int j = 0; j < n; j++) { if ((i >> j & 1) == 1) { // 残す桁の場合 int d = s.charAt(j) - '0'; sum += d; cnt--; } } if (sum % 3 == 0) { if (cnt < ans) { ans = cnt; } } } if (ans == 20) { System.out.println(-1); } else { System.out.println(ans); } } }
ここまで8分15秒+0ペナ。162位。
D - Wandering
思考過程
- とりあえず累積和を計算する。(~の和)
- 現在地にを足して答えとのmaxを取って・・・の繰り返しかと思いきや、例1を見たら、の中の~全ての時点がmaxを取る対象だった。
- これは、累積和の累積max(~のmax)を求めればよさそう。
import java.io.BufferedReader; import java.io.InputStreamReader; public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); String[] sa = br.readLine().split(" "); int[] a = new int[n]; for (int i = 0; i < n; i++) { a[i] = Integer.parseInt(sa[i]); } br.close(); long[] b = new long[n + 1]; long[] c = new long[n + 1]; for (int i = 0; i < n; i++) { b[i + 1] = b[i] + a[i]; c[i + 1] = Math.max(c[i], b[i + 1]); } long ans = 0; long now = 0; for (int i = 1; i <= n; i++) { ans = Math.max(ans, now + c[i]); now += b[i]; } System.out.println(ans); } }
ここまで13分36秒+0ペナ。124位。
E - Akari
問題
思考過程の前半を完全に捨ててやり直したことによる時間ロスが痛かった。
思考過程
- 各電球から愚直に方向調べるのは間に合わないので、調べるところを減らしたい。
- 最初に個全てをキューに入れてBFSを行い、壁マスだけでなく、既に光が届くとわかっているマスに到達した場合も打ち切る?
- 例3がになってしまい、足りない。
- の電球に対して、途中で打ち切っているせいでをカウントできていなかった。
- 電球を中心とした探索ではなく、各マスについて、そのマスを照らせる電球が存在するかという判定を行うことを考える。
- TreeMap<座標、電球か壁か>を、各行と各列分用意しておく。
- 各マスの座標に対応するTreeMapから、その座標に最も近いキーを取得し、それが電球だったら照らせるマス。
- 計算量はのつもり。2500ms制限のところ2279msでぎりぎりだった。
import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.List; import java.util.TreeMap; 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 h = Integer.parseInt(sa[0]); int w = Integer.parseInt(sa[1]); int n = Integer.parseInt(sa[2]); int m = Integer.parseInt(sa[3]); List<TreeMap<Integer, Integer>> list1 = new ArrayList<>(); for (int i = 0; i < h; i++) { list1.add(new TreeMap<>()); } List<TreeMap<Integer, Integer>> list2 = new ArrayList<>(); for (int i = 0; i < w; i++) { list2.add(new TreeMap<>()); } for (int i = 0; i < n; i++) { sa = br.readLine().split(" "); int x = Integer.parseInt(sa[0]) - 1; int y = Integer.parseInt(sa[1]) - 1; list1.get(x).put(y, 1); list2.get(y).put(x, 1); } for (int i = 0; i < m; i++) { sa = br.readLine().split(" "); int x = Integer.parseInt(sa[0]) - 1; int y = Integer.parseInt(sa[1]) - 1; list1.get(x).put(y, -1); list2.get(y).put(x, -1); } br.close(); int ans = 0; for (int i = 0; i < h; i++) { TreeMap<Integer, Integer> map1 = list1.get(i); for (int j = 0; j < w; j++) { // 左 TreeMap<Integer, Integer> map2 = list2.get(j); Integer key = map1.floorKey(j); if (key != null && map1.get(key) == 1) { ans++; continue; } // 右 key = map1.ceilingKey(j); if (key != null && map1.get(key) == 1) { ans++; continue; } // 上 key = map2.floorKey(i); if (key != null && map2.get(key) == 1) { ans++; continue; } // 下 key = map2.ceilingKey(i); if (key != null && map2.get(key) == 1) { ans++; continue; } } } System.out.println(ans); } }
ここまで32分14秒+0ペナ。271位。
F - Valid payments
問題
解けず。
解説や人のツイートを見た感じだと、考察が半分できていたかどうかといったところ。
思考過程3(エスパー狙い)に時間を費やしすぎで、4に進んだ頃にはもう残り10分とかだった。
思考過程
- まずは条件を満たす。
- ~くらいを全部試す愚直を作ってみて、法則をつかもうとする。
- が円玉を使わない場合、円玉を使うが条件を満たすことはなかったり、より大きいを使う場合において規則性が感じられたりなどはしたが、決定的なことはわからず。
- 愚直実装では、とりあえず円玉を使うかどうかだけを視覚化していたが、何個払う/もらうかを調べてみると、各について通りか通りしかない。
- 具体的には、円ちょうどを払うのに使うの枚数、とすると、
- の場合、払う場合、お釣りでもらう場合、使わない場合の通り。
- の場合、払う場合、お釣りでもらう場合の通り。
- これを全部試すととなるがどうしよう。
あとはDPをすればになるようだが、時間内にそこまで詰め切れず。
最終結果:ABCDEの5完、32分14秒、393位、パフォーマンス1891
レート変動:1642→1670(+28)
30くらい上がると結構上がった気分にはなるが、むしろパフォーマンスたった1900弱でこんなに上がっていることに違和感を感じたくらいだった。
(Highestの1820だったら+7とかだと思うので)
それだけレートが下がっているという現実・・・。
F問題が決して全く何もできない難易度ではないはずだが、日々の精進で10分で解説を見る諦め癖が付きすぎているのが悪いのかもしれない。
知見を得る目的だけで言えば、さっさと見た方が効率は良いが。
新しい問題ですぐ解説を見てしまう分、くじかつなどでちゃんと一度通した問題ができなくなっていないか再確認するべきだと思っているところ。