記録帳

クラウド、データ分析、ウイスキーなど。

AtCoderコンテスト_ABC268_C-Chinese Restaurant解説

皆さんこんばんは。ABC268お疲れさまでした。
最近、C問題が難しくないですか?
今回も私は難しいと思ったのですが、時間内に何とか解けたのがうれしかったので、解説記事を出します。

C問題の概要

C - Chinese Restaurant

問題文は↑からどうぞ。
この問題は、結局のところ
「全ての料理p_iの中で、目の前の人の番号が、料理p_i自身の数-1~+1に収まっている個数が最大となるものを求めよ」
というものでした。

例えばこの場合。
赤文字の、料理は①で人が2の場合は、±1以内なのでOKです。
逆にそれ以外は、2以上離れているのでNGで、当てはまる合計数は1となります。

次に、このテーブルを反時計回りに1つずらしてみるとこうなります。
右上の料理が⓪で人が5の場合は5離れているように見えますが、料理⓪の-1はまた5に戻るようにするため、人5,0,1のどれかであればOKです。
今回の合計数は3となります。

このように考えたとき、合計数の最大値を求めるのが今回の問題です。
普通に考えると、テーブルを1つずつずらしていき、それぞれの合計数を求めていけば答えが出そうです。
ただ、そうすると計算量がO(N^2)となってしまいます。
今回、3 <= N <= 2 * 10^5 であるため、それだと計算時間に間に合いません。

解法

まず、例えばN=6の場合を考えます。
そして、料理が
[2, 1, 5, 0, 3, 4]
である場合を考えます。
こんな感じですね。
料理①の人1、料理③の人4、料理④の人5の3つが±1以内になっています。

さて、これを、2次元の表で表してみます。
横軸が料理の番号、縦軸が人です。
料理は[2, 1, 5, 0, 3, 4]であるため、そのセルが塗りつぶされています。
[2022/9/28追記 これ以降の縦軸と横軸について、人と料理が逆です。横軸が人で縦軸が料理番号となります。]

今回は料理の数の±1までOKなのでした。それを考慮して色を塗るとこうなります。

こうなった時、±1以内になっている料理というのはどれを指すでしょうか?
すでに±1までセルを塗っているので、今回の状況に当てはまるのは、料理と人が同じ番号であるとき、つまりは左上から右下に伸ばした直線上にセルが塗られていた場合です。

少し上に戻って、今回適しているのは3通りだったことを確認してみてください。
>料理①の人1、料理③の人4、料理④の人5の3つが±1以内になっています。
この3つが表で表現されていますね。

ここまでは、ある特定の場合のみでした。
今回の問題は、テーブルを逆時計回りに回転できます。
1回転させた場合がこちらです。

反時計回りのため、全体的に1列右にずらしています。
これも同じく線を引くと、2つの場合が±1以内になっています。

さらに1つずらすとこうなります。

つまり、このように1つずつずらしていって、左上から右下に直線を伸ばした時の数を数えて、一番多いものを出力すれば答えとなります。
ここからは、どうやってプログラムに落としていくかを考えます。

まず、1つずつずらすのはプログラムで表すのが難しいですよね。
どうにか、最初の初期状態の表から考えられないものか。。。
そこから、表全体をずらすのではなく、直線自体をずらせばよいのでは?という発想に行きつきます。
つまり、こういうことです。

こうすれば、初期状態を作ってしまえば、あとはこの直線をループで回せば処理できそうです。
ただ、この直線は斜めになっているため、いまいち扱いにくいですね。
なんとか横方向の直線にしましょう。

一つ上の図とよく見比べてみてください。
p_0の列はそのまま、p_1の列は1つ上にずらす、p_2の列は2つ上にずらす…とずらしています。
つまり、p_iの場合iだけ上にずらせばいいですね。
あとは、この直線の数(=人の数)だけループを回せば最大値を得られます。
以下に、自分が書いた実装載せておきます。

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <numeric>
#include <iomanip> 
#include <string>
using namespace std;
#include <map>


int main()
{
    int n;
    cin >> n;
    int p[n+10];
    for (int i=0;i<n;i++) cin >> p[i];

    int table[n+10];

    // 表で表す
    for (int i = 0; i < n; i++) table[i] = 0;
    for (int i = 0; i < n; i++) {
        int p_0,p_1,p_m1;
        // 直線を斜めから横にするため、iだけマイナスする。
        p_0 = p[i]-i;
        p_1 = (p[i]+1)%n -i;
        p_m1 = p[i]-1 -i;
        // 0未満の場合の処理
        if (p_0<0) p_0+=n;
        if (p_1<0) p_1+=n;
        if (p_m1<0) p_m1+=n;

        table[p_0]++;
        table[p_1]++;
        table[p_m1]++;
    }

    // 最大値を調べる
    int M = 0;
    for (int i = 0; i < n; i++) {
    if (M < table[i]) M = table[i];
    }

    cout << M << endl;


}

atcoder.jp

感想

dpとかいもす法とかが頭の片隅に入っていて、とりあえず2次元の表で考えられないか、と考えるようになっていました。
そこで、なんとか表にして、ずらして、あとは足し算する方法を思いついて、きれいに整理できたので記事にしてみました。
Dの文字列のやつは全く解けなかったので、何とかDの領域も解けるようになっていきたいです。