■■■□■■■■■■ ■■■□■■■■■■ □□□□□□□□□□ ■■■□■■■■■■ ↓ ■■■■■■■■■□ ■■■■■■■■■□ ■■■■■■■■■□ □□□□□□□□□□
道を端に移動させても面積は変わらないので、A、Bからそれぞれ道の分の1ヤードを引いた長さで長方形の面積を求めればよい。
どこかなつかしみを感じる。
w, h = map(int, input().split()) print((w - 1) * (h - 1))
ABC105で出したかったんだろうなあという問題。
約数の個数は素因数分解で計算できる。たとえば $3^2 \times 5^3 \times 7$ になったら、指数の部分に1を足したものを掛け合わせて $(2+1)\times(3+1)\times(1+1)=24$ 個となる。
この説明は 約数の個数の公式と平方数の性質 | 高校数学の美しい物語 とか解説サイトに詳しい。
これが8個になる、しかも奇数ということは、奇数の素因数だけを使って
のいずれかが該当する。$N \le 200$ なので、結局以下の5つのみ該当する。
なんてことは全く考えず、素直に全部試すのが早い。
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)
'2
'は'22
'に、'3
'は'333
'に、'9
'は'999999999
'に、各数字が、数字の数だけ並んだ数に変化する現在 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
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]$ は以下を意味するようになる。
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$ が与えられた時、上の累積和の表を利用すると答えは以下の和となる。
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)))