僕が考えたこととライフハック

政治経済、ITについて書く。

ABC125 参加メモ 初めて本番でD解けた。

ABC125

昨日のAtCoderBeginnerContest125で考えたことや実際に書いたコード等を書いて残しておきます。

A - Biscuit Generator

単純に当たれられた時間をクッキー製造でかかる時間で割った商 × 一回のクッキー製造で作れる枚数。

 

B - Resale

x-yが正である宝石は買うだけ得するので、全通りのx‐yを求めつつ正になるものを数える。

 

C - GCD on Blackboard

本番では解けなかった!(ので飛ばしてDを解いた。)

ABC後のTwitterで「累積GDC」がトレンドに入っていましたがまさにそれです。

「累積和」の累積テーブルのようにしてGCDも累積していくとTLEせず書き換える数字が見つかる。

(いちいち計算していたので間に合わなかった・・・)

 実際にleftとrightをトレースしていくとわかりました。賢い!!

D - Flipping Signs

負の数と負の数が隣り合わせだと、‐1をかけたときどちらも正の数になりうれしいですよね。

一方、正の数、負の数で並んでいる場合は、負の数、正の数の順になる。この操作を連続していくとマイナスの符号を左に押し付けるようなイメージで動かすことができますよね。

例えば、

「1 , -2 , 7 , 5  -3」という数の並びの時

左から2番目と3番目に操作すると

「1 , 2 , -7 , 5  -3」 となり

左から3番目と4番目に操作すると

「1 , 2 , 7 , -5  -3」

負と負が隣り合ったので嬉しい!!

↑から分かることはマイナスのの数が偶数の場合は打ち消しあうということ。

つまり、奇数の場合はマイナス符号一つ余ってしまうので一番小さい数にマイナスを押し付けると全体として一番大きくなる。

そんなプログラムを書きました。

 

感想

ABC参加4回目でしたがやっぱり競技プログラミング楽しい。

初めて本番中にDを解いたのですごい進歩かもしれない。

ABCの問題数が令和から変わるみたいなので”ABC全完の実績解除”は難しくなると思いますが、精進して力をつけていこうと思います。