5完3WA。
やっててよかったCodeforces。
各問題
A - I Scream
与えられた条件をそのままif文で表せばいいだけの問題ですが、いつものA問題よりちょっと作業量が多かったですね。
B - Job Assignment
ちょっと手間取ったのですが、実は単純に2重ループを回して全探索すればよいです。
int ans = 1001001001; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (i == j) { // 一人で両方の仕事をやったときの作業量 : a[i] + b[j] if (ans > a[i] + b[j]) ans = a[i] + b[j]; } else { // iさんがA、jさんがBをやったときの作業量 : max(a[i], b[j]) if (ans > max(a[i], b[j])) ans = max(a[i], b[j]); } } } cout << ans << endl;
こんな感じで。
C - Squared Error
がんばって式変形します。
(n - 1) * (a_1^2 + a_2^2 + ... a_n^2) - 2*(a_1(a_2 + ... + a_n) + a_2(a_3 + ... + a_n) + ... a_(n-1) * a_n)
となります。
前半はよくて、後半部分で(a_2 + ... + a_n)
みたいになっているところは累積和を取っておけばO(1)で取れるので、トータルO(N)で計算できます。
D - Journey
「当たるまで引くときの期待値は確率の逆数」です。
なのでn/1 + n/2 + ... + n/(n-1)
が答えです。
何故かうっかりそれぞれの期待値を掛け算してしまい、1WA・・・。
E - Mex Min
こどふぉでおなじみのMEXさんです。
セグ木やsetなどを使って指定範囲内のMEXを管理していけばよいです。(範囲に加わった数のインデックス部分を加算、出ていった数は減算する)
自作のMEX管理用セグメントツリーを意気揚々と貼ったはいいものの、使い方を間違って2WAです。(はい?!
F - Digits Paradise in Hexadecimal
桁DPかなー、桁DPわからんなー、といっているあいだにコンテストが終わってしまいました。
まとめ
やっててよかったCodeforces。
ただ、わざわざMEX用にカスタマイズしたセグ木を作っているのに、使い方を思い出すのに時間をかけているようではだめですね。(ていうか、設計がそもそもの悪いかも・・・)