AtCoder Beginner Contest 319に参加しました。
コロナに罹って1週間位寝込んでからの療養で2週間くらい体調を崩していたり、予定があって参加できなかったりで1ヶ月ぶりくらいのAtCoderでした。
久々で全体的に鈍ってる感がすごかった。あと、ここ1ヶ月くらい業務でPythonしか書いてないからC++の書き方忘れてた。
これはリハビリが必要そう。
結果
A,Bの2問正解でした。
久々でいろいろ鈍ってる感じはあるけど、C問題も解けなかったのがちょっとショック。
C問題がなんか難しかった。
D問題は2分探索を駆使すれば解けると思うけどちょっとバグらせてて、バグ取りで時間がなくなった。
A - Legendary Players
文字列が渡されるから、それに対応する数値を出力する問題。
Pythonだと辞書を使えば一発だなあと思いながら、普段のC++だとどう書いてたっけと思いながらif文を10個並べて解いた。
B - Measure
問題文のとおりに処理を実装して解く問題かなあ。
約数列挙が必要かなと思いきや9以下の約数だけが知りたいので、1~9でNを割り切れるものを探せばいい。
約数が一通り分かれば、0~Nの範囲でiがN/約数で割り切れるかどうかを確認して、
割り切れるならその中で最小の約数をiごとに保存しておく。
最後にiごとに結果を出力すればいい。
C - False Hope
ビンゴ?スロット?がテーマな問題。
3×3のマス目にランダムに数字が振られてて、縦横斜めで同じ数字が1列に揃うことはないときに、ランダムにマス目の内容が教えられ
2マス揃って3マス目は揃わなかったと言う状況にならないマスの開き方は何通りあるかを答える問題。
決して1列揃うことは無いのがちょっと悲しい…
9マスの開き方は9!通りでそれほど大きな値じゃないので多分全通りの確認ができる。 なので、ある順番でマス目を開いていくときに条件を満たすかどうかを判断していけば答えられそうだと思った。
条件を満たすかどうかの部分を関数に切り出して処理しようと思ったけど、うまく実装できなかった。
どこかでバグらせているのか、そもそも考え方が悪いのか…
D - Minimum Width
N個の英単語を画面に表示させようとしている。M行で全部表示できた時、画面の横幅としてありえる最小値はいくつかを答える問題。
横幅が小さいうちはM行以上になって、ある閾値からはM行で表示できるようになるので、2分探索でその閾値を探せば良いと思う。 横幅を仮にXとした場合に、全部で何行で表示できるかを計算してM行以下にできるかどうかで2分探索の更新内容を判断すればよいかなと思った。
横幅をXとしたときに単語列を何行で表示できるかは競プロ典型90問でほぼ同じ問題( 001 - Yokan Party(★4))があったと思いながら、この部分だけを処理する関数を作って処理を分割しておいた。
一通り実装してみてサンプルを解いてみたけどすごく遅かった… 二分探索に二分探索を重ねているのが悪いのか、それとも何かの処理が遅いのか…