AtCoder ABC 161

ABC3完緑パフォでした。以下振り返りと反省。

ABC Swap

問題のリンク

概要

• 箱に数字が入っている。
• との中身を入れ替える。
• との中身を入れ替える。
• 最終的な数字の中身は？

制約

• 
• 入力は全て整数

考察

勿論一発でprint(Z, X, Y)で行けるし、分かってるんだけど、凡ミスが怖くて謎にダラダラ書きました。（あとで振り返ると逆に間違いやすい気もしなくもない。）

コード

X, Y, Z = map(int, input().split())
X, Y, Z = Y, X, Z
X, Y, Z = Z, Y, X
print(X, Y, Z)

B - Popular Vote

問題のリンク

概要

• 種類の商品について人気投票をした。投票結果は数列
• 得票数が 以上の商品を選べる。
• 選べる商品数がM以上か否か。

制約

• 
• 
• は異なる
• 入力は全て整数

考察

普通に全探索した。ちなみにこの問題、出力結果を Yesではなく、YESにしてしまって1WAしてしまいました。C以下の問題で1ペナはきつい。。

コード

N, M = map(int, input().split())
A = list(map(int, input().split()))
to = sum(A)
cnt = 0
for a in A:
    if a>=(to * (1/(4*M))):
        cnt += 1

if cnt >= M:
    print('Yes')
else:
    print('No')

C - Replacing Integer

問題のリンク

概要

• 整数に対して、以下の操作を好きな回数だけ処理できる時、取り得る値の最小値を求めよ。
• 操作：をとの差の絶対値で置き換える。

制約

• 
• 
• 入力は全て整数

考察

• 制約を見るからに全探索はできない。
• 割り切れるだけ割り切った数。もしくはそこから更にを引いた数が0付近に集まるので、小さくなりそう。

コード

N, K = map(int, input().split())
mod = N%K
print(min(mod, K-mod))

D - Lunlun Number

問題のリンク

概要

• 隣あうどの2つの桁の値についても、差の絶対値が1以下の数をルンルン数と定義する。
• 1から数えて番目に小さな数を求めよ。

ここはどうやるのか、全然分からず本番中に手も足も出ませんでした。

制約

• 
• 入力は全て整数

考察

• 取り敢えず全探索がダメってとこで止まってしまった。
• 本番後の解説でキューを使うという文言を見て、色々試行錯誤した結果以下のようなコードに、実際に値を取り出してはいないものの、iをイテレータで回していることで、headを1つずつずらしてる。

コード

K = int(input())
Q = list(range(1, 10))
 
for i in range(K):
    x = Q[i]
    y = x%10
    if y != 0:
        Q.append(10*x + y-1)
    Q.append(10*x + y)
    if y != 9:
        Q.append(10*x + y+1)
 
print(Q[K-1])

• 連続した数字が3つ（もしくは2つ）規則的に出てきてるなってのは実際に数列を手書きしている中で気づいた。
• それをキューを使って実装しようという発想が本番中は全く出てこなかった。反省。

E - Yutori

問題のリンク

概要

• 日間のうち、日間働く。
• ある日働いたら、その直後の日間は働かない。
• のi文字目が x の時は働かない。

解説みて、どう実装すれば良いかはひとまず分かった。でもなぜその様に考えられるかは分かった様な分からない様な感じ。

制約

• 
• 
• 
• の長さは
• の各文字はx or o
• 問題文中の条件を満たすように働く日を選ぶことが可能

方針

スライド作ってみた。

コード

N, K, C = map(int, input().split())
S = list(input())
rS = S[::-1]
lcnt, rcnt = 0, 0
left, right = [0]*N, [0]*N
llimit, rlimit = -1, -1

for i in range(N):
    # 左から貪欲
    # llimit (数字がカウントされた日+C日)以降
    # 上記かつ、シフトに入れる日 ('o')であればシフトに入る。
    if S[i] == 'o' and llimit<i:
        lcnt += 1
        left[i] = lcnt
        llimit = i + C

    # 右から貪欲
    if rS[i] == 'o' and rlimit<i:
        rcnt += 1
        right[-(i + 1)] = K + 1 - rcnt
        rlimit = i + C

#print(left)
#print(right)

# leftとrightで同じ数字が入っている日にちを出力
for i in range(N):
    if left[i]==right[i] and left[i]>0:
        print(i + 1)

AtCoder ABC 160

　3完でした。DはTLEでしたが、コンテスト終了後にPyPyを選択するとコードの書き換えなしでACでした。。。後の祭りですが、次回からはPythonだけでなく、PyPy試す事忘れずにいきたい。

（2020年4月1日　E問題追記）

A - Coffee

問題のリンク

概要

　文字列の3文字目と4文字目、及び5文字目と6文字目が等しいかどうか。

考察

　特になし

コード

S = input()

if S[2]==S[3] and S[4]==S[5]:
    print('Yes')
else:
    print('No')

B - Golden Coins

問題のリンク

概要

　X円が与えられた時、以下の条件下で喜びを最大化させる。

