ABC338参加記 - Ang107kの日記

結果

0ペナAB2完でした。
ABCで冷える（しかも大幅）のは数か月ぶりなので悲しいです。
落ち着いたら通せる問題を通せなかった...
気を取り直して、来週も頑張りたいです。

各問題の感想・解法

A問題

書くだけですね。
毎回覚えてないので、アルファベット小文字大文字一覧のリストの作り方メモしておいて良かったです。
istitleなんていう関数もあるらしくてびっくり

以下コード

import string

PY = lambda: print("Yes")
PN = lambda: print("No")

alph_s = set(string.ascii_lowercase)
alph_l = set(string.ascii_uppercase)

s = input()
for i in range(len(s)):
    if i == 0:
        if s[i] in alph_s:
            PN()
            exit()
    else:
        if s[i] in alph_l:
            PN()
            exit()
PY()

B問題

そのままやりました。

以下コード

import string

alph_s = set(string.ascii_lowercase)
s = input()
tmp = {}
for i in alph_s:
    tmp[i] = s.count(i)

tmp = sorted(tmp.items(), key=lambda x: x[1], reverse=True)
print(tmp[0][0])

材料の上限は10と確認して、各料理の最大は10^6と理解＆Aの料理数を決めたときのBの料理数をO(1)で計算できていたにも関わらず、何故か全探索が思い浮かばず、傾きを求める二分探索(名前分かんない）やったり、ＤＰ考えたりしてました。
その二部探索もどきでは、Ａの料理数を、mid-1, mid, mid+1の三種としたた時のAの料理数+Bの料理数を元に傾きに応じて二部探索する感じでやっていたのですが、ＷＡでした。原因としては、横軸Ａの料理数、縦軸Aの料理数+Bの料理数のグラフは、凸であるが、y = 定数となる部分が存在する可能性があるからかなぁ、という感じです。(前後+-1で変化しない場合のl,rの移動ができないため）

うーんダメですね。思考をリセットすることを上手くならなきゃです。
コンテスト後に出したものです。

以下コード

II = lambda: int(input())
MII = lambda: map(int, input().split())
LMII = lambda: list(map(int, input().split()))

n = II()
q = LMII()
a = LMII()
b = LMII()

def solve(num):
    mid = num
    A = [0] * n
    B = [0] * n
    for i in range(n):
        A[i] = a[i] * mid
    idx = 0
    for i, j in zip(A, q):
        B[idx] = j - i
        idx += 1
    tmp = []
    for i, j in enumerate(B):
        if b[i] != 0:
            tmp.append(j // b[i])
    tmp = min(tmp)
    return mid + tmp

tmp = []
for i, j in enumerate(q):
    if a[i] != 0:
        tmp.append(j // a[i])

r = min(tmp)
ans = 0
for i in range(r + 1):
    ans = max(ans, solve(i))
print(ans)

D問題

方針自体は解説と似ていましたが、実装バグらせてACならず。
累積和はインデックスがぐちゃぐちゃになりがちなので、何かいい考え方があるなら知りたいです。（例：index0に余白を持つか、区間の端は+1するかなど）
解説と異なる点としては、累積和で、切断による生じるロスを保存したことです。解説の方は理解できたような出来ていないような、といった感じですが、まあＡＣできたし、嘘解法でも無さそうなので良し。

コンテスト後に出したものです。

以下コード

MII = lambda: map(int, input().split())
LMII = lambda: list(map(int, input().split()))


def dlist(*l, fill=0):
    if len(l) == 1:
        return [fill] * l[0]
    ll = l[1:]
    return [dlist(*ll, fill=fill) for _ in range(l[0])]


# 入力
n, m = MII()
x = LMII()

# 0-indexに変換
x = [i - 1 for i in x]

tmp = [0] * (n)

for i in range(1, m):
    # 移動前後の島
    a, b = x[i], x[i - 1]

    # 順番を昇順に統一
    a, b = min(a, b), max(a, b)

    # 時計回り、反時計回りで移動したときの移動距離
    p, q = b - a, n - b + a

    # 時計回り、反時計回りの移動距離の差
    num = abs(p - q)

    # 時計周りで移動した方が距離が短い場合
    if p < q:
        # a ~ b に含まれる区間を切断した時、反時計周りで移動することになり、移動距離がnum増加する
        # indexをa ~ b全て更新するとTLEするため、区間の端の差分のみを保存
        tmp[a] += num
        tmp[b] -= num

    # 反時計周りで移動した方が距離が短い場合
    elif p > q:
        # b ~ n,0 ~ a に含まれる区間を切断した時、時計周りで移動することになり、移動距離がnum増加する
        tmp[0] += num
        tmp[a] -= num
        tmp[b] += num

# 累積和(各区間を切ることにより生じる、移動距離の増加分)
prf = list(accumulate(tmp))

# 切断前の最短の移動距離を計算
dis = 0
for i in range(1, m):
    a, b = x[i], x[i - 1]
    a, b = min(a, b), max(a, b)
    p, q = b - a, n - b + a
    dis += min(p, q)

# 切断前の最短の移動距離と、最適に切断したときに生じる移動距離の増加分の和を出力
print(dis + min(prf))

結果

各問題の感想・解法

A問題

B問題

C問題

D問題