AtCoder ABC106

概要

AtCoderの勉強記録です。全部Pythonで頑張ります。

この記事の対象

• AtCoderについてある程度知っている人
• Pythonがある程度読める人

本編

AtCoderとは

競技プログラミングコンテストを開催している会社です。 atcoder.jp

ABC106

解いていきます。

A Garden

はい。

a,b = map(int,input().split())
print((a-1)*(b-1))

B 105

Nを√N未満の数xで割り切れるとき、必ずxと異なる約数N/xが存在するので、√Nまでを探索して約数カウントが4になったらいいのかなーって思って実装したけど何かをミスっていたのか、WAを出してしまった。問題設定を見直すとNが200以下とかなり余裕があったので普通に全探索に切り替えました。N,約数ともに奇数しか探索する必要がないことには注意。

N = int(input())
cnt2 = 0
for n in range(1,N+1,2):
    cnt = 0
    for i in range(1,n+1,2):
        if n % i == 0:
            cnt += 1
    if cnt == 8:
        cnt2 += 1

print(cnt2)

C To Infinity

Mr.Infinityとかいう数字を無限増殖させるチート能力の持ち主が登場する問題。
まず、Kが10¹⁸オーダーだったり、操作を5000兆回繰り返したりと普通ではありえないくらい大きな数字が出てくることに違和感を覚えます。そこでよく考えてみると、1を除く数字のうち一番増殖度合いが小さい2でさえ、2^5000兆個に増殖するので余裕でKを超えることに気づきます。
つまり、初期状態の数列を左から順に見ていって1以外の数値が出てきたらそこから先はその数字が増殖してくれるので考える必要がないことになります。 ということで左から続く1の数を数えてKと比較して終了。

s = input()
k = int(input())

cnt = 0
for i in range(len(s)):
    if int(s[i]) == 1:
        cnt += 1
    else:
        first_number = s[i]
        break

if k <= cnt:
    print(1)
else:
    print(first_number)

D AtCoder Express 2

これはわからなかった。Q行出力なので最大で10万回ループが必要になります。何も考えずにp<=L かつ R<=qの条件を満たす数をカウントして出力とするとO(MQ)でTLEに確実に引っかかります。
ということで何か配列を作ってそこから参照して計算するだけのアルゴリズムを組む必要があることを推測して、それを考えましたがいいのが思いつかずギブアップ。
L,Rを軸にした二次元の表を考えて累積をあらかじめ計算しておくことで簡略化するんですね。次は解きたい。

（解説より）

さあ、解説にもある通り、余裕で間に合うそうなので実装してみました。

？？？
おや？？？？
Pythonだとこれでも実行時間制限3sに引っかかってしまいました。PyPyでも超ギリギリです。C++なら100倍くらいの短さで通るのですが、ここはPythonで頑張ってみます。細かいところを工夫したらこの方法も通りそうですが（というか通ってくれないと困る）、今回は解説に追記してあった二次元累積和を試してみます。
二次元累積和の説明はこのサイト（→[ABC106] 解法、二次元累積和の使い方 - tqkoh's diary）を参考にしました。

N,M,Q = map(int,input().split())

train = [[0 for i in range(N+1)] for j in range(N+1)]
for m in range(M):
    L,R = map(int,input().split())
    train[L][R] += 1

c = [[0 for i in range(N+1)] for j in range(N+1)]
for i in range(1,N+1):
    cnt = 0
    for j in range(1,N+1):
        c[i][j] = train[i][j] + c[i-1][j] + c[i][j-1] - c[i-1][j-1]

for x in range(Q):
    p,q = map(int,input().split())
    print(c[q][q]-c[q][p-1]-c[p-1][q]+c[p-1][p-1])

これでようやくPythonでも通りました。相変わらず2700msとかでギリギリでした。（いい加減C++を勉強しないと）

まとめ

B,Cが個人的には簡単でした。Dは考えやすい問題ではあったけど結局解ききれなかったので精進したいと思います。