AtCoder Regular Contest 119
コンテスト前のレート:2064
レート通りのパフォーマンスが得られる順位:290位(1300点、34分02秒)
A - 119 × 2^23 + 1
思考過程
- となる最大のを取った時が最小?
- のような気がしたが、サンプルが合わないのでを~上記1.の最大値で全探索してみる。
- まだ合わなかったが、実装ミスしていただけだった。直したらAC。
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)); long n = Long.parseLong(br.readLine()); br.close(); long ans = n; int b = 1; while (true) { long x = 1L << b; if (x > n) { break; } // 実装ミス:以下2行がxではなくbになっていた long a = n / x; long c = n % (a * x); long val = a + b + c; ans = Math.min(ans, val); b++; } System.out.println(ans); } }
ここまで5分42秒+0ペナ。704位。
B - Electric Board
思考過程
- 問題文を読み解くと、他の'0'を飛び越えない範囲で'0'を自由に動かせる。'0'に注目して考える。
- '0'を移動させるだけなので、数が合わなければ不可能。逆に数が合えば必ず可能。
- 他の'0'を飛び越えられないので、内の番目の'0'は、内の番目の'0'と対応させるしかない。
- 端の方から適切に動かしていけば、どの'0'も回動かせば目当ての位置に動かせる。
- 結局、内の番目の'0'は、内の番目の'0'が元々同じ位置にあった場合のみ動かさなくてよく、番目の位置が不一致である個数が答え。
- のはずだがWA。誤読していないか、ここまでの思考過程に誤りがないか、実装ミスがないか、散々見直したがおかしいところが見つからない。
- 分ほど悩んでようやく、Java特有の実装ミスに気付く。(Integer型とint型の比較なら「==」で問題ないが、Integer型同士はequalsメソッドで比較する必要がある)
import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.List; 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()); char[] s = br.readLine().toCharArray(); char[] t = br.readLine().toCharArray(); br.close(); List<Integer> l1 = new ArrayList<>(); List<Integer> l2 = new ArrayList<>(); for (int i = 0; i < n; i++) { if (s[i] == '0') { l1.add(i); } if (t[i] == '0') { l2.add(i); } } if (l1.size() != l2.size()) { System.out.println(-1); return; } int ans = 0; for (int i = 0; i < l1.size(); i++) { // 実装ミス:「!=」で比較していた if (!l1.get(i).equals(l2.get(i))) { ans++; } } System.out.println(ans); } }
ここまで20分30秒+1ペナ。405位。
C問題は30分ほどかけて解けず。
公式解説に書かれている、奇数番目の和と偶数番目の和が等しいという条件にすら気付かなかったので、全く解ける気がしなかった。
残り1時間余りはD問題に費やした。
赤マスがマス以上存在する行の数を、列の数を、赤マスを上下左右に繋いでできる連結成分の数をとすると、回、縦方向でも横方向でも好き(最大は回と回だが)に選べそうという結論にまでは至ったが、それの具体的な手順を40分ほどかけても実装することができなかった。
連結成分を気にする必要もなく、あらかじめ縦と横を何回選ぶかを求めておいて、あとは選ぶ方向についてマスしか残っていないところから順にやっていけばよさそうだと思ったのだが、選ぶ方向についてマス以上存在する箇所しか残っていない状態になった時の優先順位がおかしかったのかもしれない?(あるいはやっぱりちゃんと連結成分ごとに見ないと駄目だったか)
E問題も一応問題文だけは読んでいて、少しは考えてみたかったが、Dを優先していて時間を取れなかった。
最終結果:ABの2完、25分30秒、839位、パフォーマンス1425
レート変動:2064→2013(-51)
橙パフォが出たARC118のプラス分をほぼそのまま吐き出した。
やっぱりABCは爆死続きだけどARCだけ平気なんてそんな甘いことにはならないか・・・。