ABC162振り返り

今回から復習もかねてAtCoderのコンテストの振り返りをnoteに書いていきます。

ABC162終わっての自分のレートはこんな感じです。

たくさんサボってる時期がありますが、近いうちに青色になれたら良いなあと考えています^ ^

コンテスト中

A~D問題を順番にといて提出するも全てCEになっていて焦った。
いつもは言語がデフォルトでC++になっていたが、今回はなぜかCになっていた。
理由が分からず戸惑っていたが、5分ほどで気づいてACした。

E問題はN=3,K=6までの時を紙に書いて数え、gcd(A_1, .. A_N)の数値をそれぞれ考えるという思考には至ったものの、小さい方から数えようとして詰まっていました。

その後F問題を見てなんとなく解けそうな気がして取り組む。
しかしとっかかりが見えず、両方解けないまま終わってしまいました。

コンテスト後

できなかった問題E、Fに関して、

E問題

E - Sum of gcd of Tuples (Hard)

K,K-1,......1と大きい方から見ていけば、最大公約数がそれぞれの時の出現回数が把握できる。

累積和を取りながら、逐次それぞれの最大公約数の出現回数を計算していく。

計算量は、K^NにO(K logN)でそれぞれの最大公約数の累積和から引く時の処理でO(K logK)で解ける。

振り返ってみると簡単に感じる。

F問題

F - Select Half

DPで解ける。
DPで解けると言われたらDPで解けそうであることはすぐにわかりました。

そんなに飛ばしたらfloor[N/2]個の整数を選べないのでいくつかの状態を次に引き継ぐ形になりそうです。

しかし、実際に処理してみようと思うと結構時間がかかりました。

dp[i][j] (i個の中からj個とった時の要素の和の最大値)というベクトルor配列を取れればすんなり計算できるのですが、状態数が多くてメモリが足りなくなりました。

i個目の整数をとっているか否かで別のdpをとり、iに対してi/2個かi/2+1個かで状態を保存しながら進めていく形で解けました。

for(ll i = 1; i < N; i++){
   if(i % 2 == 1){
     //notで遅れ
     dpnot[i][0] = max(dpnot[i-1][0], dptake[i-1][0]);
     //takeして進んでいる
     dptake[i][1] = dpnot[i-1][0] + a[i];
     //notして進んでいる
     dpnot[i][1] = dptake[i-1][1];
   }
   else{
     //takeで遅れている
     dptake[i][0] = dpnot[i-1][0] + a[i];
     //notで遅れ
     dpnot[i][0] = max(dptake[i-1][1] , dpnot[i-1][1]);
     //takeで進んでいる
     dptake[i][1] = dpnot[i-1][1] + a[i];
   }
 }

んーこれがコンテスト中に解けるくらいになれたら良いなあ