MIS.W新歓コンテスト2020
自分の大学にあるサークルが主催するコンテストに参加しました。
自分のコードはまとめてここに上げてあります。問題の前から順番にa,b,...と振ってあります。自分のコードを動かすことができるeの入力データも添えました。
長いのでかなり端折る部分があります。
コンテストリンク
- Mistale
- Join MIS.W!
- Okimochi Expression
- Random Card Battle
- SABAKAN FEVER
- Jewelry Construction
- MIS.W scheduling?
- Taberungo
- Contiguous Subsequences
- Dentaku
- 感想
Mistale
か、か、はたまたそのどちらでもないか、で場合分けをします。
サンプルに"Genocide"
となるケースが存在しないので、
10 10 0 0
などと入力してチェックをしてあげたほうがよいでしょう。
Join MIS.W!
から、それぞれで入力される人を引いていけば、最終的にすべてが0以下になっているかどうかで場合分けができます。
Okimochi Expression
の降順でソートし、得点が一番高い人について、"True"
であれば(初期値が0の)カウントを+1,そうでなければ-1として、カウントが正か負かはたまた0になるか、で場合分けをします。
Random Card Battle
が間に合うので、全てのについて愚直に試してしまえばよいです。
それぞれのカードについて独立なので、番目に勝てる確率の最大値について計算し、その総和を求めると答えになります。
に対し、を選択した場合、勝てる確率は
です。出す可能性のある得点を区間として見ると見やすくなるかもしれません。
SABAKAN FEVER
面倒な入力の部分必要だったのでしょうか問題自体はbitDPを用いて解けます。
の集合について、問題の条件に違反していないかどうか
とします。
それぞれについて愚直に見るとかかってしまいますが、
とある集合について、から一つの要素を取り出してとした場合に、が問題の条件に違反してたら、その時点でも問題の条件に違反してしまいます。そうでなければ、が、の要素と隣接していないかを調べることで、
に抑えることができます。
得点計算も愚直計算でそれぞれに対しでできるので、全体でで解けました。
ちなみに、グーグル翻訳に投げてローマ字に直せばいいや、と思っていたのですが…
Google Translate
問題の指定ではし
がsi
なのに対し、翻訳ではshi
になったり、北区がKita
とNorth
に表記ゆれしたり、台東区がTaito
とTaitung
で表記ゆれしたり、他にもいろいろあったりで大変でした。
Jewelry Construction
二人の持っている宝石を個とします。
よくよく考えると、となるのは、の場合のみです。それ以外の場合(とします)、最後にをA面に置いたのは明らかで、その結果となり、元々個だったのが個増えて個になったのだとわかります。
ここで、の場合、この場合も明らかに最後に宝石が増えたのはをA面に置いた場合であり、をA面に置いたターンは0倍であったことがわかります。
すると、0倍の操作については無視をして、となるようなの倍率で1回操作を行った、と考えてよいです。結局、になります。
これをお互い繰り返して行き、最終的に初期の条件、つまりになるかを調べればよいです。
この方法だと、初めに後手が個、先手が個持っているパターンが生じてしまい、のようなパターンで嘘解法になるように見えますが、この場合は、初手でとしてあげることで、上手く調整ができるようになっています。
これらの操作をうまくまとめると、結局であればOKです。にのみ注意しましょう。
MIS.W scheduling?
実装が破滅しました(その1)。
曜日、時間は全て分になおします。
まずは、サークル活動に重複がないかを調べます。重複があり、この時点で個すべてに参加できなければ"No"
です。
次に、全体で参加できる数を調べます。個の区間について区間スケジューリングで調べればよいです。
最後に、今調べた個数に、サークル全てに参加しながらたどり着けるかを調べます。
サークルとサークルの空き時間それぞれについて、尺取り法のようにしながら、講義を入れられるかどうか区間スケジューリングで試していきます。
サークルについて、0分開始、0分終了および、inf分開始、inf分終了という2つの番兵を入れてあげると楽になります。
Taberungo
食べるリンゴ個を決めたとき、それらを食べる順番は、明らかにが大きい順です。
なので、でソートをします。
あとは、ナップサックDPのようにして解けばよく、
- 番目までみて、個のリンゴを食べた場合に得られる満足度の最大値、とします。
で更新すればよいです。
Contiguous Subsequences
実装が破滅しました(その2)。
頑張って二分探索をします。
総和が以下となるような連続部分列の個数が個以上あるかどうか、については、しゃくとり法を用いることでで調べることができます。
連続部分列全体の個数が奇数の場合は、として一度二分探索をすればよく、
偶数の場合は、との2パターンについて調べ、その平均を取ればよいです。
Dentaku
足し算によって区切られるので、掛け算について考えます。足し算も同様にすればよいです。
+
で区切られる部分の連続する文字についての順列をまず考えます。
これはこんな感じで計算ができます。
次に、*
を入れる箇所について考えてみると、文字が個存在するときに、*
は個あります。
これらを左から並べていくときに、文字の個数と*
の個数には、という関係がなりたっていなければなりません。
左端は必ず文字なので、これを除くと、を満たすように文字と*
を並べる並べ方を求めることになり、これはカタラン数そのものです。ということで、ここを参考に計算すればよいです。
+
パートについてですが、+
で区切られる文字列を1つの大きな文字と見てあげて、*
と同じことを考えればよいです。
文字列について、辞書順ソート等できちんと並び替えることに注意すれば、この問題に答えることができます。
後は、計算した値の積を求めればよいです。
感想
実装で破滅した問題がいくつかあったので悔しいです。
典型っぽい考え方を使いつつ、面白い部分もたくさんあったので楽しかったです。
自分の中で400点問題と5,600点問題の難易度が逆転していました。