A bolt out of the blue

競プロ、その他勉強したことなど

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
3. ai≤105かつN3000なので、最小公倍数は最大で1015000。全部は計算できない。
4. 計算量が究極に少ないのは、決め打ちすることだよな
5. あれ、最小公倍数より1だけ小さい数字は、元のどの数も割り切らないぞ

つまづきポイント

「最大公約数(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で安定ソートすると、下のようになる。

f:id:hazuhi:20180722000959j:plain

 

○のうち、左側がa, 右側がbだ。

こうやって並べてみると、確かに上から処理していけば、右に部分問題が残るのでうまくやれそうに見える。

 

反省点

1. 問題を多角的に捉えられていない。

2. 特に部分問題に分ける意識が低かった(部分問題に分けようとすれば、自ずと並び替えにも至ったかもしれない)

 

結果 

R964 => R919 (Down)

次はCまでは解けるようにしたい、、、