takuroooのブログ

勉強したこととか

AtCoder Beginner Contest 139

AtCoder

9/1のABC139は4AC5WAだった。初めてコンテスト中にD問題解けたけど、いつものD問題よりも難易度が低く正解している人が多かった印象。

atcoder.jp

A問題

問題

3文字の文字列が２つ入力されて何文字一致しているかカウントする問題。

自分の回答

単純にループで数えただけ。他の人の回答も同じような感じだった。

s=input()
t=input()
 
cnt=0
for i in range(3):
    if s[i] == t[i]:
        cnt+=1
print(cnt)

B問題

問題

整数A、Bが与えられて、Aを1回加算するという操作を何回繰り返すとBにたどり着くかという問題。しかし、Aを1回加算するという操作を行うたびに合計数が-1される。初期値は1。 なので操作を1回行うと、合計数に A-1 が加算される。

自分の回答

上記操作をループで実行すればいいのだけれどもここで1WAしてしまった。

間違ったコード
def MAP():
    return map(int, input().split())
 
a,b=MAP()
 
t=1
cnt=0
while True:
    t -= 1
    t += a
    cnt += 1
    # このif文がループの先頭になければならない
    if b <= t:
        break
print(cnt)

このコードだとループの中の処理が必ず１回行われてしまう。そのため入力のB(プログラムの変数ではb)が1のときに間違った答えを出力してしまう。

正解したコード
def MAP():
    return map(int, input().split())
 
a,b=MAP()
 
t=1
cnt=0
while True:
    # if文をループの先頭に移動した。
    if b <= t:
        break
    t -= 1
    t += a
    cnt += 1
print(cnt)

ループを抜けるif文をループの先頭に書いて条件を満たしている場合は何もしないで抜けるようにした。
最初からちゃんとwhile t < b:と書いておけばよかった...境界条件は今後注意してしていこうと思う。

他の人の回答みて勉強になったこと

そもそもループしないでも

  • 1回の操作でA-1を加算する。
  • 初期値は1

なので(B - 1) \div (A - 1) （切り上げる）で答えがでる。切り上げは以下のように書くことができる。

def ceil(x,y):
  return -(-x//y)

print(ceil(b-1, a-1)

C問題

問題

長さNのある数列が与えられて自分 >= 右隣が最大何回続くか？という問題。

自分の回答

1 <= N <= 105 なので単純にループで数えていけばいい。
自分 >= 右隣 ならカウンターを+1する。
自分 < 右隣 ならカウンターをリセットする。
を繰り返していき、カウンターの最大値を求める。

ちなみに与えられる数列がものすごく長い場合、sys.stdin.readline()を使うとinput()より数百msec速くなったことがあるので、こっちを使うようにしている。

import sys

input = sys.stdin.readline

def LIST():
    return list(map(int, input().split()))

N=int(input())
H=LIST()

p=H[0]
cnt = 0
max_cnt = 0
for h in H[1:]:
    if p >= h:
        # 自分 >= 右隣
        cnt += 1
        max_cnt = max(max_cnt, cnt)
    else:
        # 自分 < 右隣
        cnt = 0
    p = h

print(max_cnt)

D問題

問題

ある数列A={1,2,...,N}とそれを並べ替えた数列P={P1,P2,...PN}があって、

A[0] % P[0] = M0
A[1] % P[1] = M1
A[2] % P[2] = M2
・
・
・
を合計していったとき、最大値がいくつになるか？という問題。(%は余りを求める演算子)
Pをどうやって並べるかは自由。

自分の回答

例えば、A={1,2,3,4,5}だった場合、P={2,3,4,5,1}という数列Pを作ると余りの合計が最大値になる。

  • 1 % 2 = 1
  • 2 % 3 = 2
  • 3 % 4 = 3
  • 4 % 5 = 4
  • 5 % 1 = 0

つまり自分より+1大きい数に割ってもらえれば、余りが自分自身になり、それが余りとしての最大値になる。
（4だったら、5(=4+1)に割ってもらえれば、余りは4になる。）

これを考慮すると余りの合計とは1〜N-1の総和ということになる。（上記例だと1,2,3,4を足したものが答え）
1〜Nの総和はガウスの公式で

(N+1) \times N \div 2

で求めることができる。

...なのだけれどもコンテスト中にいろいろ勘違いしてしてしまって回答が汚くなってしまったので割愛。 綺麗に書けば以下のように2行程度で書ける。

N = int(input())
print((1+N-1)*(N-1)//2)

結果

5WAが効いて茶色パフォーマンス止まりだった。 f:id:takuroooooo:20190908191341p:plain