https://emtubasa.hateblo.jp/entry/2020/04/23/210517

自分の大学にあるサークルが主催するコンテストに参加しました。
自分のコードはまとめてここに上げてあります。問題の前から順番にa,b,...と振ってあります。自分のコードを動かすことができるeの入力データも添えました。
長いのでかなり端折る部分があります。
コンテストリンク

Mistale

$K = N$ か、 $F=N$ か、はたまたそのどちらでもないか、で場合分けをします。
サンプルに"Genocide"となるケースが存在しないので、

10 10 0 0

などと入力してチェックをしてあげたほうがよいでしょう。

Join MIS.W!

$P,C,M$ から、それぞれ $S_{i}$ で入力される人を引いていけば、最終的にすべてが0以下になっているかどうかで場合分けができます。

Okimochi Expression

$R$ の降順でソートし、得点が一番高い人について、"True"であれば(初期値が0の)カウントを+1,そうでなければ-1として、カウントが正か負かはたまた0になるか、で場合分けをします。

Random Card Battle

$O(Nmax(A_{i})$ が間に合うので、全ての $X$ について愚直に試してしまえばよいです。それぞれのカードについて独立なので、 $i$ 番目に勝てる確率の最大値について計算し、その総和を求めると答えになります。
$A_{i},B_{i}$ に対し、 $X_{i}$ を選択した場合、勝てる確率は
$max(A_{i} + X_{i} - max(A_{i} - X_{i} , B_{i} + 1) + 1, 0)$
です。出す可能性のある得点 $A_{i} + j$ を区間として見ると見やすくなるかもしれません。

SABAKAN FEVER

~~面倒な入力の部分必要だったのでしょうか~~問題自体はbitDPを用いて解けます。
$dp[S] = S$ の集合について、問題の条件に違反していないかどうか
とします。
それぞれについて愚直に見ると $O(2^{N}N^{2})$ かかってしまいますが、
とある集合 $S$ について、 $S$ から一つの要素を取り出して $i$ とした場合に、 $S\setminus i$ が問題の条件に違反してたら、その時点で $S$ も問題の条件に違反してしまいます。そうでなければ、 $i$ が、 $S\setminus i$ の要素と隣接していないかを調べることで、
$O(2^{N}N)$ に抑えることができます。
得点計算も愚直計算でそれぞれに対し $O(N)$ でできるので、全体で $O(2^{N}N)$ で解けました。
ちなみに、グーグル翻訳に投げてローマ字に直せばいいや、と思っていたのですが…
Google Translate

問題の指定ではしがsiなのに対し、翻訳ではshiになったり、北区がKitaとNorthに表記ゆれしたり、台東区がTaitoとTaitungで表記ゆれしたり、他にもいろいろあったりで大変でした。

Jewelry Construction

二人の持っている宝石を $p,q$ 個とします。よくよく考えると、 $p = q$ となるのは、 $p = q = k$ の場合のみです。それ以外の場合( $p \lt q$ とします)、最後に $p$ をA面に置いたのは明らかで、その結果 $q = pX + y$ となり、元々 $y$ 個だったのが $pX$ 個増えて $q$ 個になったのだとわかります。
ここで、 $y \geqq p$ の場合、この場合も明らかに最後に宝石が増えたのは $p$ をA面に置いた場合であり、 $y$ をA面に置いたターンは0倍であったことがわかります。
すると、0倍の操作については無視をして、 $q = pX + y (y \lt p)$ となるような $X$ の倍率で1回操作を行った、と考えてよいです。結局、 $y = q \% p$ になります。
これをお互い繰り返して行き、最終的に初期の条件、つまり $p=0,q= K$ になるかを調べればよいです。
この方法だと、初めに後手が $K$ 個、先手が $0$ 個持っているパターンが生じてしまい、 $K = 1,N =13,L=7$ のようなパターンで嘘解法になるように見えますが、この場合は、初手で $X = 1$ としてあげることで、上手く調整ができるようになっています。
これらの操作をうまくまとめると、結局 $GCD(L,N-L) = K$ であればOKです。 $L + K \gt N$ にのみ注意しましょう。

MIS.W scheduling?

実装が破滅しました(その1)。
曜日、時間は全て分になおします。
まずは、サークル活動に重複がないかを調べます。重複があり、この時点で $N$ 個すべてに参加できなければ"No"です。
次に、全体で参加できる数を調べます。 $N + M$ 個の区間について区間スケジューリングで調べればよいです。
最後に、今調べた個数に、サークル全てに参加しながらたどり着けるかを調べます。
サークルとサークルの空き時間それぞれについて、尺取り法のようにしながら、講義を入れられるかどうか区間スケジューリングで試していきます。
サークルについて、0分開始、0分終了および、inf分開始、inf分終了という2つの番兵を入れてあげると楽になります。
f:id:emtubasa:20200423153052p:plain

Taberungo

食べるリンゴ $M$ 個を決めたとき、それらを食べる順番は、明らかに $B$ が大きい順です。
なので、 $B$ でソートをします。
あとは、ナップサックDPのようにして解けばよく、

$dp[i][j] = i$ 番目までみて、 $j$ 個のリンゴを食べた場合に得られる満足度の最大値、とします。

$dp[i][j] = max(dp[i-1][j],dp[i-1][j-1] + A_{i} - B_{i}(j -1))$
で更新すればよいです。

Contiguous Subsequences

実装が破滅しました(その2)。
頑張って二分探索をします。
総和が $X$ 以下となるような連続部分列の個数が $P$ 個以上あるかどうか、については、しゃくとり法を用いることで $O(N)$ で調べることができます。
連続部分列全体の個数が奇数の場合は、 $P = N(N+1)/4 + 1$ として一度二分探索をすればよく、
偶数の場合は、 $P = N(N+1)/4$ と $P=N(N+1)/4 + 1$ の2パターンについて調べ、その平均を取ればよいです。

Dentaku

足し算によって区切られるので、掛け算について考えます。足し算も同様にすればよいです。
+で区切られる部分の連続する文字についての順列をまず考えます。
これはこんな感じで計算ができます。
次に、*を入れる箇所について考えてみると、文字が $n$ 個存在するときに、*は $n-1$ 個あります。
これらを左から並べていくときに、文字の個数 $p$ と*の個数 $q$ には、 $p \geqq q + 1$ という関係がなりたっていなければなりません。
左端は必ず文字なので、これを除くと、 $p \geqq q$ を満たすように文字と*を並べる並べ方を求めることになり、これはカタラン数そのものです。ということで、ここを参考に計算すればよいです。
+パートについてですが、+で区切られる文字列を1つの大きな文字と見てあげて、*と同じことを考えればよいです。
文字列について、辞書順ソート等できちんと並び替えることに注意すれば、この問題に答えることができます。
後は、計算した値の積を求めればよいです。

感想

実装で破滅した問題がいくつかあったので悔しいです。
典型っぽい考え方を使いつつ、面白い部分もたくさんあったので楽しかったです。
自分の中で400点問題と5,600点問題の難易度が逆転していました。