• 500円硬貨 1枚につき喜び+1000

• 5円硬貨 1枚につき喜び+5

制約

• 

• は整数

考察

• 500円と5円以外は無価値。さらに1円当たりの効果率で言えば、5円玉より500円玉の方が良い。

コード

X = int(input())
n500 = X//500
mod = X%500
n5 = mod//5

print(n500*1000 + n5*5)

C - Traveling Salesman around Lake

問題のリンク

概要

　1週K メートルの湖の周りにN軒の家がある。全ての家を訪れる時の最短距離を求める。

制約

• 

• 

• 

• 入力中のすべての値は整数である。

考察

• N軒全ての家を訪れた時点で探索終了ということは、家々の間（家1と家2, 家2と家3, ...）でどれか一つは通らなくても良いということ。であればその中で最も距離が大きいところを除けば、より最短距離で目的が達成できる。

コード

K, N = map(int, input().split())
A = list(map(int, input().split()))

dist = [0] * (N)  # 家々間の距離を初期化
for i in range(N):
    if i != N-1:
        dist[i] = A[i+1] - A[i]  # 家々間の距離を更新
    else:
        dist[i] = K-A[i] + A[0]  # 最初の家とラストの家の間は単純な引き算ではない

print(sum(dist) - max(dist))

D - Line++

問題のリンク

概要

　典型的な最短路問題。制約が結構厳しい。range(N)でループ三回回すとN⁹超える。

制約

• 

• 

• 

• 入力中のすべての値は整数である。

考察

　最初から最後までダイクストラ法でチャレンジ。

コード1

　Python3では通らず、PyPyでは通るくらい。工夫した点としては、以下の二つ。

• 中継地点を1 ~ Nまで全て探索するのでなく、バイパスのみに絞る。

• 上記の処理をするためにSの初期化を工夫（一律Nではない）

from itertools import combinations

N, X, Y = map(int, input().split())

# Sを単純に初期化するのではなく、[2, 1, 0, 1, 2, 3, ...]の様にソートされた状態で初期化
S = [list(reversed(list(range(1, i+1)))) + list(range(N-i)) for i in range(N)]

# バイパスの距離は1
S[X-1][Y-1] = 1
S[Y-1][X-1] = 1

for i in range(N):
    for j in range(N):
        x, y = X-1, Y-1

        # バイパス経由の方が近い場合、距離更新
        S[i][j] = min(S[i][j], S[i][x]+1+S[y][j])

dist = [0]*N
for i, j in combinations(list(range(N)), 2):
    d = S[i][j]
    dist[d] += 1

for i in range(1, len(dist)):
    print(dist[i])

コード2

　終了後に他の人のコードを見て、なるほどと思ったので貼っときます。（ちょっと改変してます）

N, X, Y = map(int, input().split())
ans = [0]*N

for i in range(1, N):
    for j in range(i+1, N+1):
        d = min(j-i, abs(X-i)+abs(Y-j)+1)
        ans[d] += 1

for i in ans[1:]:
    print(i)

　上手いと思ったのは、以下の点

• S（二次元配列）を作ってない。そもそもバイパスが存在しなければ、iとjの距離はj-iが保証されているためこの手が使える。

• 上記に伴って、一度のfor文でans[d] += 1まで処理できてる。自分のコードはS更新後にitertools.combinationsを使ってしまってるので、そこで更に処理時間がかかってしまっている。

E - Red and Green Apples

問題のリンク

コンテスト後にやってみたけど5分くらいで解けた。。。他の人も言っていたけどE問題にしては難易度高くなかったようです。こういうこともあるので、次回のコンテストからは先の問題も目を通していきたい。

概要

• 赤いリンゴをX。緑のリンゴをY個食べる。
• それぞれのリンゴには美味しさ（整数）がある。
• 美味しさを最大化させるようにリンゴを食べた場合、その最大値を求めることが今回のタスク
• 色がついてない無色のリンゴも存在し、赤と緑のどちらにも代用可能

制約

• 

• 

• 

• 

• 

• 

考察

1. 制約より、無色のリンゴが存在しないと仮定すると、赤いリンゴA個の中から大きい順にX個食べる & 緑のリンゴB個の中から大きい順にY個食べることで、美味しさを最大化することができる。

2. 無色のリンゴはどちらの色にも代用可能であることから、上記でセレクトされたリンゴのうち美味しさの少ないものと無色のリンゴをチェンジしていけば良い。

コード

X, Y, A, B, C = map(int, input().split())
p = sorted(list(map(int, input().split())), reverse=True)
q = sorted(list(map(int, input().split())), reverse=True)
r = sorted(list(map(int, input().split())), reverse=True)

eat_p = p[:X]
eat_q = q[:Y]
eat = sorted(eat_p + eat_q)

for i in range(min(len(eat), len(r))):
    if eat[i] < r[i]:   # 元々のリンゴより無色のリンゴの方が美味しい場合
        eat[i] = r[i]
    else:
        break

print(sum(eat))