スクリーンショット_2019-12-22_22

ABC149:解けなかった問題EをACとるまでやってみたけど、コードを理解するまでむちゃくちゃ時間がかかった

12月29日に、競技プログラミングサイトAtCoderで開催された競技プログラミングコンテスト「AtCoder Beginner Contest 149」に参加した。

【今回の結果】
順位は約3670人中1514位(上位41%くらい)
レート:598(unretedのため変化なし)

今回も前回同様、問題 A、問題 B、問題 C、問題 D は正解でき、上位50%に入れたので、よかった。しかし、問題 B では、しょうもないミス 1 回、long long にすべき変数が int だったので 1 回の合計 2 回 WA を出してしまった。10分のペナルティは自分くらいのレベルだと順位にかなり影響を与える。焦ってやってもいいことないな。

問題 E を考えている最中に終わってしまったのだが、コンテスト後、年末だからか時間があったので、かなり背伸びして問題 E を考えてみた。

問題文はこちら

入力例1は以下の通りである。

5 3
10 14 19 34 33

A を並び替えると

10 14 19 33 34

となり、3回握手するとなると、
左:34 右:34 で 68
左:34 右:33 で 67
左:33 右:34 で 67
で、合計 202 となる。

数が少ないからいいものの、数が多くなるとどうしたらいいのだろう?というところで詰まってしまった。

解説と正解した方々のコードをを参考にして、作ったコードは以下の通り。
※自分流の解釈をコメントにつけています。

#include <bits/stdc++.h>
using namespace std;

int main() {

 long long N, M;
 cin >> N >> M;

 vector<long long> A(N);
 for (int i = 0; i < N; i++) {
   cin >> A[i];
 }

 sort(A.begin(), A.end());

 // --- M 通り以上の握手ができる最小の x を探す ---

 long long x = 0;
 long long ng = 100000 * N + 1;

 while (1 < ng - x) {

   long long mid = (x + ng) / 2;
   long long num = 0;

   for (int i = N - 1; 0 <= i; i--) {

     // A[i] で握手できる回数 =
     // Aの最後の要素番号 - (mid - A[i] 以上の要素のうちの最小の要素番号)
     num += A.end() - lower_bound(A.begin(), A.end(), mid - A[i]);

   }

   // num が M 以上の場合は、X を詰める
   // その逆の場合は、NG を詰める
   if (M <= num) {
     x = mid;
   } else {
     ng = mid;
   }

 }

 // --- 幸福度の計算 ---

 // 累積和であらかじめ集計しておく
 vector<long long> SUM(N + 1);

 for (int i = 0; i < N; i++) {
   SUM[i + 1] = SUM[i] + A[i];
 }

 long long answer = 0;
 long long count = 0;

 // x を超える幸福度を計算する
 // 左手で握手する人を A[i] とする
 for (int i = 0; i < N; i++) {

   // x - A[i] を超える要素のうち最小の要素を返す
   long long v = upper_bound(A.begin(), A.end(), x - A[i]) - A.begin();
   
   // 握手をする回数
   count += N - v;
   
   // 左手の幸福度は A[i] * 回数、右手の幸福度は累積和から計算
   answer += A[i] * (N - v) + SUM[N] - SUM[v];
   
 }

 // M - count で残りがあれば、それはすべて x となるパターン 
 answer += x * (M - count);

 cout << answer << endl;

}

ほぼ同じですが、提出したコードはこちら。

これで AC とれたが、コードを(自分流で)理解するのに数時間使った。が、何も見ずにこの問題をやれって言われても、多分まだ無理だわ。

2020年も過去問とかたくさん解いて少しでもできるようになろう。

この記事が気に入ったら、サポートをしてみませんか?気軽にクリエイターを支援できます。

ありがとうございます!
1
三重県伊勢市でiOS・AndroidアプリのUX設計・UIデザイン・実装、Webサイト、Webアプリの情報設計、UIデザイン、実装を行なっています。また、競技プログラミングに参加したり、読書をしたり、2羽の文鳥と遊んだり、写真を撮ったり、洋菓子を作ったりしています。

この記事が入っているマガジン

コメントを投稿するには、 ログイン または 会員登録 をする必要があります。