AtCoder Beginner Contest 284に参加しました。
結果
A,B,C,Dの4問正解でした。 E問題ももう少し時間があれば解けそうな気がした。ぱっと解き方を思いつかなかったから先にF問題解いてみたのが失敗だったな。
A - Sequence of Strings
問題文の通り処理する。
配列に文字列を登録してから逆順に表示すれば良い。
文字列はN個とわかっているのでインデックスをNから1まで順番に減らしていけば良い。
配列の扱い方がわかっているかどうかな問題だと思う。
B - Multi Test Cases
これも問題文の通り処理すれば良い。
具体的には以下の処理をT回繰り返せば良い。
- Nを受け取る。
- 奇数の数をリセットする。
- N個のAを受け取り奇数か偶数かを判定する。
奇数ならカウントする。 - カウントした奇数の数を出力する。
A問題くらいの難易度の問題をT回解くコードを書けば良い。
C - Count Connected Components
グラフが与えられるので連結成分の数を答える問題。
連結成分の数という点でUnion-Findを使って解くことにした。
具体的には、ある頂点同士が辺でつながっているという情報からある頂点をもう一方の頂点のグループに追加していった。
最後に、rootが何種類あるのかをsetを使って数える。
setのサイズ＝連結成分の数になるので、これで答えが求められる。
D - Happy New Year 2023
すごく単純に言うと、合成数Nが与えられるから元になる素数を答える問題。
情報として、素数は2種類だけでとなることがわかっている。
Nはとかなり大きいけど、答えとなる素数うち小さい方は
以下になる。
（もし小さい方の素数さえも
より大きいなら、
になるから）
なのでより小さい素数を洗い出してから順番に割り切れるかどうかを確かめる。
割り切れる素数を見つけられたら同じ素数でもう1度割り切れるかどうかを確認する。割り切れないならになるのでNを素数で割った後の値の平方根をとる。
割り切れるなら同じ素数でさらに割った答えが
となる。
計算量を考えても
くらいになると思うのでTLEしないで解ける。（Mは
以下の素数の数。Nと比べると十分に小さい値になる。）
1番大きいところで以下の素数を探すところだけど、どの値が素数かはNに関わらず一定なのでT個あるテストケースの内最大のNに合わせて素数を列挙しておいて
後はテストケースごとに線形探索で素数を1つ見つければ良い。