00:04
ユニークビジョンプログラミングコンテスト2022）
AtCoder Beginner Contest 248）
A問題、ラックドナンバー。
問題文、数字のみからなる長さがちょうど9の文字列Sが与えられます。
Sには0から9までのうち、ちょうど1つの数字を除いた9種類の数字が1つずつ登場します。
1度ずつですね。Sに登場しない唯一の数字を出力してください。
入力例1、0、2、3、4、5、6、7、8、9、出力例は1。
入力例2は、4、5、9、2、3、0、7、8、1、出力例は6。
なので、Sイコール、どうしようかな。
リストのインプットにして、4i in rangeの10。
で、if stri not in Sだったら、exit print。
はい。で、いいんじゃないですか。
1回提出してみますね。
はい、ACしたのでB問題いきます。
B問題スライム図。問題文。
A匹のスライムがいます。
すぬけくんが1回叫ぶたびにスライムは軽倍に増殖します。
スライムがB匹以上になるためには、すぬけくんは最小で何回叫ぶ必要があるでしょうか。
軽倍。10の9乗。
割り算かな。
B匹割るKかな。
B割るKかな。
出力例は、1、4、2。
B割るK、2ですね。
7割る10。
はいはいはい。
えーっと、A匹います。
軽倍。B、K。
うーん、ちょっとよくわかんないな。
とりあえず、A、B、Kを受け取ります。
A、B、K。
マップ。ピント。インプットドットスプリット。
まあ、B問題なんであんまり深く考えなくてもいけるとは思うんですが、
03:05
Aが、えーっと、
A小なりイコールBだったら、
エグジット。プリント。ゼロ。
そうじゃなかったら、プリント。
割り算でいいのかな。
B割るK。
たぶんB割るKだと、
うーんと、
まあ、入力例3がちょっと数字デカいんで、
確認してみましょうか。
出力が6になったらOK。
ゼロ。
ああ、そうか。逆?
AとBの数字逆?
スライムがB匹以上になるためには、逆ですね。
A、A。ダイナリーイコールBか。
8、3、1、8、5。全然違うな。
いっか。ファイル。トゥルー。
で、A匹のスライムがいます。
ああ、そうか。CNTイコールゼロの
AかけるイコールK。
CNTプラスイコール1。
ファイル分を、えーっと、
AがダイナリーイコールB。
逆だな。小なりA、小なりBの間、
Aを軽倍していきます。
で、最後、プリント。CNTかな?
なんか割り算で解けそうな気はしますけどね。
提出例は、提出例じゃない。入力例クリアしたので提出していきます。
はい、ACしたのでC問題いきまーす。
C問題。台数サム。問題文。
長さNの整数からなる数列Aであって、
以下の条件を全て満たすものは何通りありますか?
Aiは1以上N以下。
Iは1以上N以下。
06:00
で、Iが1からNまでのAiについて、
それはK未満、K以下ですと。
ただし答えは非常に大きくなることがあるので、
答えを998244353で割った余りを求めてください。
制約。NMは50。
で、MAXでもN×M。50×50の2500かな?
以下の数字の条件を満たすものは何通りありますか?
入力例1、2、3、4。出力例1、6。
条件を満たす数列は1、1、1、2、1、3。
2、1、2、2、3、1。
ちょっと何言ってるかわかんないな。
NMKを受け取ります。
NMKイコールマップのインとインプットとスプリット。
で、モード。
これで割ってくださいって言ってた998244353を受けておきます。
Ai。条件は何通りありますか?
Kはどこから出てきたの?
Kは3つ目か。3つ目の受け取り。
リストAの合計が…
そうですね。その数列の中で足した合計がK以下であること。
で、それぞれの値がM以下であること。
え、めっちゃむずくね?
なんだこれ。全然ピンとこないな。
長さNの整数からなる数列A。
数列AはM。
だから1からM。
でもNとMが一緒かどうかはわかんないのか。
んー、ちょっとチンプンカンプンですね、これは。
解説ちょっと見ようかな。早めにリタイアした方が良さそう。
数列を全通り試そうとするとMのN乗種類の数列が考えられるため、
実行時間制限には到底間に合いません。
数列を先頭から決めていくこととします。
ここで以下の事実に着目します。
数列を先頭から決めていく際、覚えておくべき必要があるものは、
09:03
その時点での数列の相和のみであり、
具体的に各要素の値が何であったかは、
斜増しておい、捨てる増ですね。
斜増、初めて見たな。
このことを用いると動的計画法で解くことができます。
DPってやつですね。
DPiJ、数列の先頭からi項まで決めた際に、
相和がJであるような数列の決め方の総数。
DPの定義。
iとしては0以上N以下。
Jとしては1以上K以下を考えれば良いので、
乗体数はオーダーN×Kです。
DPの初期値。
はじめDP00イコール1で、残りは0で埋めます。
DPの占議。
iの標準に計算していきます。
Jイコール0からKマイナス1、
Kイコール1からMについて。
もしJプラスK小なりイコールKならば、
JプラススモールK小なりイコールビッグラージKならば、
DPiプラス1、JプラススモールKに
DPiJを加算すると遷移すれば良いです。
答え。
最終的にDPN1プラスDPN2プラス…
DPNKが答えとなります。
計算量はオーダーN×M×Kです。
DPですね。
ちょっとPythonの回答じゃないので、
ユーザー解説。
見てもちょっとわかんないね。
Pythonの解説例、
回答例がないので、
後でチェックしておきます。
ではまた次回お疲れ様です。