AtCoder Beginner Contest 254に参加しました。
結果
A,B,Cの3問正解でした。
C問題が難しかった。なので解けそうなD問題を先に解いてみたけど失敗だった。
結局D問題は解けずC問題に戻ってきて力技で解いてみたらACできた。でもC問題をACする時間が遅かったから順位が低くなた。
A - Last Two Digits
入力された数字の下2桁を出力する問題。
数値として受け取って100で割った余りを先頭0埋めの2桁表示させたり、
文字列として受け取って下2桁を表示させたり解き方は色々ある。
入力される数値は3桁だけだから文字列として受け取って決め打ちで2,3文字目を表示させれば1番楽そう。
B - Practical Computing
数式がややこしいけど結局二項係数を出力すれば良い。
を計算する関数を作っておけば後はループでn,rを全通り当てはめて計算すれば良い。
mod計算に関して勉強した時にライブラリを自作しておいたのでコピペしてループを書いて終わりだった。
C - K Swap
幅が固定されたコームソートで昇順にソート可能かどうかを判定する問題。
難しかった… K=1のときはバブルソートなので必ず昇順にソートできるのでK>1の時に関して考える。
時間制限を気にしないなら幅Kで入れ替えが起こらないまでコームソートをして、
その結果が正しく昇順になっているかどうかを確認すればいいけど、
”入れ替えが起こらないまで”がどれだけ時間がかかるかわからないけど最悪になるので実際にはTLEになる。
説明するのがややこしい力技な解き方をしたらなんとかACできたから良かった。
D - Together Square
そもそも平方数って何ってなった。ググった結果の数のことらしい。
計算時間を気にしないなら１～Nまでのを計算して、それぞれの約数を列挙してN以下の約数の組み合わせを数えていけば答えは求められる。
実際にやってみるとTLEになった。
手計算で1,4,9,16,・・・の約数を手計算して条件を満たす組み合わせを数えてみると、Nがある程度の以上になると条件を満たす組み合わせが1にしかならなくなるっぽいことがわかった。ある程度までは組み合わせを数え上げて、ある程度以上は1になるとしてまとめてカウントすればTLEにならないくらいの時間で答えが出せそう。結局ある程度のギリギリがわからないし、適当な値でやってみたらTLEやWAになったので解き方の方針がそもそも間違っていそう。
