AtCoder Beginner Contest 106

解説放送: AtCoder Beginner Contest 106 解説放送 - YouTube

A - Garden

問題

農夫ジョンは縦 $A$ ヤード、横 $B$ ヤードの長方形の畑を持っている
畑には、縦、横にそれぞれ幅1ヤードの道がある
道を除いた畑の面積は何平方ヤードか

解法

■■■□■■■■■■
■■■□■■■■■■
□□□□□□□□□□
■■■□■■■■■■
↓
■■■■■■■■■□
■■■■■■■■■□
■■■■■■■■■□
□□□□□□□□□□

道を端に移動させても面積は変わらないので、A、Bからそれぞれ道の分の1ヤードを引いた長さで長方形の面積を求めればよい。

どこかなつかしみを感じる。

w, h = map(int, input().split())
print((w - 1) * (h - 1))

B - 105

問題

105のように、約数がちょうど8個ある $N$ 以下の奇数の個数を求めよ
$N \le 200$

解法

ABC105で出したかったんだろうなあという問題。

約数の個数は素因数分解で計算できる。たとえば $3^2 \times 5^3 \times 7$ になったら、指数の部分に1を足したものを掛け合わせて $(2+1)\times(3+1)\times(1+1)=24$ 個となる。

この説明は約数の個数の公式と平方数の性質 | 高校数学の美しい物語とか解説サイトに詳しい。

これが8個になる、しかも奇数ということは、奇数の素因数だけを使って

$3 \times 5 \times 7$ のように、3つの数を1つずつ掛け合わせると $(1+1)\times(1+1)\times(1+1)=8$
$3^3 \times 5$ のように、1つの数を3つ、1つの数を1つ掛け合わせると $(3+1)\times(1+1)=8$
$3^7$ のように、1つの数を7つ掛け合わせると $(7+1)=8$

のいずれかが該当する。$N \le 200$ なので、結局以下の5つのみ該当する。

$105=3 \times 5 \times 7$
$135=3^3 \times 5$
$165=3 \times 5 \times 11$
$189=3^3 \times 7$
$195=3 \times 5 \times 13$

なんてことは全く考えず、素直に全部試すのが早い。

n = int(input())
ans = 0

for i in range(105, n + 1, 2):
    c = 0
    for d in range(1, i + 1, 2):
        if i % d == 0:
            c += 1
    if c==8:
        ans += 1

print(ans)

C - To Infinity

問題

文字列 $S$ は、1～9の数字よりなる
$S$ は、1日ごとに、'2'は'22'に、'3'は'333'に、'9'は'999999999'に、各数字が、数字の数だけ並んだ数に変化する
5000兆日後、左から $K$ 番目の数字は何か
$1 \le |S| \le 100$
$1 \le K \le 10^{18}$

例

 現在  1324
1日後→1333224444
2日後→133333333322224444444444444444

解法

5000兆日≒14兆年≒215億エンドレスエイト。

'1'は'1'のまま変わらないが、他は、一番小さい'2'でさえ5000兆日後には $2^{5000兆}$ 個並ぶことになる。これは10の底で表すと $10^{1.5兆}$ くらいになる。$K$ などもはや関係ないスケールで、先頭付近は見渡す限り最初に出てきた文字のみが並んでいる状態となる。

S         : 11213
5000兆日後: 1122222222......(悠久の2)......2222221333333......
                       ↑
          Kの制約10^18 この辺

よって、$S$ の先頭 $K$ 文字の中で、最初に'1'以外で出てきた数字が答えとなる。先頭 $K$ 文字が全て'1'なら、答えは'1'となる。

s = input()
k = int(input()) - 1
for i, c in enumerate(s):
    if i == k:
        print(c)
        break
    if c != '1':
        print(c)
        break

D - AtCoder Express 2

問題

東西に一直線に伸びる線路に、$N$ 個の都市、$M$ 本の鉄道路線
$i$ 番目の鉄道路線は、都市 $l_i$～$r_i$ の区間を走行する。$l_i=r_i$ である場合もある
質問が $Q$ 個与えられる
$i$ 番目の質問は「都市 $p_i$～$q_i$ の区間に、走行区間が完全に含まれる路線はいくつあるか」
全ての質問に答えよ

例

       1 ===== 2 ===== 3 ===== 4
