金曜夜に開催されたエデュフォに参加しました。休み前なので参加しやすくて嬉しい。結果は AB/D 完です。

競プロ参戦記

この連載記事では、着手した問題の考察を自分なりに書いていきます。

問題の詳細はリンク先を参照してください。
前回: 競プロ参戦記 #38 Reversi | AGC 31

Educational Codeforces Round 62 (Rated for Div. 2)

問題一覧: https://codeforces.com/contest/1140

A. Detective Book

問題概要: N ページからなるミステリー本がある。すべてのページに新たな謎が現れて、i ページ目に現れた謎は a[i] ページ目に解決される。以下の手順で本を読むとき、最後のページまで読み終わるのに何日かかるか求めよ。

手順: まだ読んでないページを読む。これまでに現れたすべての謎が解決されたら、本を閉じる。そうでなければ、この手順を繰り返す。

考察:

シミュレーションで解けそうです。「これまでに出現した謎」の集合を M、「すでに解決された謎の集合」を R とおき、M が R の部分集合になるタイミングで日数をカウントする、というのを繰り返せばよさそう。

しかし集合が部分集合になるかどうかの判定は O(N) なので、何か工夫しないと O(N^2) 時間になってしまい間に合いません。以下のように考えると集合を使わずに判定できます。

ページ p まで読んだときのことを考えます。「これまでに出現したすべての謎が解決された」ということは、「すべての q (≤ p) について a[q] ≤ p」と表現できます。これは a[0] から a[p] の最大値を m とおくと、m ≤ p と同じです。

したがって、a[p] の最大値 m を更新しながら1ページずつ読んでいき、m ≤ p になったタイミングで日数を増やす、ということをすればOKです。

筆者の回答 (Rust, AC): https://codeforces.com/contest/1140/submission/51692723

B. Good String

問題概要: > と < からなる長さ N の文字列が与えられる。以下の操作を繰り返して、最終的に文字列の長さが 1 になるとき、この文字列は good である。いくつかの文字を削除して、この文字列を good にしたい。最小で何文字削除すればいいか求めよ。

操作: いずれかの > の次の1文字を削除する。または、いずれかの < の手前の1文字を削除する。

考察:

例えば ><> なら、左端の > に対して「次の1文字を削除する」操作を繰り返すことで ><> → >> → > のように1文字になるので、これはもともと good です。

一方 <<>> はどのように操作しても中央の <> を削除できないので good ではありません。また、どの1文字を削除しても good にはなりません。<< と >> のどちらかを削除すると good になります。

< で始まる文字列は、< の次の文字を削除できないので good ではないことが分かります。(同様に > で終わる文字列もダメ。)

逆に、文字列の先頭にある < をすべて削除して > で始まるようにすると good になります。(同様に末尾の > を削除しても good できる。)

したがって、文字列の先頭に連続して出現する < の個数と、文字列の末尾に連続して出現する > のどちらかを削除するのが最小です。

筆者の回答 (Rust, AC): https://codeforces.com/contest/1140/submission/51698090

C. Playlist

問題概要: N 個の曲がある。i 番目の曲は長さ t[i]、美しさ b[i] である。ここから 1 曲以上 K 曲以下を選ぶ。選ばれた曲の長さの合計を sum_t、美しさの最小値を min_b とするとき、sum_t * min_b 点のスコアを得る。最大のスコアを求めよ。

考察:

以前に AtCoder で似たような問題を見たので、おそらく「美しさ min_b を全探索」するのだろうと見当がつきました。

仮に選ぶ曲の中で美しさの最小である1曲が決まったとして、その美しさを min_b とします。残りの曲は美しさが min_b 以上の曲から選ばなければいけませんが、この選考基準は簡単で、とにかく長い曲を最大 K-1 個選ぶのがベストです。

まず長い順に (長さが同じなら美しさが大きい順に) K 曲選び、このときのスコアを計算します。

ここで選んだ曲の美しさの最小値を b すると、このスコアは、スコア計算式の min_b が b であるケースでの最適解です。

min_b が b 以上であるすべてのケースを試していきます。美しさが b の曲をすべて除外して、次に美しさが小さい曲を1曲確定します。「選ぶ曲の中で美しさの最小である1曲が決まった」ので、曲数が足りないぶんは長い順に選べばいいです。

これを繰り返すと、min_b の各値におけるスコアの最大値が計算できます。

問題は実装です。

曲を長い順に選ぶときと美しくない順に選ぶときの2通りがあります。これは曲のリストを複製して各々ソートすればできますが、今回は2つのヒープを使うほうがシンプルだと思います。

計算量の都合で、選択している曲の集合の性質を変数に持ち、追加・削除の際に適切に更新します。

曲数: K と比較するため
曲の集合: 同じ曲を複数回追加しないため
長さの合計: スコアを O(1) で計算するため

筆者の回答 (Rust, AC): https://codeforces.com/contest/1140/submission/51750396

反省:

本番では実装をバグらせてしまって、間に合いませんでした。もっと簡単な解法もありそう。

D. Minimum Triangulation

問題概要: n 角形が与えられる。各頂点には 1 から n のラベルが反時計回りに割り当てられている。この多角形の頂点を3つ線分で結んで三角形を作る。このような三角形を互いに重ならないように複数作って、多角形を覆った。三角形の頂点のラベルの積を三角形の重みと呼ぶ。三角形の重みの総和の最小値を求めよ。

制約: 3 ≤ n ≤ 500

考察:

最終的に三角形で覆ったとき、多角形の頂点 1, n といずれかの頂点 x からなる三角形があります。この三角形によって多角形は3つの領域に分割されています。辺 1-x に接する領域に注目します。

領域は「ある三角形の辺で多角形を分割したとき、三角形の内側ではない方」という形で表現できるので、その辺の両端の頂点で表すことにします。つまりいまは領域 (1, x) に注目しています。

この領域も三角形で覆われていて、頂点 1, x と、その間にあるいずれかの頂点 y を使った三角形があるはずです。この三角形によって領域は3分割されていて、三角形の外側である2つの領域は領域 (1, x) と同様なので、再帰的に考えれば解けます。

つまり dfs(x, y) = 「領域 (x, y) を三角形で覆うときの最小の重み」としてメモ化再帰すれば、状態 O(N^2)、遷移 O(N) なので全体として O(N^3) 時間で解けます。

筆者の回答 (Rust, AC): https://codeforces.com/contest/1140/submission/51712448

今回の教訓

A: 与えられた条件を式で書くと整理できるかも
C: いずれかの変数を全通り試すといいかも