AtCoder Beginner Contest 186 参加ログ・感想

内容
結果
どう考えたか + α
おわりに
参考になる書籍

内容

Python3でやっている。
参加ログ。
所感。
コンテスト中に何を考えたか。
コンテスト後に解説をみたり、少し整理したりしたくらいの内容。
問題の詳細で細かく書こうと思うものは別記事とする。

結果

久しぶりにABCD完。Eも方針が立つくらいにまでは時間があった。少しは成長している感触だった。Cはn進数をリストで持つようにして対応。制約的にDは線形で考えなくてはいけないと考え、絶対値がポイントになると踏んで対応した。

どう考えたか + α

問題

A - Brick

問題タイプ：商

文意から商が答え

n, w = map(int, input().split())
ans = n // w
print(ans)

B - Blocks on Grid

問題タイプ：最小値・ループ処理

$A$ を多重リストで持つと面倒なので、flattenして、１次元のリストにする。
$A$ の最小値を求める。
$A$ をループで回しながら最小値をとの差を加算していく。

import itertools
def flatten(l):
    return list(itertools.chain.from_iterable(l))
h, w = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(h)]
a = flatten(A)
min_a = min(a)
cnt = 0
for i in a:
    cnt += i - min_a
print(cnt)

C - Unlucky 7

問題タイプ：n進数

もしかしたら、組み込み関数でいい感じにできるかもしれなかったが、知らんかったのと、入力値とn進数を入れたら、各桁のリストで管理したかったので、その様にやった。あとは10進数と8進数どちらも出てきたの中に $7$ がないものだけカウントするだけ。

def shinsu(N, shinsu=8):
    keta=0
    for i in range(10**5+1):
        if N<shinsu**i:
            keta+=i
            break
    ans=[0]*keta
    check=0
    for i in range(1,keta+1):
        j=N//(shinsu**(keta-i))
        ans[check]=j
        check+=1
        N-=(j)*(shinsu**(keta-i))
    return ans
n = int(input())
cnt = 0
for i in range(1, n+1):
    ans10 = ch(i, 10)
    ans8 = shinsu(i)
    if 7 not in ans10 and 7 not in ans8:
        cnt += 1
print(cnt)

ちなみに、調べたらoct()とすれば8進数にできるらしい。 10進数はstrにすればいいので、そうすると以下のように可能。 oct()のために超絶めんどいことしてしてしまった。

n = int(input())
ans = 0
for i in range(1, n+1):
  if ('7' not in str(i)) and ('7' not in oct(i)):
    ans += 1
print(ans)

D - Sum of difference

問題タイプ：ソート・累積和

すべてのパターンは $\frac{(n)\times (n-1)}{2}$ でも制約的に、線形で考えなくてはいけないので二重のforではだめ。ポイントは、順番をソートする。その後順番に数ごとに加える量や引く量を線形に計算していく。別記事にする。

おわりに

今回は、比較的できた。今までやってきたことが、問題に多く出てきたという感じ。やはり慣れが重要だし、ぱっと思いつける様に精進が重要。が沼はまだ深い・・・。

参考になる書籍

問題解決力を鍛える!アルゴリズムとデータ構造

けんちょんさんこと、大槻さんの書籍である、「問題解決力を鍛える!アルゴリズムとデータ構造」ご本人の記事の中で難易度は、螺旋本ということで初学者でも非常に結構読みやすい!!!（実際に、けんちょんさんの記事はC++に疎い自分でも、その思考プロセスを学べるくらい丁寧に書かれているし、この書籍も非常に読みやすい）どのようなステータスの人にもおすすめの一冊になっている。