AtCoder Beginner Contest 125
Beginner Contest 125 まではA~Dまでの4問題だったようだ。 6問題ある前提で、D問題まで確実に解けて、E問題を半分ぐらい。と考えていたが、6問になったのは意外と最近なことがわかってしまった。
これからどうやって練習していこうかちょっと迷うが、とりあえず今回はBとC問題を解いてみて難易度を確認する。
B問題
思ったより簡単だった、6問ある場合のBとC問題の間でB寄り。ぐらいの難易度だった。 一発AC
C問題
最初に思った解法だとTLEだったので、もう少し計算量を減らすようにしたらACだった。 O(N)を意識できるようになってきた感じがする。
大体最初に思いつく解法はO(N2)な事が多くて、そこからどう計算量を減らせるかなーって考えることが多い。
ちなみにこの問題の解説を読んだけど何を言っているのかわからなくて難しかった。
自分は解法はこう。 1. 与えられたAのなかで2番目に小さい数字を取り出す 1. その数字でAの要素の中で割り切れない数字が1つ以下になるかどうか確かめる。 1. 1つ以下になればその数字が答え。2つ以上あればそこから1減らした値でまた(2)を行う。
1つだけ数字を変えることができるので、1つ割り切れないものがあってもその数字を変えれば良いという考え。 最初に一番小さいものではなくて、小さいものから2番目を取っているのは一番小さい数字を変更する可能性があるため。
感想
家に帰ってきた時間が遅くて、時間的にD問題を解く時間がなかったけど、30分でBとCが解けたので良かったと思う。 と書いたところで、このコンテストの順位を見に行ったのだけど、40分でA~Cを解いている人は水色かそれ以下のランキングの人だった。 青色を取るにはこのコンテストでD問題まで解かないといけないらしい。
次回はこの問題のD問題を解いてみようと思う。
