AtCoder Beginner Contest 103 参加ログ
ABC103に参加しました
AtCoder Beginner Contest 103 - AtCoder Beginner Contest 103 | AtCoder
実力:緑色(最高R: 1007, 現R: 964)
今回は概ね時間通りに参加。
A, B
いつも通り普通に解けばおk
今回はAが少し引っ掛けで、Bが少し考える問題だったか
C - Modulo Summation
今回はCでつまづいた。
C問題自体はそれほど難しくはなかった。
ai列の最小公倍数より1だけ小さい整数の時に、fが最大となることに気がつけば良い。
だがここに至るまでにも紆余曲折経た。次のような思考をして答えにたどり着いた。
1. 全ての剰余類についてfを計算して、最大を探せば良いのでは?
2. 次の例でn = 24までを調べてみると、値の変化が12周期である。つまり最小公倍数ごとに1周する。
3 3 4 6
つまづきポイント
「最大公約数(GCD)を計算するmath.gcdは、Python 3.5から追加」
コレだ。
Pythonで最大公約数と最小公倍数を算出・取得 | note.nkmk.me
最小公倍数(LCM)を計算するのに、GCDを計算しなければいけないが、それをそのままこのサイトから持ってきてしまった。
AtCoderはPython3.4.3なので、math.gcdは使えない。
反省点
AtCoder上でコードテストができるので、それを使ってまず試す。
また環境を3.4.3に合わせる。
D - Islands War
計算量をうまく減らすことができず、TLEのまま時間切れ。
(C問題を提出してすぐDを解き始めたので、CのREに気がつかず両方落とす結果に)
解説を読んで自分なりに解説してみたい
aでソートされた列を考える基点にしていると、うまく正解にたどり着かないのかもしれない。
元の配列をbで安定ソートすると、下のようになる。
○のうち、左側がa, 右側がbだ。
こうやって並べてみると、確かに上から処理していけば、右に部分問題が残るのでうまくやれそうに見える。
反省点
1. 問題を多角的に捉えられていない。
2. 特に部分問題に分ける意識が低かった(部分問題に分けようとすれば、自ずと並び替えにも至ったかもしれない)
結果
R964 => R919 (Down)
次はCまでは解けるようにしたい、、、