AtCoder Beginner Contest 164 感想&反省
AtCoder Beginner Contest 164が終了しました。お疲れ様でしたー。
今回のコンテスト、気になったのですが...
ズバリ "ABC早解きコンテスト" だったと思います。
(A問題、B問題、C問題を早く解くことと、ABC○○コンテストにあやかってこのような名称としました)
D問題がかなり難しかったみたいです...
Twitterなどで私が何度も言及した"C問題とD問題の間にある壁"が今回はより一層分厚かったように感じます。
個人的には、このような問題セットもアリだとは思うのですが、おそらく今回のコンテスト、早解きをした方ほどパフォーマンスが高くなる傾向になったのではないでしょうか？(私は3完早解き上位20人くらいに入っていたと思います)
A問題 A - Sheep and Wolves
https://atcoder.jp/contests/abc164/tasks/abc164_a
かどうかを判定し、
ならば"unsafe",そうでなければ"safe"と出力すれば良いです。
コード: https://atcoder.jp/contests/abc164/submissions/12332240
B問題 B - Battle
https://atcoder.jp/contests/abc164/tasks/abc164_b
以下のようなループを変数iを用いて有限回回します(私は回としました)
を2で割った余りが0なら、
を
にする。
もしが0以下ならば"Yes"と出力する。
を1で割った余りが0なら、
を
にする。
もしが0以下ならば"No"と出力する。
いずれの場合でも、何らかの文字列を出力した段階でループを終了する。
これにより、この問題を解くことが可能です。
コード: https://atcoder.jp/contests/abc164/submissions/12339019
C問題 C - gacha
https://atcoder.jp/contests/abc164/tasks/abc164_c
何種類の景品を手に入れたでしょう？と聞いて思いつくのは
全ての入力()をリストにして、それを集合にして 集合の要素の個数を出力する
ということです。
Pythonでは、set()を実行することにより、リスト
の要素の集合を作成することが出来ます。
また、list(set())を実行することにより、リスト
の要素の集合をリストとしたものを出力することが出来ます。
集合の要素の数はlen(list(set()))などで求めることが出来るので、これで求められる値を出力すればよいでしょう。
以下、方針です
k = [空のリスト]とする
回以下のループを実行する
kに文字列を挿入する
リストkの集合の要素の個数を出力する
計算量はです。
コード: https://atcoder.jp/contests/abc164/submissions/12341880
D問題 D - Multiple of 2019
https://atcoder.jp/contests/abc164/tasks/abc164_d
聞いたことがある気がするのですが
長さの文字列の部分文字列の個数は
個だったと思います。
<証明>
長さの文字列において
長さの部分文字列の個数は
個です。
長さの部分文字列の個数は、連続した2文字を選ぶので
個です。
・
・
長さの部分文字列の個数は長さ
の文字列しか考えられないので
個です。
以上のことから、部分文字列の個数は個であるといえます。
今回の制約では、だったので、最大で
(200億)個の部分文字列を考えないといけなかったのです。当然、PythonどころかC++でも列挙するまでにTLEになりそうだと思い、さじを投げました。orz
今回は先述した通りABC早解きコンテストになったということで、予想よりパフォーマンスが高く出たと感じた方が多かったと思います。私もおそらく初の水パフォになりそうです。
以上、ABC164の感想&反省でした。
(レートが冷えてしまった方、私を恨まないようにお願いしますよ....)
