はまやんはまやんはまやん

hamayanhamayan's blog

Between Two Arrays [エクサウィザーズプログラミングコンテスト2021(AtCoder Beginner Contest 222) D]

https://atcoder.jp/contests/abc222/tasks/abc222_d

前提知識

解説

https://atcoder.jp/contests/abc222/submissions/26480980

問題を眺めるとかなりDPな感じがする。
具体的には

  • mod 998244353
  • 先頭から数を決めていくと広義単調増加は1つ前しか見なくていい
  • 制約的に何となく

みたいな所からDP感を感じてDPで考えてみると解けると分かってくる感じ。

naive DP

※ lstはlast, nxtはnextのつもり。関数名とかと被ってしまうのでこんな表記にしてる

単純なDPから考えてみよう。
先ほども書いたが、先頭から数を決めていくと広義単調増加は1つ前しか見なくていいので、
DPの状態としては最後に何の数を選んだかという状態を含めておけばいいことになる。
なので、

dp[i][lst] := i番目まで数列が確定していて、最後の数がlstであるような条件を満たす組合せ

というのを計算すればいい。
dp[i][lst]からdp[i+1][nxt]に遷移を考えたときに、満たす条件は

  • lst ≦ nxt
  • a[i]≦nxt≦b[i]

の2つである。
これに気を付けながらDPを書いていくとO(N3)の解法が出来上がるはず。
https://atcoder.jp/contests/abc222/submissions/26480825
これが理解できるまでは最初の段階。

高速化

これを高速化していくことを考える。
前のnaive DPは遷移元を起点として遷移先に分配していくような「配るDP」から、
遷移先を起点として、遷移元を見ていくような「貰うDP」にまずは変化させよう。
一概には言えないが、この変換が高速化に役立つことが多々ある。
言葉では何とも説明しにくいのだが、以下のような実装に変化する。

https://atcoder.jp/contests/abc222/submissions/26480899

これを眺めると、最終的な更新で、[0,nxt]の区間和を取るような計算が要求されている。
これは累積和を作っておけば高速に処理することができる。
よって、別途累積和を作っておいて、毎回それを使うことにすれば大幅に計算量が改善でき、
O(N2)となって通る。

int N, a[3010], b[3010];
mint dp[3010][3010];
mint rui[3010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> a[i];
    rep(i, 0, N) cin >> b[i];

    dp[0][0] = 1;
    rep(i, 0, N) {
        rui[0] = dp[i][0];
        rep(lst, 1, 3001) rui[lst] = rui[lst - 1] + dp[i][lst];
        rep(nxt, a[i], b[i] + 1) dp[i + 1][nxt] += rui[nxt];
    }
    
    mint ans = 0;
    rep(lst, 0, 3001) ans += dp[N][lst];
    cout << ans << endl;
}

Swiss-System Tournament [エクサウィザーズプログラミングコンテスト2021(AtCoder Beginner Contest 222) C]

https://atcoder.jp/contests/abc222/tasks/abc222_c

解説

https://atcoder.jp/contests/abc222/submissions/26480601

シミュレーション問題、実装問題となる。
どういったことを問うているのかについては頑張って読み解いてほしい。
場合によってはサンプルを手計算でシミュレートすることも理解を助けるだろう。

問題を分割する

プログラミングにおいて一般的な話であるが、問題を小問題に分割することで
この問題に立ち向かうことにしよう。
各ラウンドでは

  1. 上位のユーザーから2人ずつグループにして戦わせる
  2. その後、これまでの勝敗を集計して、順位順に並びなおす

ということを行う。
問題の入力例1を使いながら理解を深めていくことにする。
あと、自分の実装と合わせるために、1 2 3 4ではなく0 1 2 3として説明していく。

1. 上位のユーザーから2人ずつグループにして戦わせる

