AtCoder Beginner Contest 139 A~D（過去問） - 「三日坊主にならないようにがんばるぞ！」なブログ

A問題

2つの等長文字列SとTが与えられた時、それぞれのn文字目が一致している回数を数える問題 atcoder.jp

コード

#!/usr/bin/env python3
#### input
S = input()
T = input()

#### process
score = 0
for i in range(0, len(S)):
  if S[i] == T[i]:
    score = score + 1

print(score)

B問題

コンセント穴が1つだけある
差込口をA個持つ電源タップが複数ある
B個のコンセント穴を使いたい

このとき、最小で何個電源タップを使えばよいか atcoder.jp

所感

電源タップを差し込む時に一個のコンセントを使うので、電源タップを差し込むごとにA-1だけコンセント穴が増える
ただし、最後に差し込んだ電源タップではすべてのコンセント穴が空いているのでAだけコンセント穴が増える

ある電源タップにあらかじめコンセントを1個差し込んでおき、この電源タップが最後に差し込む電源タップになるようにすると、「電源タップを差し込むたびにA-1だけコンセント穴が増えるとき、B-1個のコンセント穴を作るために必要な最小の電源タップ数は何か」という問題になるので、割り算を使って解ける

コード

#!/usr/bin/env python3
import math

#### input
A, B = map(int, input().split())

#### process
print(math.ceil((B-1)/(A-1)))

C問題

長さ \( N \) の数列 \( H_1, H_2, ..., H_N \) が与えられた時、\( H_k \geq H_{k+1} \) は最大で何連続成立するかを求める問題

atcoder.jp

所感

\( 1 \leq N \leq 10^5 \)なので、先頭から全部見ていっても間に合う

コード

#!/usr/bin/env python3

#### input
N = input()
H = list(map(int, input().split()))

#### process
now_step = 0
max_step = 0
for i in range(0, len(H)-1):
  if H[i] >= H[i + 1]:
    now_step = now_step + 1
  else:
    max_step = max(max_step, now_step)
    now_step = 0

max_step = max(max_step, now_step)

print(max_step)

D問題

\(1〜N\)の整数が順番に並んだ整数列\(A\)と、\(1〜N\)の整数を並び替えてできる整数列\(B\)（長さ\(N\)）があるとき、\( \displaystyle \sum_{k=1}^N (A_k \ mod \ B_k) \) の最大値を求める。\( 1 \leq N \leq 10^9\)

atcoder.jp

所感

Nの大きさ的にN回のループ（＝数列の各要素を処理）すら許容されないので、整数問題として考えるのが良さそう。
整数問題の定番としてとりあえずN=1から試していく。 N=1からN=4まで、順列を全通り書いて試してみたところ、

N=1のとき：[1]に対して順列[1]を用意して答えは0
N=2のとき：[1,2]に対して順列[2,1]を用意して答えは1
N=3のとき：[1,2,3]に対して順列[2,3,1]を用意して答えは3
N=4のとき：[1,2,3,4]に対して順列[2,3,4,1]を用意して答えは6
　となったので、[2,3,4, ..., N, 1]の順列を用意すれば良さそうで、その時の余りは下記で求められる。

\( \displaystyle \sum_{k=1}^{N-1} k = \dfrac{N(N-1)}{2} \)

改めて考えてみると、1〜Nの中で除数としたときに最も剰余を多くできるのはN（最大の剰余はN-1）であり、当然ながら1〜Nの中でこれを満たすためにはN-1を被除数に取るしかない。よってNとN-1、N-1とN-2を対応付けしていき、最後に余った1とNを組み合わせるのが最も剰余を最大化することがわかる。

なんだ今回チョロかったなと思いながら実装へ（フラグ）

コード（１回目）

#!/usr/bin/env python3

#### input
N = int(input())

#### process
print(int(N*(N-1)/2))

結果（１回目）

WAが２つ（絶句）

所感（２回目）

数学的にも合っているはずなのにどうして。。。

上記の証明が間違っている可能性も含め、色々検討した。

N=1〜4を書き出した時、最大の剰余和を生成する順列は[2,3, ..., N, 1]以外にもパターンがあったことを思い出し、そこにヒントがあるかもしれない
整数問題のよくあるパターンとしてNが素数の時に何か起こるのかもしれない
とりあえず全通り解かせて見るかと思いN=11（数分かかる）くらいまで全部計算させて法則が破れたりしないか確かめる

とか色々やってみたけど、まったくわからず。ここで、そういえばめちゃめちゃ大きい数字を扱うと丸め誤差とかで値がおかしくなることがあったなということを思い出し、改めて調べてみるとドンピシャ。 float型に変換されるときに丸め誤差が悪さをするので割り算の実行タイミングを考慮する必要があった。久々に意識したな、丸め誤差・・・。

（参考）

>>> int(999999999*999999998/2)
499999998500000000　　# 2で割った後の1の位は0だが、

>>> int(999999999*999999998)
999999997000000002　　# 2で割る前の1の位は2・・・？

>>> a=999999999
>>> b=int(a/2)　　　# 先に割っておく
499999999
>>> a*b
499999998500000001     # めでたしめでたし

コード

#!/usr/bin/env python3

#### input
N = int(input())

#### process
if N % 2 == 0:
  tmp = int(N/2)
  print(int(tmp*(N-1)))
else:
  tmp = int((N-1)/2)
  print(int(tmp*N))