鉄道1  |-------|
鉄道2  |---------------|
鉄道3          |---------------|
鉄道4                 |-|
鉄道5                  |-------|

質問1  |--------|                 -> 鉄道1の1つ
質問2         |-----------------| -> 鉄道3,4,5の3つ

解法

$N \le 500,Q \le 100000$ が制約のため、だいたい1クエリ $O(1)$ か、せいぜい $O(N)$ で解けるように前計算しとくんだろうと予測を付ける。

ゴールから考えてみる。前計算で用意しておくべき情報はどんなのがいいか。たとえば $ANS$ という配列を用意して答えを $ANS[p][q]$ で一発で取ってこれるようにしておくとしたら、上の例はこんな感じになる。

          q
      1  2  3  4
    +-----------
  1 | 0  1  3  5
p 2 | 0  0  1  3
  3 | 0  0  1  2
  4 | 0  0  0  0

横で見ても縦で見ても累積和っぽい形になっている。

数直線上で具体的に考えても、$p_i$ が小さいほど、$q_i$ が大きいほど、区間が広がるので答えは単調に大きくなる。そのことからも累積和の方針はよさそう。

と、方針を仮決めしたところで累積和の元となる配列を考える。仮に、区間 $l$～$r$ を走る路線の個数を $D[l][r]$ で表すと、こんな感じになる。

          r
      1  2  3  4
    +-----------
  1 | 0  1  1  0
l 2 | 0  0  0  1
  3 | 0  0  1  1
  4 | 0  0  0  0

これを横に累積和を取ると、$D[l][r]$ は以下を意味するようになる。

$l$ を左端に持ち、$r$ までに走行区間が完全に含まれる路線の数

          r
      1  2  3  4
    +-----------
  1 | 0  1  2  2
l 2 | 0  0  0  1
  3 | 0  0  1  2
  4 | 0  0  0  0

たとえばクエリで $p=2,q=4$ が与えられた時、上の累積和の表を利用すると答えは以下の和となる。

4を左端に持ち、4までに走行区間が完全に含まれる路線の数
3を左端に持ち、4までに以下同
2を左端に持ち、4までに以下同

          r
      1  2  3  4
    +-----------
  1 | 0  1  2  2
l 2 | 0  0  0 ①
  3 | 0  0  1 ②
  4 | 0  0  0 ⓪

なので、これも縦を基軸に累積和でまとめられそう。下から上に累積和を取ると、以下のようになり、最初に求めたかった $ANS$ に一致する。

          r
      1  2  3  4
    +-----------
  1 | 0  1  3  5
l 2 | 0  0  1  3
  3 | 0  0  1  2
  4 | 0  0  0  0

実装

行列の入れ替え

Pythonでは、2次元配列aの行列の入れ替えは、zip(*a)でできる。ただし型に関する注意点が2つある。

1つは各列がtuple型になっている。これはまぁ、値の更新などしない限りlistと変わらないのでそこまで問題ではない。

もう1つはzip()自体の返値がiterable型になること。要はfor文では回せるけど添字でa[0]のようにはアクセスできない型なので、そのまま添字アクセスをしたい場合はlist(zip(*a))としてlistに変換しておく必要がある。

入出力

この問題のように入力が $10^5$ 行に及ぶ問題は、input()で1行ずつ取得するより、sys.stdin.readlines()でまとめてリストとして取得した方がコンマ数秒も速い。input()と異なり行末の改行が残るが、int()に渡すと関係なく処理してくれる。

同様に出力も $10^5$ 行に及ぶので、1行ずつprint()するより、改行で結合したものを一度に出力 print('\n'.join(buf)) した方が速い。

正しい解法なのに入出力の問題でTLEになることはそこまで多くない（とはいえ皆無なわけでもない）が、覚えておくと得。

import sys
from itertools import accumulate

n, m, q = map(int, input().split())
ipt = sys.stdin.readlines()
rails = [[0] * n for _ in range(n)]
for line in ipt[:m]:
    l, r = map(int, line.split())
    rails[l - 1][r - 1] += 1
rails = [accumulate(s) for s in rails]
rails = [list(reversed(list(accumulate(reversed(s))))) for s in zip(*rails)]
buf = []
for line in ipt[m:]:
    p, q = map(int, line.split())
    buf.append(rails[q - 1][p - 1])
print('\n'.join(map(str, buf)))

目次