みんなのプロコン 2019 & C問題 ABC7 - ABC8
二回目のコンテスト参加。
結果は23分でABCの3完。
順位: 736th
パフォーマンス:1598
rating: 326 →815
D問題は全然ダメだった。
散歩の開始・終了位置をO(L^2)にしないで処理する方法がわからなかった。
正解はdpだったらしい。制約的にdpもありうるかもとは思ったが、
どうやったらいいのか検討もつかなかったので諦めていた。
"以上より、DP[i][t]: i 番目の耳まで見て、D,S,T,U のうち t 個の地点を既に通過したときのりんごさん
の必要な操作回数の最小値 として DP 配列を O(L) 時間で更新していくことで、この問題を解くことができます。"
いやグロすぎる。偶奇性に着目して処理するのはわかったが、
こういうdpの使い方の問題はまだやったことがない。
散歩の開始と終了位置を考えて…というのはo(L^2)になる気がしなかった。
そこをあらわに指定しなくても解けるのか…?
" DP 配列を O(L) 時間で更新していくことで、この問題を解くことができます。”
こちとらそこが知りてえんじゃ。
連結DPというクラスの問題らしい。一応典型問題？
可能な内部状態が複数あるときにdpしてくためのテクニック？
とにかくいろいろ解いて典型力をつけるしかない。
E問題ちら見だけしたが、数学だったらしい。
コンテスト中に問題文読んだときはAOJで見た2D window系の問題に近いかと思っていた。
計算量的にO(N^3) -> 行列計算？ まで発想が行けばという感じか。
一応、目標にしていたパフォーマンス1500超え & レーティング緑到達は果たせた。
前回のパフォーマンスが1518、今回が1598と、だいたい水色後半ぐらいの実力と思ってよいのかもしれない。ただ、参加回数が少ない現状で青を狙うには安定して2000近いパフォーマンスが要求されそう。やはり500点以上をしっかり解けるように。
今回のようにDが難しい場合、ABCの早解きでも1600ぐらいのパフォーマンスは出ることがわかった。これに追加でD問題が解けるとちょうど青に行けるぐらいの感覚。
C埋めがもうすぐ終わるのでD埋めで青レベルの力を付けたい。
次回パフォーマンス1518以上でrating1000到達。
次回2005以上でrating1200到達。次回水色はちょっと現実的ではないか。
もうABCは出なくてもという感じだが、参加回数を稼がないとレーティングが伸びないのであればあるだけ参加で。
ABC-C精進は、前日残していたABC9のデバッグがあったりでそれほど。
以下、コンテスト中のメモ。
D問題考察
偶数、奇数、0で状況が違う。
0で区切られたクラスターを考える。
左からi番目からj番目までのクラスターを使うとすると、
コストは、i-1番目までのAiの和 + j+1番目以降のAiの総和 +
i … j内でのコスト
クラスター内の値は偶数奇数の並びから計算できる。
-> クラスターが一般にO(L/2)個あるのでTLEしそう。
むずすぎる！ E問題もちら見したが無理そう。
順位表見た感じ、黄コーダーでさえ結構落としてる。
スタート位置を決めたときにどこまで言えるのか。
Aiの現在の値が最も大きいものを減らしていく？
最大のAiを持つものを左に切って値を減らすということを繰り返してみる。
-> サンプル1, 2についてはこれで通りそう。もう実装する時間はないが。
総ステップ数が Aiの総和を超えない範囲で上の動作を繰り返す。
Aiに達した時点で余った数字を振り分ける。
以下、今日解いた ABC-Cのメモ。
ABC8 614点
満点解法を狙うなら、N!について調べて…は不可能 (N<=100)。
各コインについて個別に考えてみると、最終状態で表になっているのは、
自分より左側にある、自身の約数の個数が偶数個の場合。
与えられたコインの中で、今見ているコインの約数になっていないものは無視して構わない。それがどのように並んでいようが影響は無い。
約数になっているコインを m1, …, mM、なっていないコインをk1,...,kKとすると、 M + K + 1 = N;
今見ているコイン C の位置についてループを回すことを考える。
Cの位置iについて、
i = 1: 必ず表
i = 2: M + K枚の可能な並べ方のうち、一番左がk1.,..,kKのいずれか
= (M+K)!通りのうち、左端のコインの選び方がK通りで K * (M+K-1)!
-> K/(M+K)
の確率で表になる。
i = j+1: 1…j枚のうち、m1…mMから偶数枚。
それを 2n 枚とすると、M_C_2n * K_C_(j-2n) * (j)! (M+K-j)!/(M+K)!
要するに、M_C_2n * K_C_(j-2n)/ {M+K}_C_j
原理的には、これを2n <=jについて和を取り、iについて和を取れば良いはず。部分点はこれで十分だろう。
ただし、M+K ~ 100とかでは分母、分子の計算自体が不可能では？
2nでなければ公式
が使えて分母、分子が打ち消して1になる。
偶数部分だけをどうやって引っぱり出してくるか。
-> doubleの最大値は1.797693e+308なので大丈夫そう。
二項係数をダイレクトに求められる。
-> 結果は正しいのだが、出力のformatingが違っていて部分点に。
cout << (double) hoge << endl;
はデフォルトでは「整数部含めて6桁」なので、許容誤差次第ではWAする。
printfで指定するようにしてAC。
安全策としては、doubleを使う問題では常にmainの最初に
cout<<fixed<<setprecision(10);
としておけば良い。
ABC7 404点
相変わらずbfsのコードを書くのが苦手。
一つだけTLEするテストケースがある。
解けることは保証されているはずなので、バグってる。
-> 迷路からのはみ出し判定の部分をいじってたらいつの間にかACできた。