順位を配列に入れておくことにしよう。自分はorderという名前で用意した。
最初の順位は0 1 2 3であり、これで上位2人ずつ戦わせていく。
勝敗は、どのラウンドかと、誰と誰の対戦であるかが分かれば決するので、それを引数としたbattle関数を用意した。
引き分けなら-1でそれ以外なら勝者を返す。
この中身は本当に根性実装なので、頑張って理解してほしい。

これで勝敗が分かれば勝者の勝ち点を+1すればいい。
win配列を用意して各人の勝ち数を記録しておくことにしよう。

2. その後、これまでの勝敗を集計して、順位順に並びなおす

どちらかというとこっちが問題である。
それほど厳しい制約でもないので、実装ができればTLEすることはなさそうだが、実装もちょっと大変かもしれない。
C++では、比較関数を自作したソートによって、これを簡単に実装することができる。

順位順に並びなおすというのと、特定のルール下におけるソート処理であると捉え、ルールを作る。
ルールは

  • 勝敗が違っていれば勝ち点が多い方が先に来る if (win[a] != win[b]) return win[a] > win[b];
  • 勝敗が同じであれば、番号が小さい方が先に来る else return a < b;

ということなので、これをソートの条件として指定する。
実装結果は↓にある通りなのだが、慣れないと少しパッと書くのは難しいかもしれない。
だが、このように特殊なソートをする場合にこれを使うことはよくあり、とても便利なのでこれを機に覚えるといい。

int N, M;
string A[101];
int win[101];
//---------------------------------------------------------------------------------------------------
int battle(int round, int userA, int userB) {
    char a = A[userA][round];
    char b = A[userB][round];

    if (a == b) return -1;

    if (a == 'G' && b == 'C') return userA;
    if (a == 'C' && b == 'P') return userA;
    if (a == 'P' && b == 'G') return userA;

    return userB;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;
    rep(i, 0, N * 2) cin >> A[i];

    vector<int> order;
    rep(i, 0, N * 2) order.push_back(i);

    rep(round, 0, M) {
        rep(k, 0, N) {
            int res = battle(round, order[k * 2], order[k * 2 + 1]);
            if (0 <= res) win[res]++;
        }
        sort(all(order), [&](int a, int b) {
            if (win[a] != win[b]) return win[a] > win[b];
            else return a < b;
        });
    }

    rep(i, 0, N * 2) printf("%d\n", order[i] + 1);
}

Max Sum Counting [AtCoder Beginner Contest 216 F]

https://atcoder.jp/contests/abc216/tasks/abc216_f

前提知識

解説

https://atcoder.jp/contests/abc216/submissions/25449760

DPが分かっていることは前提なので勉強してきてほしい。

何から始めるのか

手がつかない場合は問題の弱点を探るのが良い。
今回は条件のうち、maxの上限が5000である部分が弱点となりうる部分である。
maxの上限が5000であるということはBの総和の上限も5000まで考えればいいことになる。
この条件は考察するうえでとても有用な条件であるように見える。

まあ、ここまではいいとして、ここからちょっと思考の飛躍が必要となる。
条件のmaxの値は選択された値の中での最大値によって決まり、
「それより小さい数についてはどのように選択されても変化しない」
といえる。
ここがとても重要な部分で、この「どのように選択されても変化しない」という部分にDPの同一視が適用できそうである。
さて、小さい数について、細かな状態は無視したいので、配列をまずはソートすることにする。
AとBを1つのグループにまとめてAでソートしておく。
max, sumや部分集合の選択方法に順番は影響しないので、ソートしても答えは変化しない。
この状態でDPを考える。

DP定義

dp[i][Btot] := i番目まで選択が確定していて、かつ、「i番目を選択していて」、かつ、選択した要素のBの総和がBtotである組合せ

このDPを更新していくことを考える。
これを貰うDPで実装していくことを考えると、

dp[to][Btot]の更新はto未満である全てのcuに対してdp[cu][Btot - B[to-1]]の総和

