ABC416 参加記録（2完）とC・D問題の振り返り

土曜日の夜に実施された ABC416 は、残念ながら A・B の 2完という結果に終わりました。

C問題について

C問題は、文字列の並べ替えを C++ の sort 関数で時間内に処理できるという発想に至らなかったのが反省点です。
20分ほど粘って考えましたが、解法が見えず D問題に進むことにしました。

実際には、単純に文字列の配列をソートすることで答えに到達する問題だったようです。

問題概要

最大長さ10の英小文字の文字列が最大10個与えられ、その中から１～5個を連結してできる文字列をすべて列挙し、それら文字列を辞書順に並べ替え、指定された位置の文字列を出力するという問題です。

初見では、最大50文字の文字列が 10の5乗 通りもできるため、「辞書順に並び替えるのは時間がかかりそうだ」と感じ、またそもそも文字列を辞書順に並べる方法もすぐに思いつかなかったため、Ｄ問題に進みました。

しかし、公式解説 を確認すると、列挙された文字列のソートは標準のsort 関数で十分間に合うとのことでした。

解法の流れ

  1. 文字列の全列挙
    解説では DFS を使って全列挙していました。大変エレガントな方法で、マスタしたいですが、選べる数（1～5）は固定なので、泥臭くfor文で場合分けして回すことも可能です。
    例えば、5個選ぶ場合は次のように記述できます：

    rep(i, n) rep(j, n) rep(k, n) rep(l, n) rep(m, n){
    ans.push_back(a[i] + a[j] + a[k] + a[l] + a[m]);

    }

  2. ソート
    実際の計算量は以下のように見積もれます：

    • N: 10の５乗（組み合わせ総数）

    • L: 50（文字列長）

    • ソートの計算量: O(N×L×logN) ≒ 8.3×10の７乗　＜10の８乗
      → 十分間に合います（実際、C++では27msでACできました）。

  3. X番目の文字列出力

シンプルな全列挙＋ソートの問題だったので、ここは確実に取りたい問題だったと感じます。

D問題について

問題は、長さNの非負整数列 A, B と、正整数 M が与えられたうえで、Aを任意に並び替えたとき、A[i]+B[i] をMで割った余りの総和の最小値を求めるというものです。

最初に A, B を昇順に並べ、それぞれの和を計算 し、Mで割った 余りの総和を取る方法を試しました。
次に、Aは昇順、Bは降順という組み合わせも試しましたが、サンプルを通過できませんでした。

解説を読んで

公式解説 によると、

まず、余りの総和を最小化するということは、Ａ＋ＢがＭ以上になるペアの数Ｃを最大化する。そして、ＡとＢの総和からＣＭを引いたものが、最小の余りの総和となる。なので、順序としては、

  • Aを降順、Bを昇順にソート

  • Aの各要素に対して、Bの中からA+BがM以上となるものを順に試していき、ペアの数Ｃをカウントしていく。

という方法が解説されていました。この様子を図解すると下記のようになると思います。

 

この図で説明すると、A1+B1がＭ以上であるので、カウント１となり、次にA2に対して、B2を足しても、Ｍを超えないので、次のB3を持ってくるという具合に、和がＭを超えるＡ、Ｂの組み合わせが最大になるように処理を行っていきます。この場合ですと、Ｍを超える組み合わせは３になります。Ｍは８ですので、３×８＝２４をＡＢの総和から引くと、余りの最小の総和ということになります。

このように、「各ステップにおいて局所的に最適な選択をしていくことで、全体としても最適解に近づける」アルゴリズムを「貪欲法」と呼ばれます。単純な貪欲法は、Ｂ問題から出題されますが、貪欲法の応用問題は、Ｃ、Ｄ問題でもよく出るようです。

 

総括

今回のパフォーマンスは 273（灰色）、レートは 518（-26） と下がってしまいました。
ここ3回連続で2完が続き、最高レートから50以上ダウンしてしまいました。

実はこの土曜日、過去10回のACできなかった問題の復習を行うなどの対策を取っていたのですが、残念です。

 

対策するべきポイント

　文字列のソートの計算量

　ソートと貪欲法の組み合わせ

 

📎リンクまとめ