Educational Codeforces Round 81 解法

コンテストページ

Dashboard - Educational Codeforces Round 81 (Rated for Div. 2) - Codeforces

解法

✔A - Display The Number

桁数を最大にすることを考えると、'1' と '7' のみを使う以外の選択肢はありません。また、なるべく '1' を多くすると桁数が増えます。ひとつだけ '7' になることがあるのですが、それは一番上に持ってきましょう。一番下に持っていってしまった人がいるようですね。

✔B - Infinite Prefixes

場所と呼べそうなものは N 個あります。基本的にはそれぞれ高々 1 回しか日の目を浴びることが出来ません。大小比較をして、割り切れることも確認すれば合格です。

ただ、全体のバランスが 0 のときは答えが 0 になったり無限になったりしますから、注意です。

✖C - Obtain The String

t は貪欲に作っていけばよいですから、列を伸ばしていきながら、それが s の部分列になっていることがリアルタイムでわかればよいです。s に消極的にマッチしてきましょう。s の各場所で、各アルファベットが次にどこで出るのかを DPがです。

ところで、部分列は連結でないといけないと思った人がいるようですね。

✔D - Same GCDs

簡単枠です。Z/mZ の中で a と位数が同じものを数えればよいです。これは約数包除ですね。

✔E - Permutation Separation

これ好きです。置換をマス目 (i, p[i]) に書くと、解は格子点を選ぶことに対応していて、スコアはそこを起点に「斜めな」位置に書いてある点数の合計です。

i=0 の部分から順番に走査していきます。この部分は、a[P[i]] の累積和です。（P は逆置換です。）ここからそして、(i,p[i]) を通ると、p[i] 以下の部分が -a[i] されて、それより上の部分が +a[i] される感じになります。このように列を編集していいながら全体の Max を毎回取得していけばよいです。これは遅延セグで実現可能です。

なのですが、遅延セグを書きたくなかったので、頑張りました。隣接差を管理すると、作用すべき場所は定数個になります。マージは、その区間の総和とその区間の中での累積和の最大値のペアをノードにしておくことで実現できます。