3/4の21:00から開催されたAtCoder Beginner Contest 089と3/5の0:35から開催されたCodeforces Round #468(div2)に参加しました 備忘録も兼ねて解法まとめます
解法
ABC089-A
n/3で切り捨てるだけ COUT(IN()/3);とかprint int<>/3とかですね
Submission #2159783 - AtCoder Beginner Contest 089
ABC089-B
"Y"が存在したらFour,ないならThreeを出力 実際はset使って通しました
Submission #2153671 - AtCoder Beginner Contest 089
ABC089-C
頭文字が"MARCH"のどれかで始まる人をカウントして全列挙53で通す
Submission #2155406 - AtCoder Beginner Contest 089
ABC089-D
愚直にやるとDが1の時などでTLEを起こすのでメモ化
costs[i][j]:i番目から始めてj回移動した時にかかる総コスト として、これを適当に書いてみます
既に探索済みのものにはflagを立てて計算量を落としたり、iの値をdで割った余りを取るとといい感じになります
Submission #2158302 - AtCoder Beginner Contest 089
Round #468(div 2)-A
差をとって2で割っていい感じにやる
Round #468(div 2)-B
計算量に余裕があるのでcou=2から始めて一回ごとにcou<<1をしつつfor(i=0;i<n;i+=cou)で全探索してみる
i<=a,b<i+couならそこで終了 cou==nになったらFinalですね
Round #468(div 2)-C
条件を見ていくとmax-min==2の時以外は入力された値をそのまま出力すればいい事がわかるのでそうします
max-min==2の場合は中央方向に寄せるパターンと端へ寄せるパターンの二つだけ考えればよいので、両方試してより良い方を選べばよいです
Round #468(div 2)-D
えーMLEでした つらい
この問題で与えられるデータは頂点1から伸びる有向木と考える事ができて、DFSなりDijkstraなり適当な方法を使って頂点1からの距離の列挙ができます
また、ある頂点において時間iにリンゴがいくつ存在しているかを調べる事は、頂点から出ている辺の先にある頂点において時間i-1に存在しているリンゴの数の総和の偶奇を取ることで可能です
頂点1からの距離が長い順にsortした後にその頂点から伸びている辺を見つけて、各時間ごとにxorを取る(偶奇を見る)事で、ある時間にその頂点にリンゴが存在するかどうかが分かります。
ここで大問題なのですが、このデータの確保方法だと頂点一つ辺りの計算量が最悪O(N)かかってしまいます これでは通らないのも当然ですね かなしい
多分嘘解法なのでちゃんと解き直そうね(自戒)
ただ深さごとに偶奇見ればいいだけじゃねぇか！！！！！！
結果
ABCは62分全完でWAなし、結果は212位(Rated内72位)でパフォ1515でした
レートは1032➔1101(+70)なので、順調に行けばあとRated二回で水色になれますね(なりたい)
A問題は21秒ACでFA、ABC087から3連続でA問題のFAを出せているので非常に嬉しいです
Codeforcesは3完2555点、Hackなしで957位でした システムテストで落とさなかったのが良かったです
D落としたのはクッソ辛いですね なぜ分からなかったのか…ただのアホじゃん
