東京海上日動 プログラミングコンテスト2021(AtCoder Regular Contest 122)
コンテスト前のレート:2080
レート通りのパフォーマンスが得られる順位:315位(1500点、70分14秒)
A - Many Formulae
問題
できてみればそこまで難しいDPでもなかったのに、時間かかってしまった。
例3がなかったらペナも出しまくってたかも。
思考過程
- 各が全部で何回足されて何回引かれるか、寄与数を求められないか? と思うがよくわからない。
- "-"が個の場合から個くらいの場合まで分けるとか? "-"が連続するかどうかを問わなければ二項係数でよいが、連続する場合を取り除くとかは厳しそう。
- 樹形図で伸ばしていくことを考えると、「番目まで見て最後の符号がの場合の答え」として、"+"へは"+"と"-"から、"-"へは"+"からだけ遷移するようにしてできそう。
- しかし、どうにも例3が合わない。modの取り方がおかしいかと思って見直してみても変わらず。
- 上記のDPで、答えだけでなく件数も管理して、を足し引きするときに件数倍してやる必要があった。
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 mod = 1000000007; long[] dpp = new long[n]; // i番目まで見て末尾が"+"の時の総和 long[] dpm = new long[n]; // i番目まで見て末尾が"-"の時の総和 long[] dpp2 = new long[n]; // i番目まで見て末尾が"+"の件数 long[] dpm2 = new long[n]; // i番目まで見て末尾が"-"の件数 dpp[0] = a[0]; dpp2[0] = 1; for (int i = 1; i < n; i++) { dpp[i] += (dpp[i - 1] + a[i] * dpp2[i - 1]) % mod; // +→+ dpp[i] += (dpm[i - 1] + a[i] * dpm2[i - 1]) % mod; // -→+ dpp[i] %= mod; dpm[i] = (dpp[i - 1] - a[i] * dpp2[i - 1]) % mod; // +→- if (dpm[i] < 0) { dpm[i] += mod; } dpp2[i] = (dpp2[i - 1] + dpm2[i - 1]) % mod; dpm2[i] = dpp2[i - 1]; } long ans = dpp[n - 1] + dpm[n - 1]; ans %= mod; System.out.println(ans); } }
ここまで27分15秒+0ペナ。739位。
B - Insurance
問題
「とりあえず三分探索してみればいいや」と決断するのが遅く、で割り忘れる実装ミスをしている箇所があって解消に手間がかかり、時間がかかった。
思考過程
- となるを全部調べればよさそうな気もしたが、中間とかに答えがない根拠が薄い。
- なんとなく下に凸な関数になっていそうな気がする。
- 例1でをずつ増やしてみたりして、多分合っていそうという気を強める。
- 最近ABC204-Eで失敗したばかりで抵抗があったが、とりあえず一度三分探索を出すだけ出してみることにする。 →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)); 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(); // 失う金額の期待値 double t = 0; for (int i = 0; i < n; i++) { t += a[i]; } t /= n; // 保険料を三分探索 double l = 0; double r = 1e9; for (int i = 0; i < 200; i++) { double m1 = (l * 2 + r) / 3; double m2 = (l + r * 2) / 3; double v1 = t + m1 - calc(a, m1); double v2 = t + m2 - calc(a, m2); if (v1 <= v2) { r = m2; } else { l = m1; } } System.out.println(t + r - calc(a, r)); } // 保険金の期待値 static double calc(int[] a, double x) { double x2 = x * 2; double ret = 0; for (int i = 0; i < a.length; i++) { ret += Math.min(a[i], x2); } return ret / a.length; } }
ここまで43分44秒+0ペナ。620位。
C - Calculator
思考過程
- 値を大幅に増やしていくには、操作をメインに使うことになる。
- 操作とを繰り返すとフィボナッチ数列になっている。
- フィボナッチ数列の適当なところにを足してみると、足さなかった場合との差がフィボナッチ数列になっている。
- をフィボナッチ数列に登場する値のみの和に分解することで、操作とを繰り返しながらどのタイミングで操作やを挟めばよいかがわかる。
- 実装上は、操作やを行った後の最終的な数列で値がになるインデックスの偶奇によって、操作とが入れ替わるようにする。
- 上記のインデックスは、フィボナッチ数列でを超えない最大の値が出現する箇所。
- が小さい時(特にとかとか)の動作が怖かったので、念のため以下の場合は回操作としてみた。(後から試してみたら、そんな保険を入れなくても通った)
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)); long n = Long.parseLong(br.readLine()); br.close(); // 7 if (n <= 130) { System.out.println(n); for (int i = 0; i < n; i++) { System.out.println(1); } return; } int m = 90; long[] a = new long[m]; a[1] = 1; for (int i = 2; i < m; i++) { a[i] = a[i - 2] + a[i - 1]; } long n2 = n; int[] c = new int[m]; int msb = 0; // 6 for (int i = m - 1; i > 0; i--) { c[i] = (int) (n2 / a[i]); n2 -= c[i] * a[i]; if (msb == 0 && c[i] > 0) { msb = i; } } // デバッグ用 // System.out.println(Arrays.toString(a)); // System.out.println(Arrays.toString(c)); int d = msb % 2; List<Integer> list = new ArrayList<>(); list.add(2 - d); for (int i = 2; i <= msb; i++) { // 元のフィボナッチ数列からの差分調整のため、 // フィボナッチ数列のp番目の値をc[p]回足したい // (c[p]は基本的に(必ず?)1以下) int p = msb - i + 1; for (int j = 0; j < c[p]; j++) { if (d == 0) { list.add(1 + i % 2); } else { list.add(2 - i % 2); } } if (d == 0) { list.add(3 + i % 2); } else { list.add(4 - i % 2); } } System.out.println(list.size()); for (int i : list) { System.out.println(i); } // デバッグ用 // int x = 0; // int y = 0; // for (int i : list) { // if (i == 1) x++; // else if (i == 2) y++; // else if (i == 3) x = x + y; // else if (i == 4) y = x + y; // } // System.out.println(x); } }
ここまで81分36秒+0ペナ。290位。
この後は、DとEを両方見て見事にどっちつかずになって両方とも解けず。
Fは見てもいない。
Dは、上の桁から見ていって初めて1が奇数個出てきた桁は絶対に0にはできないが、それより下の桁の扱いをどうすればいいのかよくわからず。
Eは貪欲に気付ける可能性ゼロではなかったかもしれなかったが、時間が足りなすぎた。
最終結果:ABCの3完1500点、81分36秒、349位、パフォーマンス2027
レート変動:2080→2074(-6)
AとBで出遅れた割には浅い傷で済んでまずまずの結果。Cで救われた。
Eに十分な時間を使えなかったことが心残り。