が更新ルールとなる。
これをそのまま実装するとO(N2 Bmax)になるので間に合わない。
更新時に利用している値は、toを1から順番に計算していることを考えるとdp[to未満の全て][とある値]の総和を取得していることになる。
これは事前に計算することができる。
よって、
tot[x] := dp[これまで][x]の総和
と定義して、dp[to][any]の更新が終わった直後に、totにその値を入れることで、
dp[to][any]を更新→tot[x]を更新→更にそれを使ってdp[to+1][any]を更新→…みたいな感じに高速に計算ができる。
この辺は累積和を使った更新最適化と捉えることもできる。
https://blog.hamayanhamayan.com/entry/2017/03/20/234711

答えを取得する

これでdp[i][Btot]について考えると、maxの値はA[i-1]になっているので、BtotがA[i-1]以下であるものが条件を満たすものになる。
なので、全てのdpの要素dp[i][Btot]についてBtot≦A[i-1]である組合せの総和を取れば答えになる。

int N;
int A[5010], B[5010];
pair<int, int> AB[5010];
mint dp[5010][5010];
mint tot[5010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];
    rep(i, 0, N) cin >> B[i];
    rep(i, 0, N) AB[i] = { A[i], B[i] };

    sort(AB, AB + N);

    dp[0][0] = 1;
    tot[0] = 1;
    rep(to, 1, N + 1) {
        rep(Btot, 0, 5010) if (AB[to - 1].second <= Btot) dp[to][Btot] = tot[Btot - AB[to - 1].second];
        rep(Btot, 0, 5010) tot[Btot] += dp[to][Btot];
    }

    mint ans = 0;
    rep(to, 1, N + 1) rep(Btot, 0, AB[to - 1].first + 1) ans += dp[to][Btot];
    cout << ans << endl;
}

Amusement Park [AtCoder Beginner Contest 216 E]

https://atcoder.jp/contests/abc216/tasks/abc216_e

解説

https://atcoder.jp/contests/abc216/submissions/25449841

この問題は貪欲法で解ける。
勉強熱心な方はDPを思いついたかもしれないが、たぶん正常な反応だと思う。
貪欲法で解けそうな問題が実際はDPでしたというパターンも、逆のパターンもかなり見てきた。

今回は貪欲法の方針を見つけるのはそれほど難しくなく、実装がちょっと大変。

貪欲法の方針

貪欲法で解きますという風な前提があれば、その方針を見つけることはそれほど難しくないだろう。
楽しさを最大化するには、「各操作時に楽しさが最大のアトラクションを選ぶことを繰り返す」という貪欲をすればいい。
その貪欲法で問題ないかという見積もりをする必要があるが、パッと考えた感じ反例が思い浮かばず、
かなり自明な貪欲法に思えたのでそのまま突っ切って実装してACした。
正直これで何回も痛い目を見ているのだが、貪欲法の見積もりって難しいですよね…
基本DPから考えるといいと思います。で、不可能になったら貪欲法という感じで。

実装

さて、少し回り道をしたが、「各操作時に楽しさが最大のアトラクションを選ぶことを繰り返す」で貪欲法を実践する。
言われたまま実装をするとKの値は大きいのでTLEしてしまう。
大きい数を減らしていくと、次に大きい数と一致するときが来る。
この間は地道に-1するのではなく一気に減らすような工夫をすると貪欲法を高速化できる。
このように一定の操作が行われる部分については計算で省略をしながら高速に貪欲法をやっていく。
Aの値は大きい順で使用するので、降順ソートした上で、先頭から使用していこう。

サンプル1の例で考えてみよう。
先頭が102で次が100なので、その間の102+101が使用されることになる。
その次は、2番目が100でその次が50なので、100+99+98+...+51が使用されることになる。
ただ、2回目は1番目が2番目と同じ値にまで減らされているので(100+99+98+...+51)×2が使用される感じになる。
なので、基本的には(A[i] + ... + (A[i + 1] + 1))×(i + 1)を足していけばいいことになる。
iは0始まり、0-indexedで表記している。

