AtCoder Regular Contest 111
コンテスト前のレート:1832
レート通りのパフォーマンスが得られる順位:481位(1300点、111分58秒)
A - Simple Math 2
問題
1問目から大苦戦。下手したらNoSubになるところだった。
なお、思考過程2に進むまでに30分以上かかっている。
思考過程
- をで割った商と余りを倍して・・・などということをやっていたりしたが、商の方はよいが余りの方をそのように処理するのはおかしい。
- そもそも求めようとしている値と、よくあるはどう違うのか?
- 上記2の値を求めた後にで割ることはできないので、先に分母分子を倍してみたら? の制約が微妙に小さいのは乗するからか?
- とりあえずを求めつつ(最後にで割った余りを取ることを考えたら、分子の倍は省略できる)、あとはそれらしいことをやって例3を合わせる。
import java.util.Scanner; public class Main { public static void main(String[] args) throws Exception { Scanner sc = new Scanner(System.in); long n = sc.nextLong(); int m = sc.nextInt(); sc.close(); int m2 = m * m; long ans = power(10, n, m2); System.out.println(ans / m % m); } // 以下ライブラリ static long power(long x, long n, int m) { if (n == 0) { return 1; } long val = power(x, n / 2, m); val = val * val % m; if (n % 2 == 1) { val = val * x % m; } return val; } }
ここまで58分22秒+0ペナ。1066位。
B - Reversible Cards
問題
A問題にあまりに時間がかかりすぎたので、B問題が解けるまでNoSubを視野に入れて提出を保留していた。
結局58分20秒頃にAとBを2問まとめて提出したが、B問題はWA。
思考過程
- まず一旦全部を選び、被っているものをに変えていくことを念のため考えてみるが、変えていく順序で上手くいくかが変わったり、連鎖的に変えていかないと上手くいかなかったりするケースがありそうで、できるとは思えない。
- DPも上手く状態を整理できる気がしない。
- 最大流とかを使えないかとも思ったが、制約が大きいので無理そうな気がする。
- 上記1の、連鎖的に決まっていくケースを考えてみる。
- とを辺としたグラフを作ってみると、各辺についてどちらかの頂点を選ぶことを行い、全体で選ぶ頂点の数を最大化する問題になる。
- これは、上手く選べば連結成分内の頂点を漏れなく選べるので、辺が存在する連結成分の頂点数の和を求めればよさそう。 →WA
- 連結成分の頂点数と、連結成分に対して統合を行った回数(辺の数。頂点数回の可能性がある)の小さい方を求める必要があった。
import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; 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()); DSU dsu = new DSU(400000); for (int i = 0; i < n; i++) { String[] sa = br.readLine().split(" "); int a = Integer.parseInt(sa[0]) - 1; int b = Integer.parseInt(sa[1]) - 1; dsu.merge(a, b); } br.close(); List<List<Integer>> g = dsu.groups(); int ans = 0; for (List<Integer> g2 : g) { int s = g2.size(); int l = dsu.leader(g2.get(0)); int max = dsu.t[l]; // lを含む連結成分にmergeを行っている回数 ans += Math.min(s, max); } System.out.println(ans); } } // 以下、ACLのDisjoint Set Unionに配列tに関する処理を追加
提出
ここまで64分11秒+1ペナ。559位。
C - Too Heavy
問題
方針は比較的すぐ立ったが、実装で添え字周りで混乱して時間かかってしまった。
思考過程
- 重さの制約を抜きにすれば、番目から順に正しい荷物を持たせていけば最小回数になりそう。
- 体重でソートして体重が軽い順に上記を行えば、正しい荷物を持たせる代わりに受け取る荷物の重さが、元々持っていた人の体重未満なので、元々一度も交換できない場合以外で、受け取った人がそれ以上交換できなくなることはない。
- 交換の操作を管理しながらシミュレーションしていく。
import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.PrintWriter; import java.util.ArrayList; import java.util.Arrays; 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()); String[] sa = br.readLine().split(" "); int[] a = new int[n]; for (int i = 0; i < n; i++) { a[i] = Integer.parseInt(sa[i]); } sa = br.readLine().split(" "); int[] b = new int[n]; for (int i = 0; i < n; i++) { b[i] = Integer.parseInt(sa[i]); } sa = br.readLine().split(" "); int[] p = new int[n]; for (int i = 0; i < n; i++) { p[i] = Integer.parseInt(sa[i]) - 1; } br.close(); Obj[] arr = new Obj[n]; for (int i = 0; i < n; i++) { Obj o = new Obj(); o.i = i; // 人の番号 o.a = a[i]; // 人iの体重 o.w = b[p[i]]; // 人iが持っている荷物の重さ o.p = p[i]; // 人iが持っている荷物の番号 arr[i] = o; } Arrays.sort(arr, (o1, o2) -> o1.a - o2.a); // 体重の昇順 // 荷物idxをarrの何番目の人が持っているか // ※arrのindexを示しており、人の番号ではない int[] pi = new int[n]; for (int i = 0; i < n; i++) { pi[arr[i].p] = i; } List<String> list = new ArrayList<>(); for (int i = 0; i < n; i++) { Obj o = arr[i]; if (o.p == o.i) { continue; } if (o.a <= o.w) { System.out.println(-1); return; } int ni = pi[o.i]; // 正しい荷物を持っている人のindex int nw = arr[ni].w; int np = arr[ni].p; pi[o.i] = i; arr[ni].w = o.w; arr[ni].p = o.p; pi[o.p] = ni; o.w = nw; o.p = np; list.add((o.i + 1) + " " + (arr[ni].i + 1)); } PrintWriter pw = new PrintWriter(System.out); pw.println(list.size()); for (String s : list) { pw.println(s); } pw.flush(); } static class Obj { int i, a, w, p; } }
ここまで102分36秒+1ペナ。443位。
D - Orientation
問題
解けず。
以下の思考過程3の実装に苦戦している間に時間切れ。
思考過程
- とりあえず連結成分にごとに分ける。
- 構成される有効グラフがどのような形になるのかを考える。
- まず連結成分内で最小のの集合で長さのサイクルを作る。
- それ以外は、の小さい順に見ていき、の頂点からはのいずれかの頂点へつながる?
解説を読んだ上でもう少し考えてみると、まず上記3は、サイクルとは限らず、強連結成分だった。
上記4は、へつながるとは限らず、辺の両端のが異なるなら小さい方へ流しておけばよい。
結局、が異なるなら小さいほうへ向け、同じならその中で強連結成分を作ればいいらしい。
でも強連結成分の作り方がまだいまいちピンと来ていない。
EとFは問題を見ていない。
最終結果:ABCの3完、107分36秒、468位、パフォーマンス1849
レート変動:1832→1834(+2)
今回はDifficultyが緑水青黄橙赤で、緩やかな良い傾斜。
Aがやや難しすぎだとは思ったけど、それにしてもハマりすぎだし、サンプルが強めだったからできたに過ぎない感じ。
経過20分くらいで全くわからない中、正解者数は既に600人とかいて、ノルマより完全に遅れててやる気をなくしかけてもいた。
解法が一番すぐにわかったのがCで、青diff解けたのは良かったが、実装をもっとスムーズにできなかったものか・・・。
「番の人」と、「配列上の番目」をこんがらがらせすぎ。
まあでも最終的には通せてなんとか救われた。
D問題の強連結成分を作る部分は、近日中にちゃんとやっておくことにする。