A. Drinks Choosing

問題文の読解が難しかったです。2 人を割り当てられるドリンクから貪欲に取っていけば良いです。

B. Sport Mafia

飴を食べるタイミングはいつでも良いです。飴を x 個食べたとすると最終的な飴の数は、\( \frac{(n-x)(n-x+1)}{2} - x \) となります。これが k となるような x を全探索すれば良いです。

C. Basketball Exercise

DP をして欲しそうな顔をしています。DP[i][j] := i 列目まで見て、最後に j 行の選手を選んだときの身長の総和の最大値　でいけます。

D. Submarine in the Rybinsk Sea

各要素が総和にどのように寄与するかを調べます。典型ですね。ある要素の下から 1 桁目は、演算の結果、下から 1 桁目になるか、2 桁目になるかのどちらかで、それぞれ n 回発生します。ある要素の下から 1 桁目の数を x とすると、\( n(10x + x) \) が総和に足されることになります。全ての要素の下から 1 桁目について同じことをします。これで各要素の下から 1 桁目の寄与は確認できました。次に、2 桁目でも同様にして、\( n(1000x + 100x) \) を総和に足します。ただし、2 桁目が存在しない要素は特別に処理します。2 桁目が存在しない要素と存在する要素で演算を行うと、存在する要素の 2 桁目以降はそのまま総和に寄与することがわかります。これを全ての桁数分確認します。最初に要素を降順にソートしておくと簡潔に書ける気がします。
きれいに実装できた気がします。

int main()
{
  int n; cin >> n;
  vi a(n);
  rep(i,n) cin >> a[i];
  sort(a.begin(), a.end(), [](int x, int y){
    return x > y;
  });
  mint res;
  mint b(1);
  int m = n;
  while(a[0] > 0) {
    mint sum;
    int cnt = 0;
    rep(i,m) {
      int tmp = a[i] % 10;
      res += mint(m) * (mint(tmp) * b + mint(tmp) * b * mint(10));
      a[i] /= 10;
      if(a[i] == 0) {
        cnt++;
      }
      else {
        sum += mint(a[i]);
      }
    }
    b *= mint(100);
    res += mint(cnt) * sum * b * mint(2);
    m -= cnt;
  }

  cout << res.x << "\n";

  return 0;
}

E. OpenStreetMap

範囲の最小値なので、セグ木がまず思いつきます。2 次元はめんどくさいので 1 次元に落とし込みます。典型ですね。(x, y) を左上に置くような範囲における最小値は、\( min( min ( h[i][j] | y \leq j < y+b ) | x \leq i < x+a) \) となります。先に、全ての場所で横向きにサイズ b の範囲の最小値をとって記録しておくとやりやすいです。セグ木でやると TL が微妙な気がしたので、スライド最小値を使いました。ほとんど書いたことがなかったので、適当な記事を見ながら書いて、いい練習になりました。セグ木でやると落ちるんでしょうか？私、気になります！

F. Geometers Anonymous Club

幾何。わからないし、時間もなかったのでとりあえず錆び付いた幾何ライブラリを使ってやろうと思い、愚直解を書きました。が、サンプルも合いません。終了。

感想

最近やばい実装方針で進めて爆発することが多かったので、簡潔な実装を意識してやりました。D2 ではちゃんと簡潔にできて良かったです。

現代の量子力学

主に精進の様子を記録する日記帳です

Codeforces Round #574 (Div. 2) A~E メモ