このように等差数列の和を利用するので、自作のライブラリtousa_sumを持ってきて計算した。
高校生で「等差数列の和」は習うのだが、競プロやる中学生は知ってそうだな…
まあ、忘れている社会人含めて「等差数列の和」でググれば式は出てくるのでそれを使って実装すればいい。
自分の実装が気になるなら、提出URLに飛んで見てみてほしい。

半端な場合はどうする?

基本的には上記の方針でKを減らしていけばいいが、いつか中途半端になってしまう場合がある。
この場合には、これまでに数が揃っている個数分のA[i]が何回分同時に-1できるかというのを特定する。
これはKを(i+1)で割った答えdになる。
d回分は等差数列の和で計算する。
Kを(i+1)で割った余りmが、残った回数になるので、あとはその分だけ足し合わせて答えが出来上がる。

ll N, K, A[201010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> K;
    rep(i, 0, N) cin >> A[i];
    sort(A, A + N, greater<ll>());

    ll ans = 0;
    rep(i, 0, N) {
        ll diff = A[i] - A[i + 1];

        ll cnt = 1LL * diff * (i + 1);
        if (cnt <= K) {
            K -= cnt;
            ans += tousa_sum(A[i], -1LL, diff) * (i + 1);
        }
        else {
            ll d = K / (i + 1);
            ll m = K % (i + 1);
            ans += tousa_sum(A[i], -1LL, d) * (i + 1);
            ans += (A[i] - d) * m;
            K = 0;
        }
    }
    cout << ans << endl;
}

Pair of Balls [AtCoder Beginner Contest 216 D]

https://atcoder.jp/contests/abc216/tasks/abc216_d

解説

https://atcoder.jp/contests/abc216/submissions/25449941

貪欲法というかシミュレーションで解く問題。
今回は目標を達成するには、ボールが取り出せるならどんな順番でもいいので取り出していって、
最後に全部取り出せれば達成可能と判定する方針で実装していく。
なので、高速にこのことをシミュレーションしていくことを考える。

このように選択肢があるように見えて、どんな方針でやっても最適解になるような問題がある。
これも正当性判断が難しいですが、とりあえず選択肢が2つ以上あるときに、操作の順番を変えることで
有利な状況が作れそうかというのを例を作りながら確認していくしかないと思う。
点数を見て、実装が大変な系かなという判断を下したのかも。

高速シミュレーション

ボールを取り出す際に毎回筒を確認して、同じボールがあるかを探していく方針はN回取り出す必要があって、
雑に計算すると毎回M個の筒を確認する必要があるので、O(NM)は間に合わない感じがする。
なので、上手くメモを残しながら取り出せるボールというのを高速に取ってくるようにする。
以下、自分の実装について説明する。

以下のようなデータ構造を用意する。

que := 「現在取り出せる同色のボールの組」を集めたキュー
available[i] := 現在色iのボールが先頭にある筒の番号

例えばi番目の筒の先頭がA[i].front()であるとすると、
available[ A[i].front() ] = i
という風に更新することができる。
だが、更新時に既に値があった場合は、他にも筒の先頭に同じ色のボールがあるということになるので、
取り出すためにqueというキューに筒の番号を追加する
que.push({ i, available[ A[i].front() ] })
自分の番号iと、前もってメモっておいた同色が先頭にある筒の番号available[ A[i].front() ]をキューに入れている感じ。
この実装を

setAvailable(ai) := 筒A[ai]の先頭を評価する

として実装している。
キューを1つずつ処理していくことで同色の2組を削除していくが、2つの筒からボールが取り出されるので
その次のボールをsetAvailableでavailable配列の更新やqueへの追加を行っていく。
これでボールを取り出して、差分として新たに2つのボールが出てくるので、それと先頭が一致しているものがないか確認というのを
上手いこと差分だけを計算することで高速に処理していく。

