PAST #1 の記事に続いて、今回も解説記事を書きます。

公式の解説がもう上がってた。早いね。

A - エレベーター

1F, 2F, 3F, ... を渡すと 1, 2, 3, ... に、B1, B2, B3, ... を渡すと 0, -1, -2, ... にしてくれる関数を考えます。

int neko(std::string const& s) {
  if (s[1] == 'F') return s[0] - '0';
  else /* if (s[0] == 'B') */ return -(s[1] - '1');
}

あとは、差の絶対値を求めればよいです。

B - 多数決

map<char, int> などを使って数えるとよいです。

C - 山崩し

s[i][j] が 'X' なら s[i-1][j-1], s[i-1][j], s[i-1][j+1] を見て、各々 '#' なら 'X' に書き換えます。i の降順にループしましょう。配列外参照には注意です。

D - パターンマッチ

文字列 s に文字列 t がマッチするなら true を返す関数を作ります。

bool match(std::string const& s, std::string const& t) {
  // t に '.' が含まれる場合は適切に分岐する
}

あとは、全パターンの t を三重ループなどで生成し、マッチした個数を数えればよいです。 t の長さが 3 未満でもよいことや、s の長さが 3 未満だった場合などには注意が必要かもしれません。

E - 順列

言われた通りの操作を実装します。特に説明するべきことはないような気がします。あったら教えてください。

F - タスクの消化

ai が共通な bi をまとめておきます。

