サマリー

6月くらいから、AtCoderやってみようと、ふと思い立って初めて約半年。
年末時間ができたから復習していてそこで面白かった問題を上げていく。
基本過去記事の再掲しつつ、もう一度振り返る。

AtCoder Beginner Contest

169 C-Multiplication 3 (2020-05-31)

問題は以下 atcoder.jp 初めての参戦で、いきなりこの問題でWAを超絶だした記憶。オーバーフローや計算精度に関する問題も出るのかと痛感した。

どういう時に問題が起きるのかをそもそも理解できずに、試行錯誤しつつ、以下のうように、浮動小数は実際には正しい値を保持していないことを改めて知って勉強になった。

0.07 * 100
# 7.000000000000001
0.29 * 100
# 28.999999999999996

でもDecimalモジュール使えばいいやと思って通した。

a, b = map(str, input().split())
res = int(a) * Decimal(b)
print(int(res))

けど本来は、数値をそのまま掛け合わせて後で割って整数部分だけ取得するとやってほしかったんだろうなぁ

a, b = map(str, input().split())
c,d = b.split('.')
# int(c+d)とするとbを文字通り100倍された結果になる。
res = a * int(c+d) 
print(res//100)

169 D - Div Game (2020-05-31)

問題は以下 atcoder.jp この当時は、素因数分解をする方法もコードに落としてなくて１から実装しなきゃで大変だったが、それさえできればあと一工夫でできる。

170 D - Not Divisible (2020-06-14)

問題は以下

atcoder.jp

この当時は、エラトステネスの篩的な考えもコードに落としてないし、発想としても持っていなかった。

リストに含まれるある値の定数倍の値をふるい落とすという考えを学んだ
また、inで探すときは対象をlistではなくsetにしておくことが速度として重要というのも学んだ

n = int(input())
a = list(map(int, input().split()))
a_s = sorted(a)
a_set = set(a_s)
maxv = max(a)
res = [0] * (maxv+1)
rep = 0
for i in a_s:
    # iを評価してない時はiを含むの定数倍のところは+1
    if res[i] == 0:
        for j in range(i, maxv+1, i):
            res[j] += 1
    # iを評価してあればiを+1
    # すでに定数倍として評価されていたら2以上にしたい
    else:
        res[i] += 1
cnt = 0
# 最終的に検索対象が定数倍リスト内で１になっているものだけをカウントする
for i in range(n):
    if res[a[i]] == 1:
        cnt += res[a[i]]
print(cnt)

172 C - Tsundoku (2020-06-27)

問題は以下 atcoder.jp

ここらへんから記事書き始めた。

しゃくとり
累積和と二分探索

この時、これらのイメージを掴んだ感じ

サマリー

AtCoder Beginner Contest

169 C-Multiplication 3 (2020-05-31)

169 D - Div Game (2020-05-31)

170 D - Not Divisible (2020-06-14)

172 C - Tsundoku (2020-06-27)

172 D - Sum of Divisors (2020-06-27)

173 C - H and V (2020-07-05)

174 C - Repsept (2020-08-02)

176 D - Wizard in Maze (2020-08-22)

178 C - Ubiquity (2020-09-13)

180 C - Cream puff (2020-11-01)

181 D - Hachi (2020-10-17)

182 D - Wandering (2020-11-08)

183 D - Water Heater (2020-11-15)

184 D - increment of coins (2020-11-22)

186 D - Sum of difference (2020-12-19)

AtCoder Regular Contest

106 B - Value (2020-10-24)

109 B - log (2020-11-28)

110 B - many (2020-12-05)

最後に

参考書籍