最後に

シミュレーション後にすべての筒が空になっていればYes。
筒の先頭を評価するときに空の場合は無視することに注意。
あと、筒の管理にdequeを使っている。

int N, M;
deque<int> A[201010];
int available[201010];
//---------------------------------------------------------------------------------------------------
queue<pair<int, int>> que;
void setAvailable(int ai) {
    if (A[ai].empty()) return;
    if (0 <= available[A[ai].front()]) {
        que.push({ available[A[ai].front()] , ai });
    }
    else available[A[ai].front()] = ai;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;
    rep(i, 0, M) {
        int k; cin >> k;
        rep(j, 0, k) {
            int a; cin >> a;
            a--;
            A[i].push_back(a);
        }
    }
    rep(i, 0, N) available[i] = -1;

    
    rep(i, 0, M) setAvailable(i); {
        
    }
    while (!que.empty()) {
        int i1, i2;
        tie(i1, i2) = que.front();
        que.pop();

        A[i1].pop_front();
        setAvailable(i1);
        A[i2].pop_front();
        setAvailable(i2);
    }

    bool ok = true;
    rep(i, 0, M) if (!A[i].empty()) ok = false;

    if (ok) cout << "Yes" << endl;
    else cout << "No" << endl;
}

Many Balls [AtCoder Beginner Contest 216 C]

https://atcoder.jp/contests/abc216/tasks/abc216_c

関連知識

解説

https://atcoder.jp/contests/abc216/submissions/25449969

この問題は2進法についての理解があると解法が思いつきやすい。
このような構築問題は方針がいくつかあるが、Nを見ると計算量的にlogNでやらないとという感じがあるので、
このあたりから2進法が分かっていなくても解けるのかもしれない。
2進法についてはググって調べてきてほしいが、知らなくても解説は読める(はず)

操作を逆に見てみる

合計120回とあるが、とりあえず最適っぽい方針も立てられないと前進しない。
今回は実は操作を逆に見てみることで方針が立てやすくなる。
つまり、魔法Aを使うと-1されて、魔法Bを使うと÷2されることになる。

5 -A-> 4 -B-> 2 -B-> 1 -A-> 0

のような感じになるが、これは丁度順番を逆転させると元の問題に帰着される。
なので、NをA,Bの操作をして0になる様にやっていこう。

構築問題のルールはシンプルに

構築問題に共通で言えるアドバイスとして、なるべくシンプルなルールを採用することである。
複雑だと大体バグるし、ちょっと踏みとどまってシンプルなルールを探す方が期待値が高いことが多い(体験上)。
よって、シンプルなルールを考える。
以下のルールで今回はACできる。

  • 2で割り切れない場合は魔法Aをやる(魔法Aをやるしかないけど)
  • 2で割り切れる場合は魔法Bをやる

再掲すると、

5 -A-> 4 -B-> 2 -B-> 1 -A-> 0

これはこのルールで作られている。
どんな数であってもこのルールを適用することで0になることが分かるだろう。
答える前に魔法の打ち方を反転させるのを忘れずに。

120回に収まるのか?

なるべく回数を抑えるためには魔法Bを多く使うことが重要になる。
今回の方針で重要なのは魔法Aが連続することはないという部分である。
魔法Aをやれば必ず2で割り切れる状態になるので最低2回に1回は魔法Bが行える。
魔法Bを1回やれば2分の1以下にできるし、2回やれば4分の1以下にできるし、3回やれば8分の1以下である。
極端に小さくなっていくことが分かると思う。
実際はlogNになるというか、2進法のビット数分になるというか、具体的には60回くらいで0にできる。
で、毎回魔法Aを挟んでも120回くらいになって間に合うという見積もりである。

ll N;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    string ans = "";
    while (1 <= N) {
        if (N % 2 == 1) {
            ans += "A";
            N--;
        }
        else {
            ans += "B";
            N /= 2;
        }
    }
    reverse(all(ans));
    cout << ans << endl;
}

