れとろのメモ置場

とあるSEのメモ置場

freee プログラミングコンテスト2022(AtCoder Beginner Contest 264)

freee プログラミングコンテスト2022(AtCoder Beginner Contest 264)に参加しました。

結果

A,B,Cの3問正解でした。C問題でちょっと時間が掛かったので順位は低めで悲しい。

D問題は時間がちょっと足りなかった。20分くらい超過してACできた。もう少し落ち着いて解ければギリギリ間に合ったかも。

A - "atcoder".substr()

問題文の通り指定された範囲の部分文字列を出力させる。

文字列の扱い方に関する問題なんだと思う。

B - Nice Grid

指定されたマス目の色が白か黒かを答える問題。

マスの塗り方は同じなので2次元配列で白黒を管理して答えるようにして解いた。

もう少し時間をかければ何かしらの法則性があって数式にできるような気もしたけど、 時間をかけたくなかったのと15\times15くらいなら手作業で配列を初期化しても大した手間じゃないので 手作業で対応した。

C - Matrix Reducing

うまい方法が思いつかずbit全探索で全通りの探索をして解いた。

どの行を選ぶかを全探索しつつ、どの列を選ぶかを全探索して行列を作って、作った行列がBと一致するかどうかで判断した。

制約を見ると行と列のサイズはそれぞれ最大で10なので、行と列それぞれで全探索したとしても2 ^ {10}で1024程度。なので行と列をそれぞれ全探索下としても計算量はざっくりと計算して10 ^ {6}程度でTLEにはならない。 後は行列の要素が一致しているかどうかを確認するのに最大で100回なので計算量は最悪の場合で10 ^ {8}になる。これはギリギリTLEにはならない計算回数なのでbit全探索を使っても間に合いそう。

ここまではすぐに思いついたけど実装に手間取ってそこそこ時間がかかった…

D - "redocta".swap(i,i+1)

指定された文字列をバブルソートしてatcoderにする時の最小のスワップ数を答える問題。

最初は幅優先探索で解こうとしたけど入力例3を試してみたら結果が全然返ってこなかった。改めて考えてみると答えがxだとすると計算量は最小で6 ^ {x}で答えが21になる入力例3だと計算回数が恐ろしいことになっていた。
文字列の種類は7!程度で大したことないはずなので既に見た文字列を弾く処理がうまく動いてなかったのかなあ。

別の方法を考えるために少し考察してみると、無駄なくソートしたときのスワップ回数がそのまま答えになるようなので、atcoderの先頭から順番に並べていく方針で考えることにした。

ABCDEXをバブルソートでXを先頭に持っていこうとするとソート後はXABCDEとなるのでスワップ回数はXを移動させたい距離になる。ここまでは簡単だけど、ソート後の文字列を作る部分でかなり手こずった… 直感的にこうなるという部分をうまくコードにするのが大変だった。

解説を見ると幅優先探索で解くっぽい方針だったので最初の解き方で合っていたっぽい。細かい処理が少し雑だったのかなあ。