ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

MIS.W新歓コンテスト2020

自分の大学にあるサークルが主催するコンテストに参加しました。
自分のコードはまとめてここに上げてあります。問題の前から順番に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になったり、北区がKitaNorthに表記ゆれしたり、台東区TaitoTaitungで表記ゆれしたり、他にもいろいろあったりで大変でした。

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)/4P=N(N+1)/4 + 1の2パターンについて調べ、その平均を取ればよいです。

Dentaku

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

感想

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