AtCoder Beginner Contest 293に参加しました。

結果

A,B,C,Dの4問正解でした。C問題からちょっと手間取って時間がかかった。

微妙にレーティングは上げれたからいいけど、もう少し早くD問題まで解いておきたいなあ。そのほうがレーティングが上がりやすいし。

A - Swap Odd and Even

先頭から2文字ずつ前後を入れ替えて行き、操作後の文字列を出力する問題。
123456が214365となるような文字列の入れ替えを行っていく。

N以下値を持つの数列が与えられるので、１～Nで数列に含まれない数値を昇順に列挙する問題。

N個分のフラグを用意して、数列に含まれる値はフラグを立てておく。最後に先頭からフラグを確認していき、フラグが立っていない値を順番に出力すればよい。

各マスに数字が書かれたマス目があり、左上の端から右下の端へ移動する。その時に各マス目の数字が被らないような移動方法は何通りあるかを答える問題。

数字が被っているかどうかの判定は、通った道の数値を全部setに入れておいて、setのサイズと移動距離が一致するかどうかで判断できそう。なので、そこまでの数値のsetを持ちながら深さ優先探索で条件を満たす経路を全探索して答えた。

ペアで座標を持ちつつ、座標とsetのペアをスタックに入れていき深さ優先探索を行った。数字の被り判定をsetでやるのを前提に解こうとしたのでちょっと強引だった気がする。

両端が区別できるロープがN本合って、どのロープの端とどのロープの端を結ぶかが与えられる。最終的に輪がいくつできて、輪になっていない塊が何本あるかをそれぞれ答える問題。

輪になっているのかの判定をどうしようかなとか、このロープの端は結ばれた結果どのロープの端となっているのかなどをどうやって管理しようかなと考えてみたものの、なかなか考えがまとまらなかった。

最終的にはUnion-Findを使って解いた。ロープ同士を結合する時に、番号が小さいロープが親となるように結合しつつ、それぞれの親を確認して一致していた場合は輪になったと判断してカウント。輪になっていない連結成分は、連結成分全体から輪の数を引いて求めた。

問題文と数式は簡単なのに解くのはすごく難しい…

総和のMODを取るので、各項のMODを取ったものを足しても同じ答えになる。各項はAの累乗なので、AのMODを取ったものを累乗しても答えは一致する。と考えつつ、累乗のMODを取っているとどこかでループが起きると考えた。ループ部分をまとめて処理すれば総和の計算はかなり圧縮できるので、

で解けると思ったけど、Mが大きすぎるとエラーになって解けなかった。