ABC163振り返り

ABC163の振り返りをします。

結果はこんな感じでした。
Unratedになってしまったのでレートの変動はなかったです。

コンテスト中

A~Dを40分で解き終わりACしているのを確認しました。

C問題
mapを利用してかけました。
mapは最近やっと使えるようになりました。
AtCoderのC++解説のページも勉強になっていました。

C++入門 AtCoder Programming Guide for beginners (APG4b) - AtCoder

自分がわかっていなかったところは
2.04参照
3.04構造体
4.04イテレータ
4.05ポインタ
です。

D問題
初めは最大のあまりを求めるのかと誤読していました。
それぞれの選ぶ個数についての和の種類を求めればいいと気づき、和の種類は最大値と最小値の間なら任意の整数を取れると考えて解けました。

ここまでは比較的スムーズにできたと思っていました。

E問題
しっかりとした解法を整理しないままコードを書き進めて泥沼にハマってしまいました。
端っこにすべき数字を求めるために、それぞれの端からの累計より大きかったら端にすればいいのか..などと考えていました。

F問題
触らず

コンテスト後

F問題は難しそうなので、E問題に関して

E問題

E - Active Infants

大きい数字からどちらの端に移動させるか順番に考えていけば解ける。
よって、
DP[i][j]を左側i個、右側j個の移動が決まっている状態での嬉しさの最大値と定めて更新していけばいい。

dp[i][j] (i+j = N)の中で最大の値が求める値になる。

rep(i,N+1){
   rep(j,N+1){
     if(i == 0){
       dp[i][j+1] = dp[i][j] + a[j].first * abs(a[j].second - (N-j) );
     }
     else{
       if(j == 0){
         dp[i][j] = dp[i-1][j] + a[i-1].first * abs(a[i-1].second - i );
       }
       else{
         // 左側or右側 a[i+j-1]の追加 左側はすでにi-1こ、右側はすでにj-1こ
         dp[i][j] = max(dp[i-1][j] + a[i+j-1].first * abs(a[i+j-1].second - i) ,
             dp[i][j-1] + a[i+j-1].first * abs(a[i+j-1].second - (N-(j-1) ) ) );
       }
     }
   }
 }

んーなんだかんだ方針が思いついても実装に時間がかかりそう...
9分台でできている人もいますが、どうなっているのか笑

次回もあるよ^ ^