AtCoder Beginner Contest 189
コンテスト前のレート:1850
レート通りのパフォーマンスが得られる順位:491位(1500点、67分54秒)
A - Slot
思考過程
- かつかどうかを判定する。
import java.util.Scanner; public class Main { public static void main(String[] args) throws Exception { Scanner sc = new Scanner(System.in); char[] c = sc.next().toCharArray(); sc.close(); if (c[0] == c[1] && c[1] == c[2]) { System.out.println("Won"); } else { System.out.println("Lost"); } } }
ここまで0分52秒+0ペナ。297位。
B - Alcoholic
思考過程
- 例1を見ると、普通に計算したのでは小数が出てくるので、誤差回避のため全て倍して計算する。
- を足していって、を超えた時点で何杯目かを出力する。
- ももまでしかいかないので、オーバーフローはしない。
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 = sc.nextInt(); int[] v = new int[n]; int[] p = new int[n]; for (int i = 0; i < n; i++) { v[i] = sc.nextInt(); p[i] = sc.nextInt(); } sc.close(); x *= 100; int sum = 0; for (int i = 0; i < n; i++) { sum += v[i] * p[i]; if (sum > x) { System.out.println(i + 1); return; } } System.out.println(-1); } }
ここまで3分21秒+0ペナ。264位。
C - Mandarin Orange
問題
実行時間制限が1.5秒であることに気付いていなかった。
思考過程
- を決めたら、は範囲内のの最小値。
- 制約が微妙な大きさだが、前から順に上手いこと情報を更新しながら見ていく必要があるか?
- いや、の組を全探索するとして、なので、ループの中身が軽ければ通りそう。
工夫しようとしたらとても分やそこらでできそうにはないので、TLEなら仕方ないと思ってこれでいくことにする。 - 念のため入力はScannerではなくBufferedReaderを使っておく。
- 個数は最小値皿数となるが、内側ループ内で最小値は逐次更新、皿数も念のため毎回計算ではなくインクリメントとしておく。 →159msで余裕だった。
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(); int ans = 0; for (int i = 0; i < n; i++) { int min = a[i]; int cnt = 0; for (int j = i; j < n; j++) { min = Math.min(min, a[j]); cnt++; int val = min * cnt; ans = Math.max(ans, val); } } System.out.println(ans); } }
ここまで8分29秒+0ペナ。207位。
D - Logical Expression
思考過程
- 最後が"AND"ならとが両方である必要があって・・・などと動きを手作業で追ってみようとするが、面倒くさくなり、とりあえずDPを実装しようとしてみながら考える。
- 「番目まで見て最後がの場合の通り数」とする。
- (0-indexed)が"AND"の場合、
をにするには、がならはどちらでもよいので倍、がならは限定なのでそのままの値を加算。
をにするには、とが共にである必要があるので、の通り数そのまま。 - が"OR"の場合は逆のことをすればよい。
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[] s = new String[n]; for (int i = 0; i < n; i++) { s[i] = br.readLine(); } br.close(); long[] dp = new long[n + 1]; // 最後がFalseの通り数 long[] dp1 = new long[n + 1]; // 最後がTrueの通り数 dp[0] = 1; dp1[0] = 1; for (int i = 0; i < n; i++) { if (s[i].equals("AND")) { dp[i + 1] = dp[i] * 2 + dp1[i]; dp1[i + 1] = dp1[i]; } else { dp1[i + 1] = dp1[i] * 2 + dp[i]; dp[i + 1] = dp[i]; } } System.out.println(dp1[n]); } }
ここまで15分24秒+0ペナ。178位。
E - Rotate and Flip
思考過程
- 各操作を数式に変えてみる。
- 度回転の方法はとを入れ替えるような感じだった覚えがあったので、それを元に例1を見て符号を合わせる。
- 操作3については、(軸の位置)(軸から元の位置までの距離)と考え、となる。
- 1:→ →
- 2:→ →
- 3:→ →
- 4:→ →
- これらの操作を先に回行っておけば、が何であろうとで答えられる。
- 適当に上記4操作を組み合わせてみると、どのような組み合わせで操作を行っても、を回操作した後の値は一次式で表せる。
- 答えの座標をの形とした場合、はのどちらか、はくらいの値、は操作前のまたはとなることがわかる。
- あとはクエリへの答え方。クエリをでソートし、各クエリに対してに達するまで操作を進めながら答えていくことを考えるが、「に達するまで進める」というような管理が面倒だし、ソートすることで計算量悪化もするので、操作の履歴を全部持っておいて、クエリは普通に入力順に答えるようにした。
import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.PrintWriter; 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()); int[] x = new int[n]; int[] y = new int[n]; for (int i = 0; i < n; i++) { String[] sa = br.readLine().split(" "); x[i] = Integer.parseInt(sa[0]); y[i] = Integer.parseInt(sa[1]); } int m = Integer.parseInt(br.readLine()); int[] ax = new int[m + 1]; // 答えのX座標をax+bとした時のa int[] ay = new int[m + 1]; // 答えのY座標をay+bとした時のa long[] bx = new long[m + 1]; // 答えのY座標をax+bとした時のb long[] by = new long[m + 1]; // 答えのY座標をay+bとした時のb boolean[] c = new boolean[m + 1]; // 答えのax+bのxにxを使うかyを使うか ax[0] = 1; ay[0] = 1; c[0] = true; for (int i = 0; i < m; i++) { String[] sa = br.readLine().split(" "); int t = Integer.parseInt(sa[0]); if (t == 1) { ax[i + 1] = ay[i]; ay[i + 1] = -ax[i]; bx[i + 1] = by[i]; by[i + 1] = -bx[i]; c[i + 1] = !c[i]; } else if (t == 2) { ax[i + 1] = -ay[i]; ay[i + 1] = ax[i]; bx[i + 1] = -by[i]; by[i + 1] = bx[i]; c[i + 1] = !c[i]; } else { long p = Integer.parseInt(sa[1]); if (t == 3) { ax[i + 1] = -ax[i]; ay[i + 1] = ay[i]; bx[i + 1] = 2 * p - bx[i]; by[i + 1] = by[i]; } else { ax[i + 1] = ax[i]; ay[i + 1] = -ay[i]; bx[i + 1] = bx[i]; by[i + 1] = 2 * p - by[i]; } c[i + 1] = c[i]; } } int q = Integer.parseInt(br.readLine()); PrintWriter pw = new PrintWriter(System.out); for (int i = 0; i < q; i++) { String[] sa = br.readLine().split(" "); int a = Integer.parseInt(sa[0]); int b = Integer.parseInt(sa[1]) - 1; long vx = (long) (c[a] ? x[b] : y[b]) * ax[a] + bx[a]; long vy = (long) (c[a] ? y[b] : x[b]) * ay[a] + by[a]; pw.println(vx + " " + vy); } br.close(); pw.flush(); } }
ここまで48分34秒+0ペナ。206位。
F問題は解けず。
それらしいDPを試みるが、振り出しに戻るところを正しく処理できず、例4が合うことなく終了。
最終結果:ABCDEの5完、48分34秒、311位、パフォーマンス2050
レート変動:1850→1872(+22)
今回のFのような確率DPの問題、水diffくらいまでの比較的基本的なものならだいたいできるとは思うのだが、まだ苦手意識がある状態。
だいたいいつも正解者数の伸びはそれほど大きくなく、全体的に苦手な人が多い印象なので、克服できれば有利になれる分野になりそうだが・・・。
レートは、4ヶ月間くらい1700程度で安定 → 約1650まで落ちる → 5ヶ月間くらい1780程度で安定 → 約1640まで落ちる → 2ヶ月間くらい1860程度で安定 といった形で推移しているところで、とりあえずあともう2ヶ月間くらい今のレートを維持できるといいなという感じ。