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法のどっちかな、と思ったが上手く行かず途中で全探索しないようにちょっと削る… みたいな方針を変えてしまった)をやってみてもいいのかも。
それ以上に早く正確に簡単な問題を取るのも練習しとかないとなと思う。練習大事なので…。