yukicoder contest 443 概要

2024-08-30 21:20:00〜2024-08-30 23:20:00 (2h)のコンテストです。
参加登録などはありません。問題が公開されたら、回答を提出すれば大丈夫です。
誤回答によるペナルティーはありません。

# ナンバー 問題名 レベル 作問者 テスター Solved Fav
A 2862 NOT FOUND 404 yuusaan 寝癖寝癖 seekworserseekworser 149 0
B 2863 Base 10 Subsets 1 yuusaan 寝癖寝癖 seekworserseekworser 128 0
C 2864 String of yuusaan yuusaan 寝癖寝癖 seekworserseekworser 107 0
D 2865 Base 10 Subsets 2 yuusaan 寝癖寝癖 seekworserseekworser 97 1
E 2866 yuusaan's Knapsack yuusaan 寝癖寝癖 seekworserseekworser 71 0
F 2867 NOT FOUND 404 Again yuusaan 寝癖寝癖 seekworserseekworser 75 0
G 2868 Another String of yuusaan yuusaan 寝癖寝癖 seekworserseekworser 37 1
H 2869 yuusaan's Knapsacks yuusaan 寝癖寝癖 seekworserseekworser 41 0

コンテストセッター : yuusaanyuusaan

コンテスト情報

yuusaanこと「ゆ～」による単独コンテストです

今回のコンテストのテーマは「2問1セット」です！ 雰囲気が同じな2問を集めました(解法が同じとは言っていない)

ぜひ、ご参加ください！


各問題にはストーリーが付随していますが、問題を解くだけであれば読み飛ばしても大丈夫です。

全問題にて、C++及びPythonでのACを確認していますが、一部の問題では高速な言語の使用を推奨しています(該当問題には注意点としてその旨が記載されています。)。


コンテスト終了後VRC競プロ部にて解説/感想会を予定しております

VRC競プロ部について

「VRC競プロ部」はVRChatter・競プロer向けの「競プロを楽しく継続できる場」を目指しているコミュニティです！


過去のyuusaanによる単独コンテスト

yukicoder contest 432


裏話(問題をどう思いついたかなど)

ヒント集

A - NOT FOUND 404

ヒント1 Sが最大で100文字になるので、数字列を整数として受け取るのはあまり現実的ではなさそうです。
ヒント2 数字列を文字列として扱ってみましょう。
ヒント3 文字列であれば一部分を抜き出してそれが404と一致するかどうかを判定するのは容易です。


B - Base 10 Subsets 1

ヒント1 つまり、1文字/桁ずつ抜き取って大小関係を調べることができればよさそうです。
ヒント2 整数として考えた場合、一の位の値は10で割ったあまりを抜き出すことで求めることができます。
ヒント3 ある整数について、10で割って小数点以下を切り捨てたときの一の位の値はどうなるでしょうか？


C - Sring of yuusaan

ヒント1 まず、低レベルのゆ～文字列をいくつか実際に書いてみましょう。
ヒント2 書いてみたゆ～文字列たちに共通点はありませんか？
ヒント3 どうやらそのゆ～文字列たちはある文字列を繰り返しているようです。
ヒント4 より具体的には、ある文字列を繰り返してはいますが、最後だけ途中で終わっているようです。あとはどのレベルのゆ～文字列についてもこの性質が成り立つかどうかを考えましょう。帰納法を用いれば証明ができます。


D - Base 10 Subsets 2

ヒント1 当然、愚直に小さいほうから部分集合を挙げる方法ではTLEとなります。
ヒント2 桁ごとに値を決めることができれば間に合いそうです。
ヒント3

適当な部分集合である非負整数Bについて、部分集合であるという条件を満たしたまま値を増やせる桁を一つ選んで増やしてみましょう。

変化前のBと変化後のBはそれぞれ部分集合のうち小さいほうから何番目でしょうか？

そしてその何番目というのはどれくらい増加しましたか？



E - yuusaan's Knapsack

ヒント1 一見ナップサックDPそのものですが、少し工夫が必要なようです。
ヒント2 より具体的には、入れ方の個数を求める過程で、遷移によってあるDPテーブルの要素が多重に加算される状況を避けなければなりません。
ヒント3

つまり、ただのナップサック問題では$\mathrm{DP}[i][j] = ( i$ 番目の荷物まで見たとき、重さの合計が $j$ 以下)として

$\mathrm{DP}[ i ][ j ] = max(\mathrm{DP}[ i - 1][ j - w_ i ] + v_ i, \mathrm{DP}[ i - 1][ j ] ,\mathrm{DP} [ i ][ j - 1])$と遷移すれば答えを求めることができますが、

本問題では多重加算を防ぐため$\mathrm{DP}[ i ][ j - 1]$の遷移は避けなければなりません。

ヒント4 より具体的には、ある文字列を繰り返してはいますが、最後だけ途中で終わっているようです。あとはどのレベルのゆ～文字列についてもこの性質が成り立つかどうかを考えましょう。帰納法を用いれば証明ができます。


F - NOT FOUND 404 Again

ヒント1

Nの値が極めて大きいです。そして「N以下の正整数で条件を満たすものは?」という形式の問題です。

この手の問題にはお決まりのテクニックが存在します。

ヒント2 ずばり、「桁DP」というテクニックを用いれば本問題に正解できます。
ヒント3 ただし、$\mathrm{DP}[ i ][ j ][k]=(i$ 桁目まで見て、「確実に $N$ 未満かどうか」が $j$ (真/偽)で最後の二けたが $k)$だと定数倍が重くなりTLEとなります。$k$ に持たせる要素を少し工夫しましょう。


G - Another String of yuusaank

ヒント1 一見再帰で求めることができそうですが、それでは間に合いません。
ヒント2 ここで、レベルKゆ～文字列の長さをKを用いて表してみましょう。
ヒント3 どうやら、どのゆ～文字列も最初はいくつかyが連続するようです。
ヒント4 高レベルなゆ～文字列は $10^{15}$ よりもはるかに長いため素直に高レベルなゆ～文字列として扱う必要は無いかもしれません。


H - yuusaan's Knapsacks

ヒント1 さすがに全パターンを愚直に試す訳にはいきません。
ヒント2 本問題はDPが有効です。
ヒント3

制約をよく見てみましょう。$M\leq16$ というのは、DPに強い人ならピンとくる値ではないでしょうか？

ピンとこない場合は、EDPCの問題を見てみましょう。どれかの問題に $16$ という数が現れているはずです。

ヒント4

つまり、ビット列を利用した $O(3^M)$ のBit-DPです。

しかし、荷物の重さの合計を遷移のたびにいちいち計算しているとギリギリ間に合わないかもです。

そのうえ少し工夫をしないと荷物の入れ方を実際に挙げることはできません。

ヒント5 荷物の個数がとても少ないので、各荷物の選び方について、重さと価値の合計を事前計算するのは間に合いそうです。
ヒント6

荷物の入れ方はDPテーブルの値を更新した遷移を逆にたどれば求めることができます。

事前にどこから遷移したかをメモしておくとよいでしょう。