int main() {
  int n;
  std::cin >> n;
  std::vector<std::vector<int>> b(n);
  for (int i = 0; i < n; ++i) {
    int ai, bi;
    std::cin >> ai >> bi;
    --ai;
    b[ai].push_back(bi);
  }

あとは、優先度つきキューを使います。 i 日目になったら b[i] の要素をすべてキューに入れ、最適なものを取り出せばよいです。

G - ストリング・クエリ

キューを使います。

クエリ 1 では、キューに (C, X) を入れます。クエリ 2 では、キューから (C, X) を取り出していきます。キューが空になるか、取り出した X の総和が D になったら終了です。総和が D を超えそうになった場合は、実際には取り出さずに、X の値を適切に書き換えます。

C++ の std::queue::front は先頭の要素の参照を返すので書き換えが簡単ですが、そういうことができない言語であれば、両端キューなどを使うといいかもしれません。

H - 1-9 Grid

簡単のため、'S' を '0' と書き換えちゃいましょう。

dp[i][j] を「a[i][j] 未満の数字はすべて順番通りに踏んだ状態で、マス (i, j) に来るための最小コスト」とします。 a[i][j] の昇順に更新していきます。

(i0, j0) を全探索して、a[i0][j0]+1 == a[i][j] なら dp[i][j] を dp[i0][j0] + abs(i-i0) + abs(j-j0) で更新できます。

a[i][j] == '9' な各 (i, j) について、そこからゴールマスへ行くコストを計算し、その最小値が答えです。

'S' のマスを書き換えたように、'G' のマスを '9'+1 で書き換えると、もっと簡単に書けそうです。

I - トーナメント

トーナメントをシミュレートするのが楽そうです。

m = 1 << n とします。 dp[m+i] = (i, 1) (0 <= i < m) で初期化し、i = m-1 から降順に更新していきます。 dp[i] には dp[i<<1|0] と dp[i<<1|1] の勝者とその勝ち数を入れます。

このようなトーナメント状の更新はセグ木と似ていますね。

J - 文字列解析

構文解析ですね。括弧でくくられた部分に対して指示された通りの加工をする、というのを再帰で書きます。構文解析の問題を解いたことがない人には難しいかもしれません。

...と思ったんですが、冷静に考えると、もっと簡単に解けそうです。「( で始まって括弧を含まず ) で終わる部分文字列を探し、その部分を適切に書き換えた文字列を生成する」というのを、括弧が無くなるまで繰り返すだけで解けそうです。毎回先頭から見直しても制約的に間に合うよね？

せっかくなので、構文解析の問題も解いてみましょうか。 ((1+2)*3)-4-(((5))-6) のような式の値を求めるコードを書いてみましょう。

書けたら提出してみてね。

今回の問題も、そういうのと似た方針で解けると思います。数式の計算では「括弧が出てきたらその中を計算する」としていたところを、「括弧が出てきたらその中の文字列を適切に加工する」とすればよいです。

K - 括弧

dp[i][j] を「i 文字見て、閉じられていない括弧が j 個ある状態にするための最小コスト」とします。 dp[i][j] からの遷移は以下の通りです。

操作しない：dp[i+1][j+p[i]] にコスト 0
反転させる：dp[i+1][j-p[i]] にコスト c[i]
削除する：dp[i+1][j] にコスト d[i]

ここで、p[i] は、s[i] が '(' なら 1、')' なら -1 です。また、j が負になるような遷移はできません。

初期化は dp[*][*] = inf, dp[0][0] = 0 で、答えは dp[n][0] です。

なんか、「なんでその DP を思いついたのかを説明してくれ」と文句を言われそうなんですが、飛躍はありますか？どうでしょう。

「前から i 個見て何がわかってるなら i+1 個見たときの答えと同じものを計算できるか？」というのを考えられるように訓練して、それを計算するにあたって必要な情報（のために必要な情報）は何か？というのを考えられるようになるとよさそう
— えびちゃん (@rsk0315_h4x) 2020年4月29日

基本はこんな感じだと思うんですが、「どの情報は同一視しちゃってもいいか？」みたいなのを意識するといいかもです。

L - 辞書順最小

重要なこととして、K 個の要素を選べる条件を考えましょう。これは、(K-1)*D+1 個以上の要素が残っていることと同値です。なので、N の初期値がこれ未満であれば不可能で -1 です。

この条件を念頭に置いて、考察を進めます。ふわっとした言い方をすれば、「たくさん取りたいのがあるなら、あまり後ろの要素を取っちゃだめだよー」ということです。

一つ目の要素は、[0, N-(K-1)*D) の中で最も小さいもの（複数あれば最も左のもの）を選ぶのがよいです。仮にそこから一番右を選んだとしても、二つ目以降で詰まないところを右端にします。辞書順を最小化したいので、先頭から貪欲に選びたいです。

ここで選ばれた添字を j とすると、二つ目の要素は [j+D, N-(K-2)*D) から選びます。この操作を繰り返していきます。

最小値の添字が欲しいので、(値, 添字) のペアの最小値を求めればよいです。これはセグ木や sparse table で求めることができます。

M - 食堂

一生バグらせた。えびちゃんの一生は一時間くらいです。

類題は ABC 156 F です。

好物が一回も出されない人はかわいそうです。

各種類のメニューに関して、次の二つのことを前処理で求めておきたいです。

周期一回分（D 日間）で何回出されるか
- そのメニューを好む人が、それを何回食べられるかに対応する
周期一回分でそれが出されない期間がどのくらいあるか
- そのメニューを好む人が、それ以外を何回食べることになるかに対応する
- 出される間隔 x と与えられた L の割り算を、各間隔について合計して求める

あとは、各人間に対して、「周期何回分を考慮すればいいか」「周期から溢れたところからどのくらい食べるか」を計算すればよいです。

周期から溢れた部分の計算については、上の前処理（累積和みたいにする）を用いながら二分探索するのがよさそうです。

周期モノの定石として、二周分持っておくというのがあります。こうすることで、「周期で割った余りでアクセスしなきゃ」とか「一周回ったからその分の寄与が〜」とかを気にしなくてよくなります。今回はえびちゃんは念のため四周分持っておきました。

境界の条件に気をつけながら実装しましょう。

えびちゃんは、最後の二分探索パートに関して「とりあえず愚直にやって、合ってるのが確かめられたら二分探索に書き換えよう」と思ってやってたんですが、愚直パートで一生バグらせました。諦めて二分探索を書いたら一瞬で終わったので後悔しています。冷静に考えると二分探索の判定の方がバグらせにくいよね。

N - ビルの建設

実家のような安心感。

水上位〜青下位くらいだと一瞬で「座圧して imos じゃん」からの「MLE/TLE じゃん」で一生終了するんじゃないですか？（たぶんね）

全部の x, y が異なるように座標を構成すると、そうした解法の最悪ケースになると思います。

さて、クエリを先読みして、平面走査することを考えます。 y の昇順に更新していきます。すなわち、y 軸方向については実際にメモリで持つのではなく、クエリの更新順という形で処理します*1。

(xi, yi, di, ci) の更新クエリに関して行うことは次の通りです。

y = yi になったら、xi から xi+di まで ci だけ加算する。
y = yi+di になったら、xi から xi+di まで ci だけ減算する。

また、(ai, bi) の求値クエリに関して行うことは次の通りです。

y = bi になったら、x = ai での値を求める。

以上の三種類の処理を適切な順に行うとよいです。境界を含むことから、各 y に対して加算→求値→減算の順になると思います。

あと問題となるのは、加減算のクエリだと思います。いわゆる遅延セグ木を持っている人はそれを貼ってもいいと思います。区間和を求めたいのではなく、値の取得なので、imos 法のようなイメージで普通のセグ木でもできます。

次の操作ができれば十分ですね。

[l, r) に x を足す
[i] での値を求める

これを、普通のセグ木の操作で言い換えます。

[l] に +x を足し、[r] に -x を足す。
[0, i+1) での和を求める

以上で解決です。

O - 可変全域木

え、これ大丈夫なんですか？

Educational Codeforces Round 3 E で既出で、当時書いたコードが 1 Byte も変えずに通るんですが...

まず、考察としては、次のようになります。

最小全域木のコストと、それを構成する辺集合を一つ求める
辺 (u, v) についてそれを含む全域木のコストを求める
上の辺集合に含まれるなら、上で求めたコストを答える
そうでないなら、がんばる

以下では、どうがんばるかを説明します。

最小全域木に辺 (u, v) を追加するとループができてしまうので、このループのうち最もコストの高いものを取り除きたいです。すなわち、やりたいことは「与えられた木において、u-v パスに含まれる辺のうち、重みの最大値は？」というのを求めることです。

HL 分解を貼れば終わりです。 HL 分解を持っていない人もいるでしょうから、それ以外の解法にも触れます。

LCA をダブリングで求めるアルゴリズムがありますね。それと同様に、「1 << i 個上の親までの辺のうち、重みの最大値は？」というのを前処理で求めておきます。 u と v の LCA を w とすると、u から w までと v から w までについて、それぞれパス上の辺の最大値が求められますから、その最大値が所望の値となります。

長かったね、お疲れさまです。

以上をこなして、満点です。

満点、よかったね pic.twitter.com/SEsK0Z7KTP
— えびちゃん (@rsk0315_h4x) 2020年4月18日

感想

3 時間を超えちゃったので FAKE です。M 以外は合わせて 2 時間くらいで済んだのにね。 M でバグらせまくったあとは「N/O 解けなかったらどうしよう」なんて思ってたんですが、N が実家で O が既出だったので助かりました。

O の所要時間は 2 分半弱です。さすがにそれで終わらせたらつまらないなと思って書き直したんですが、20 分くらいで書けたので、よかったかなと思います。

前回よりは 1 時間くらい更新したからよしとしようかな。

えびちゃんは解けたからいいけど、青上位でも結構つらい人いるんじゃないかなあ。いろんな分野のが出てるけど、苦手なのが二つ三つあるだけでエキスパートつらそうだもんね。

お前の使ってるエディタはクソ！カス！ゴミ！
— ながたかな (@ngtkana) 2020年4月17日

えびちゃんは普段 emacs で書いているんですが、前日ながたかなに煽られたので vim で解きました。そこまで不自由しなかったです。えびちゃんすごいね。

予想に関して

言ってなかったけど、LIS か LCS ちっくなのは出ると思ってたの。出ませんでした。

構文解析を見たときはびっくりしちゃったんですが、完全既出を見たときのびっくりには勝てませんでした。数え上げは今回も出なかったね。

中級以上の典型が今後もたくさん出てきそうだし、PAST の過去問が典型問題集として有効に使えそうになるんじゃないかなぁとか思っています。数え上げはあまり出てきそうな感じがしないけどね。

おわり

おわりです。

そすうさが満点取るまでえびちゃんが課金し続けなきゃいけなくなるやつじゃん
— えびちゃん (@rsk0315_h4x) 2020年4月18日

そすうさ早めに満点とってくれ〜

*1:空間に二次元を持たせるのではなく、空間に一次元・時間に一次元という形にする？

えびちゃんの日記

えびちゃん（競プロ）の日記です。

PAST アルゴリズム実技検定 #2 解説