倉庫番ロボット [パソコン甲子園2020 予選 I]

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0436

解説

https://onlinejudge.u-aizu.ac.jp/solutions/problem/0436/review/5811448/hamayanhamayan/C++14

解くのにかなり手こずった。難しかった。
ちょっとだけ遠回りも記しておこう。

遠回り

ダイクストラで解けないか考えて実装までしたがTLEした。
xy座標が[0,300]の範囲の点を状態として、遷移は上下左右の4移動と、移動可能なななめ移動である。
ななめ移動部分は無限に行けそうに見えて、実は

  • とあるy座標に対してx座標が[0,300]のどれか
  • とあるx座標に対してy座標が[0,300]のどれか

のどちらかとなる。
なので、遷移は301×2+4になるので、状態数とそこからの遷移で考えると、まあ、間に合わないのだが、
aojなので間に合ったりしないかなーとか思ったが当然のようにダメでしたね…

方針はあってる

ちょっと他の解法見ながらズルをしながら考えると、遷移を貪欲に絞ることが求められるようだ。
最短経路を取る問題は始点から終点までピンと糸を貼るような問題になるので、
一旦戻るような遷移にはならない。
一旦戻って(見た目勢いをつけて)移動しているようなものは糸を引っ張るようにすると、
戻らない経路に移る。
よって、始点から終点まで移動する場合、必ず終点の方向に移動することになる。
具体的には、x0≦x1、y0≦y1であるときに、遷移(a,b)から(c,d)を考えると、
a≦cかつb≦dを満たすことになる。
これにより遷移が一方向になり、遷移によってループすることがなくなる。
つまり、ダイクストラというよりDPで計算ができるようになる。

実装に落とし込んでいく

ここまで分かれば、それほど難しくない。
必須ではないが、問題を簡単化するためにx0≦x1、y0≦y1となる様に座標を調整しておこう。
具体的にはx0>x1であれば、図面を反転させることで、位置関係を変化させずに大小関係を修正できる。
反転させると、座標が負の数になってしまうので、+301で平行移動して正の座標にしておこう。
301とするのは壁の場所を調整するためである。

DP

dp[y][x] := (x0, y0)から(x,y)に移動する最短距離

としてDPを計算していく。
移動は常に単調増加していく感じで実装する。

dp[y][x]からdp[y+1][x]とdp[y][x+1]に遷移する。
これに加えて、y座標が奇数であれば、棚の上側にいるので、右上へのななめ移動ができる。
x座標が奇数であれば、棚の右側にいるので、これも右上へのななめ移動ができる。
ななめ移動はsqrt関数をうまく使ってコスト計算をする。

dp[y1][x1]が答え。

int X0, Y0, X1, Y1;
double dp[305][305];
const int MA = 302;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> X0 >> Y0 >> X1 >> Y1;

    if (X0 > X1) X0 = - X0 + 301, X1 = - X1 + 301;
    if (Y0 > Y1) Y0 = - Y0 + 301, Y1 = - Y1 + 301;

    rep(y, 0, MA) rep(x, 0, MA) dp[y][x] = inf;
    dp[Y0][X0] = 0;
    rep(y, Y0, Y1 + 1) rep(x, X0, X1 + 1) {
        chmin(dp[y + 1][x], dp[y][x] + 1);
        chmin(dp[y][x + 1], dp[y][x] + 1);
        if (y % 2 == 1) rep(xx, x + 1, X1 + 1) chmin(dp[y + 1][xx], dp[y][x] + sqrt(1 + (xx - x) * (xx - x)));
        if (x % 2 == 1) rep(yy, y + 1, Y1 + 1) chmin(dp[yy][x + 1], dp[y][x] + sqrt(1 + (yy - y) * (yy - y)));
    }

    printf("%.10f\n", dp[Y1][X1]);
}