AtCoder Grand Contest 057
コンテスト前のレート:1961
レート通りのパフォーマンスが得られる順位:419位(1100点、185分23秒)
A - Antichain of Integer Strings
問題
部分文字列の説明まで開いたのに、いつの間にか連続とは限らない部分列で考えていた。
思考過程
- との桁数が同じ場合は、個全てを集合に入れることができる。
- そうでない場合、とりあえずと同じ桁数の値は全て選択して問題ないので、を満たす最大のを求め、まず個を答えに加算する。
- ならば、~(桁数は適当)の間に~は全部現れるので、より桁数が少ない数はつも選択できない。
- の場合、と増やしてみるとが選べなくなり(※この時点では連続とは限らないと勘違いしていた)、と減らしてみるとが選べるようになりそう。
- 桁少ない数は、桁少ない数を全部選んだら選べなくなるので考えなくてよさそう。
- 証明できていないが、なんとなく単調性がありそうなので、二分探索をしてを答えに加算してみることにする。
- 二分探索の判定部分は、midをxxxxとして、1xxxxとx0xxxの少なくとも一方が以下の場合NGとする。 →サンプルのみAC。REも出ている。
- 1xxxxやx0xxxをint型で扱っていたので、long型にする。 →REはなくなったがサンプル以外全部WAなのは変わらず。
- 誤読に気が付き、1xxxxとxxxx0で判定するように修正。
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 t = Integer.parseInt(br.readLine()); PrintWriter pw = new PrintWriter(System.out); for (int z = 0; z < t; z++) { String[] sa = br.readLine().split(" "); int l = Integer.parseInt(sa[0]); int r = Integer.parseInt(sa[1]); int b = 1000000000; while (b > 0) { if (b <= r) { break; } b /= 10; } if (b <= l) { pw.println(r - l + 1); continue; } int v1 = r - b + 1; int ok = b; int ng = l - 1; while (Math.abs(ok - ng) > 1) { int mid = (ok + ng) / 2; String s = String.valueOf(mid); long x = Long.parseLong("1" + s); long y = Long.parseLong(s + "0"); if (x <= r || y <= r) { ng = mid; } else { ok = mid; } } int v2 = b - ok; pw.println(v1 + v2); } br.close(); pw.flush(); } }
ここまで32分55秒+2ペナ。393位。
B - 2A + x
思考過程
- 解を更新できる見込みがなくなるまで、PriorityQueueから最小値を取り出して操作を行うことを繰り返すような流れを考えてみる。
- をいくつにすればよいのかわからないので、の場合との場合の値を両方残しておく。
- 操作を複数回行った後でも、を続けた場合とを続けた場合の範囲内の値は全て取ることが可能。
- 解を更新できる見込みがなくなるのはいつになるのか?
- とりあえずソート後のに最も近付くようにその他の要素を操作すると、例1では~、例4では~の間に全ての要素が収まる。
- そこから最小要素を、最大要素をとして操作した場合のことを考えると、最大と最小の差は倍して減るのが最善。
- そのため、ある時点で求まった解が未満なら最終的ににでき、そうでなければそれ以上操作しても悪化するだけであることがわかる。
- またこのことから、とかの周辺を目指して各要素を操作することをしても、周辺より良くなることはないので、を基準に考えて問題なさそう。
- 各要素について、以下の最大値と以上の最小値のどちらを目指すかをどうやって決めればよいか?
- 一旦全て以下の最大値を取るようにしておき、小さい方から順に以上の最小値に変えていく全探索を行う。(を続けた場合の値が小さい順が、を続けた場合の値が小さい順にもなっている扱いにしてしまっていて1ペナ)
import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.TreeMap; import java.util.TreeSet; 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 x = Integer.parseInt(sa[1]); sa = br.readLine().split(" "); int [] a = new int[n]; for (int i = 0; i < n; i++) { a[i] = Integer.parseInt(sa[i]); } br.close(); TreeSet<Obj> set = new TreeSet<>(); for (int i = 0; i < n; i++) { Obj o = new Obj(); o.min = a[i]; o.max = a[i]; set.add(o); } long fmax = set.last().min; // ソート後のa[n-1]に相当 while (true) { Obj o = set.first(); if (o.min * 2 > fmax) { break; } set.pollFirst(); o.min = o.min * 2; o.max = o.max * 2 + x; if (o.max >= fmax) { continue; } set.add(o); } Obj[] arr = set.toArray(new Obj[0]); MultiTreeSet<Long> set2 = new MultiTreeSet<>(); for (Obj o : arr) { set2.add(o.max); } long ans = fmax - set2.first(); for (int i = 0; i < arr.length - 1; i++) { Obj o = arr[i]; set2.remove(o.max); long val = o.min * 2 - set2.first(); ans = Math.min(ans, val); } if (ans < x) { ans = 0; } System.out.println(ans); } static class Obj implements Comparable<Obj> { long min, max; @Override public int compareTo(Obj o) { if (min != o.min) { return Long.compare(min, o.min); } return Long.compare(max, o.max); } } // 以下ライブラリ(未使用メソッドを削除している) static class MultiTreeSet<T> { TreeMap<T, Integer> map = new TreeMap<>(); int size = 0; void add(T e) { map.put(e, map.getOrDefault(e, 0) + 1); size++; } void remove(T e) { if (e != null && map.containsKey(e)) { int val = map.get(e); if (val == 1) { map.remove(e); } else { map.put(e, val - 1); } size--; } } T first() { return map.firstKey(); } } }
ここまで93分22秒+3ペナ。225位。
残り時間はほとんどC問題に使ってやっぱり解けず。
2進数表現で下から桁目は同じ値が連続、最上位桁のみ前半と後半をペアにした時に全て一方のみ、といった条件が必要そうなどと考えていたが、実装できず。
最終結果:ABの2完1100点、108分22秒、258位、パフォーマンス2266
レート変動:1961→1995(+34)
あとペナ1回少なければ一気に黄色復帰できていたっぽい。
A問題の2回目のペナが、本質的に変わっていないのわかっていつつ藁にも縋る思いで投げてしまったので、それをしていなければ。
なんかAGC040番台の頃はマイナスが多かったけど、AGC050番台になってからそれなりに大きなプラスが多い。