名もなき未知

エンジニアリングとか、日常とかそういうのをまとめる場所。

ABC 106振り返り

3完。実力的に4完出来ないといけないセットだったので、レートが下がった。うーん、ABCは安定させないとだめだね。先は長い。

A問題

https://beta.atcoder.jp/contests/abc106/tasks/abc106_a

やるだけ。AWKで投げた。

$0=($1-1)*($2-1)

B問題

https://beta.atcoder.jp/contests/abc106/tasks/abc106_b

エスパーしようとしてだめで、見つかりそうな数字を列挙してインクリメントしたけど、数え損ないがあったので、諦めて総当たりコードを書いた。

#!/usr/bin/env python
# -*- coding: utf-8 -*-


def solve():
    n = int(input())
    if n < 105:
        print(0)
        return

    ans = 0
    for i in range(105, n + 1, 2):
        t = 0
        for j in range(1, n + 1, 2):
            if i % j == 0:
                t += 1
        if t == 8:
            ans += 1
    print(ans)


if __name__ == "__main__":
    solve()

C問題

https://beta.atcoder.jp/contests/abc106/tasks/abc106_c

左から見たとき、1出ない文字が出たときにその文字が表示されるのが基本。しかし、Kが小さく、Nが大きく1が続いたとき、1が出る可能性があるのでそれを考慮する。

考慮が上手く行かずに2WAしたのはもったいない以外の言葉なし。

#!/usr/bin/env python
# -*- coding: utf-8 -*-


def solve():
    s = input()
    n = int(input())
    idx = 0
    slen = len(s)
    while idx < slen and s[idx] == "1":
        idx += 1
        if idx == n:
            print(1)
            return
    if idx == slen:
        print(1)
    else:
        print(s[idx])


if __name__ == "__main__":
    solve()

D問題

https://beta.atcoder.jp/contests/abc106/tasks/abc106_d

累積和を使う。制約が更に厳しければ二次元でそれをしなければいけないが、今回はそうでもないのでNの行について(多分行だよね…)ついてのみ、累積和を求めておき、毎回求めるべき範囲についてぐるぐる回して求める。

解説を見て、累積和なのは推測がついていたが、解説を参考にしてコードを書いたがどうしても通らなかった。 原因としては、Listのappendコストが高い事を忘れていたことにある。N×Nの行列を0で初期化するか、Nのリストにひたすらappendするかであるが、後者だとだめで、前者だと通った。このレベルのループ回数になるとappendの影響をもろに受けるということは再認識したい。(コレ本番だったら間違いなく焦っただろうなあ)

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import bisect
import array


def solve():
    n, m, q = map(int, input().split())
    nl = [[0 for i in range(n + 1)] for j in range(n + 1)]
    for e in [input().split() for _ in range(m)]:
        l, r = int(e[0]), int(e[1])
        nl[l][r] += 1
    table = [array.array("i", [0] * (n + 2)) for j in range(n + 2)]
    ran = array.array("i", range(n + 1))
    for i in ran:
        for j in ran:
            table[i][j + 1] = table[i][j] + nl[i][j]

    for i, e in enumerate([input().split() for _ in range(q)]):
        l, r = int(e[0]), int(e[1])
        ans = 0
        for j in range(l, r + 1):
            ans += table[j][r + 1] - table[j][l]
        print(ans)


if __name__ == "__main__":
    solve()

まとめ

安定して4完したい。なので基礎的なことを忘れないことと、もう少し直感を信じること(D問題は最初累積和か、imos法のどっちかな、と思ったが上手く行かず途中で全探索しないようにちょっと削る… みたいな方針を変えてしまった)をやってみてもいいのかも。

それ以上に早く正確に簡単な問題を取るのも練習しとかないとなと思う。練習大事なので…。