AHC031でA:緑, H:水の駆け出し競プロerが最終15位達成した話【MC Digital プロコン2024】

始めに

先日行われたAHC031にて、システムテスト15位を達成することができました。

私としては異例の好成績であるため、とても喜んでいます。
良い成績を残せた記念も兼ねて参加記を書くことにしました

以下簡単に自己紹介失礼します。

• 一年ほど前にAtCoderを始め、昨年12月からHコンにも参加し始めた、駆け出し競プロer
• 情報系の大学生
• アルゴリズム : 緑
• ヒューリスティック : 水

自己紹介に前述したとおり、レートも高くなく、経験も浅いため、高度なテクニックは使用していない(できていない）ので、理論や数学的な分析は殆ど書けないです。発想やお気持ちの部分に重点を置いて書いていくので、その辺ご了承ください。記事内で使用される用語に関しても、雰囲気で使っているので、間違っている可能性があります。

また、問題についてある程度、理解・考察が済んでいる前提で話は進めます。

全体を通した感想

賞金も貰えて、レートも増えて、一枚目に名前を残せて、何より嬉しい気持ちが強いです。結果だけでなく、コンテスト自体も、長期コンあるあるの抜きつ抜かれつの感じが楽しかったです。上位三人は、全く異なる革命的な解法を持っているのかなと思っていたのですが、箱を開けてみれば、同じ方針ということで、同じ方針でもこんなにも差が着くのだなぁ、と驚きました。

高速化が必要ということで、初めての試みとしてPythonをNimに移植したのですが、スコアも二倍近くに上がり、Nimの勉強もできたので充実した十日間になりました。

勝因は、

• 学生で春休みということもあり、時間だけは誰よりもあったので、Hコンにフルコミットできたこと
• 序盤に横の分割を固定するという発想に至れたこと
• Nimはいいぞ、宣伝してくれていた某羊さんがいたこと(マクロもお借りしました)

かなと思います。

初日から最終日まで1ページ目と2ページ目を行ったり来たりしていたのですが、好成績の副産物としてか、ツイッターのFFが増えました。嬉しいです。大した事呟いてませんが、よければフォローお願いします。

問題概要

詳細はこちらをご覧ください。
自分なりに要約したものを以下にまとめます。

• 1000 * 1000の正方形のエリアがある。
• D日間、それぞれN個の面積が与えられる。
• 正方形の中に、N個の長方形区画を割り当てるのが貴方の仕事であり、長方形区画の外周(正方形の外周は除く)にはパーティションを設置する必要がある。
• 但し、パーティションは格子点を通り、正方形の辺に平行、垂直な直線でなくてはならない。
• 初日の設置コスト、最終日の撤去コストを除き、パーティションを設置、撤去するには長さに比例すたコストが掛かる。
• また、要求された面積よりも少ない面積を割り当てた場合、ペナルティとして大幅なコストが掛かる。
• 掛かるコストがなるべく小さくなるように、長方形区画を割り当てよ。

最終提出コードの方針、お気持ち

前提の方針

より多い数の行に分けて固定し、縦線のみを移動させることを考えました。

既に分割された複数行の平面をN個の長方形に分けるには、約Ｎ本の縦線を配置する必要があります。であれば、コストは引いた縦線の長さの総和に依存することになります。その発想から、コストを下げたい->縦線の長さ、即ち各行の高さを小さくしたい->分割数を増やしたいという発想の流れになります。
(実際は、実験の中で、分割数増やしたらスコアが劇的に改善したことから、逆算的に上記のことに気づきました。)
コンテスト序中盤は、より縦横比が小さい正方形に近い形こそが至高だと考えていたため、それに気づいた時は目から鱗でした。

シード5(score = 8825)のビジュアライザは以下のようになります。

前提を達成するための具体的な方針

行の分割数、それぞれの高さの決定

より多くの行に分けたい、という気持ちがありますが、行を増やすほど面積の不足なく配置することの難易度が上がるというトレードオフな問題があります。そこで私は、二分探索を用いて、面積の不足なく配置可能な最大の行数を求めました。
(今思えば小さい方から線形に探索しても良かった気がしますが。)

そこで考えなくてはいけない問題が、行の分割方法、長方形の配置の方法です。貪欲で良い分割や良い配置を求めたいですが、私は思いつきませんでした。
良い分割や、良い配置が存在することは分かるが、それに達する手段が分からない->ランダムに決めて、それの良さを評価できれば、山登りできそう?という思考で山登りで行の分割数とその高さを決定することにしました。

行の分割数を決定する山登りに関する詳細

• 初期解

以下のように適当に作りました。お気持ちとしては、各ケースの面積の特性にマッチした初期解になればいいな～ぐらいで、0.25乗の部分も差が大きすぎるのは悪そう+実験する中で良さげだったという感覚的なものです。

1. 分割数Bは予め決まっている。(上記二分探索のmidに相当)
2. 全日における、i番目に大きい面積の平均Si_avrを計算
3. [S1_avr, S2_avr, S3_avr..., SN_avr]を約N / B個ずつ、B個に分割する。
4. 分割されたB個それぞれの総和を取り、それを0.25乗したものをh[h_1, h_2, h3, ... hB]とする
5. 1000 * (h_i / sum(h))をそれぞれの高さheight_iとする

• 近傍

以下の一つだけです。

1. 減らす行iと増やす行jをランダムに選択
2. 減らす大きさは、1 ～ (height_i / 4)の中でランダムに選択
3. それぞれ、減らす、増やす

• 評価関数

生スコアをそのまま計算
改善すれば採用、悪化すれば不採用のシンプルな山登りです。

与えられた分割数Bそれぞれに対し、この山登りを最大0.3秒行っています。
このパートは、分割行数を求めるのが目的なので、途中で面積を不足なく配置できた場合はその時点で山登りを打ち切るようにしました。

• 配置方法

以下のような適当な貪欲です。
色々試して良さげだったので採用しました。
お気持ちとしては、面積に適した行(大きな面積のものは、高さが大きい行に、小さい面積のものは、高さが小さい行に)に配置されて欲しいという感じです。

1. 面積が大きい順に見ていく。
2. 配置場所は、配置可能な行の中で最も縦横比が小さくなる行とする。
3. どの行にも必要な面積が配置できない場合、はみ出る面積だけコストに加算する以外は特に何もしない。

行の高さを決定する山登りに関する詳細
上記の二分探索と、行の分割数を決定する山登りにより、面積を不足なく配置可能な最大の分割数、B_maxが求まりました。
ですが、このままでは配置は可能ですが、高さとしてはイマイチな状態(っぽい)です。
そこで、二分探索によって最終的に得られた、heightを初期解として、再度山登りを0.3秒実行します。山登りの中身は、面積を不足なく配置できていても続行すること以外はほとんど同じです。

これは、私のローカルテストでは殆どスコアに寄与しなかったのですが、スコアが改善するかつ、heightの分散が小さくなる場合のみ採用するようにしました。お気持ちとしては、後述する別の山登りでスコア増加の確率を上げられそう、というものです。

このパートに関して、後述する別の山登りにより、長方形（縦線）の配置場所はかなり変わるので、意味がないように思えたのですが、行っていた方がスコアが伸びたので採用しました。

ここまでで1.5秒弱くらいを使用しています。

縦線の配置場所の決定

ここまでで、heightを決めることはできましたが、縦線に関しての工夫を一切行っていません。横線は全く動かさないため、それだけでも最低限の改善はできていますが、可能であれば、縦線の移動も抑えたいところです。
そこで、縦線の移動を抑えるため、以下の貪欲法と山登り法による改善を行いました。

貪欲法による改善
二種類の貪欲法による改善方法を用意し、ケースごとに改善量が大きい方を適用するという形を取りました。

• 貪欲法_1

この貪欲は、余る面積が少ない場合に採用されることが多い貪欲法です。

1. 1-2日目, 3-4日目, 5-6日目といった感じで2日ごとで区切り、2日単位での縦線の一致を試みる。
2. 2日間で、まだ使用していない面積のうち、面積の差が最も小さくなるペアを見つけ、i日目, i+1日目両方で、そのmaxを取った場合に配置可能かを判定
3. 配置できれば、ペアの数を増やす、ということを繰り返す

2-3日目, 4-5日目, 6-7日目...で区切るような、偶奇反転した組も試しています。
日付全体で、ペアを作って縦線の場所一致させることができた回数を、偶数スタート、奇数スタートそれぞれで管理して、返すようにしてます。

配置の方法は分割数や高さを決める山登りのものと同じです。

• 貪欲法_2

この貪欲は、余る面積が多い場合に採用されることが多い貪欲法です。

貪欲_1では、2日のペアを作っていたため、ペアとペアの間の部分の縦線は全く考慮していません。
余る面積が大きく、三日以上のペアを作ってもそれなりに一致させられるケースでは、貪欲_1ではイマイチなので、そのカバーを行うような役割を持つ貪欲法になります。

l = 1, r = 2とする。

1. l日目からr日目までの中で、面積の大きい順に見ていき、何個目までmaxを取って配置可能かを判定
2. (N / 2)個以上maxを取れるならばrをインクリメント、そうでないなら打ち切ってl = r, r = r + 1として、再開

これを繰り返します。 (N / 2)個以上というのも適当な数字です。
上記の例では左から見ていく例を示しましたが、右から見る場合も試しています。
日付全体で、ペアを作って縦線の場所一致させることができた回数を、左スタート、右スタートそれぞれで管理して、返すようにしています。

また、l ~ r日目それぞれのi番目に大きい面積のmaxは、セグメントツリーを用いて取得しました。

配置の方法は分割数や高さを決める山登りのものと同じです。

山登り法による改善
山登り法を行う中で、主に管理したものは以下の二つです。
line[ i ][ j ][ k ] = i日目のj行目のk番目に大きい縦線の場所
surf[ i ] = i日目の盤面の長方形の面積の集合

line,surfどちらも、挿入・削除を高速に行いたかったため、tatyamさんが公開しているpythonで使用できるSortedset,SortedMultisetを改造してNim用に移植しました。データの個数は高々50なので速度的な話で、如何ほど意味があったのかは分かりませんが、直感的に操作できるメソッドが用意されていた分、実装はしやすかったです。

• 初期解

lineを初期解としました。
lineは、上記貪欲法で求めた長方形配置から、縦線の場所を抽出しただけのものです。

• 近傍

最終的に採用した近傍は以下の5つです。
lineのi, j, kを乱択し、line[ i ][ j ][ k ]を移動することを考える部分は共通

1. 同一行の、前後日に存在する縦線への移動
2. 異なる行の、前後日に存在する縦線への移動
3. 同一行の、ランダム左右移動
4. 異なる行へのランダムワープ
5. 左右にある長方形の場所のスワップ(実質的には1つの縦線の左右移動)

以下近傍設定のお気持ちです。

• 1,2の近傍は直接スコアに寄与する部分なので外せない。
• 3,4の近傍は直接スコアには寄与しないが、1,2だけだと局所解にすぐはまってしまいそうだったので、盤面を良い感じに混ぜて欲しい。
• 5の近傍は評価にかかる計算が軽いため、3,4ほどバリエーションは無いが、軽い計算で盤面を良い感じに混ぜて欲しい。

前述した、heightの分散が小さくなるようにした、というのは、2,4近傍での改善を意識したからになっています。高さが近ければ異なる行への移動の際にも面積変化が少なくて良さそう~と思いましたが、スコアは殆ど変わりませんでした。

割合は、[1,1,1,2,2,3,4,5]としました。と言っても、私が実装した各近傍はそれぞれ探索範囲が異なるので、割合に関しては実装に左右されると思います。
色々と試す中で、これらの近傍をこれくらいの割合で入れると良さげでした。

実装したものの採用されなかった近傍は以下の三つです。

6. 行をまるごと左右反転
7. 二つの行を上下スワップ
8. 同一行の、前後日に存在する縦線との平均への移動

以下近傍設定のお気持ちです。

• 6,7の近傍は盤面を大きく混ぜて欲しい。
• 8の近傍は近傍1,2以外でのスコアに寄与する近傍が欲しい。

いま改めて、採用された近傍、採用されなかった近傍を見比べると、変化量が大きすぎる近傍は良くないのかなー、と感じています。6,7,8全てにおいて、動く縦線が複数なのに対し、1,2,3,4,5はどれも1行のみなので。
それから、各近傍の探索範囲は小さい方が良いのかな、みたいなことも今記事を書きながら考えました。一つの近傍の中で探索範囲を広げても、その盤面から遷移可能な範囲しか到達できないため、それならば、一回当たりの探索量を抑えて、より多様な盤面から探索を試みた方が良さそう、という発想です。

• 評価関数

以下の二つの基準を評価関数としました。

1. 移動した後の盤面の中に、必要な面積を配置可能かどうか
2. 移動したとして、スコアが悪化しないか

1の面積を配置可能かどうかに関しては、移動後の面積の集合と、その日に要求される面積の集合を比較し、N個全ての長方形において、移動後の面積 >= 要求される面積が満たされるかを判定しました。
その際に、一度盤面上の面積の集合に追加、削除を行い、受け入れられたらそのまま、却下されれば追加削除の逆のことを行いました。毎回新規の集合を作らない分、速度的にメリットがありそう、と思って実装したのですが、実際のところは不明です。

2の移動したとして、スコアが悪化しないか、これに関しては、前後日の移動前と移動後の場所の縦線の存在判定さえできれば計算することができます。

どちらの判定においても、line[ i ][ j ]、surf[ i ]をソートされている状態をキープすることで、高速化できるため、前述のSortedset,SortedMultisetを用意しました。

終わりに

ここまで読んで頂き有難うございました。
最終提出コードはここから見られるので、必要であればご覧ください。

これからも引き続き競技プログラミングを楽しんでいくので、応援よろしくお願いします。

誤植、勘違い、アドバイス等ありましたら以下ツイッターアカウントまでお気軽にご連絡ください。
https://twitter.com/Ang_kyopro

ABC338参加記

結果

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])

C問題

材料の上限は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))

ARC170参加記

結果

†0完†でした。
二時間椅子を温めて、レートは冷えました。
悲しい。
ARCはAtCoder始めたての頃に一度だけ参加して一問も解けず、それ以来半年ぶりくらいの参加だったのですが、ダメでした。
維持する価値のあるレートでも無いので、これからもratedで挑戦し続けようと思います。

各問題の感想・解法

A問題

問題見たときは、そぐできそうじゃん、と思ったのですが、WAが取れず...
本番中はSをTに一致できるか、とできる場合の最短手数を同時に求めようとしていたせいで、色々ぐちゃぐちゃになってしまっていました。落ちてるケースが分からないので、後半はかなり迷走していました。
コンテスト終了後落ち着いて、SをTに一致できるかを先に判定し、後は可能である前提がある状態での最短手数を求める方針で書けば15分ほどで書けたので、悔しいです。

本番中に、現コードの修正を辞め、切り替えて一から書き直すべきかを見極める力みたいなのも必要だと感じました。次のARCではリベンジしたいです。

ABC337参加記

結果

0ペナ4完でした。
温まったので良かったですが、
１時間以上かけてE問題通せなかったので悔しいです。

各問題の感想・解法

A問題

書くだけですね。
TakahashiとかAokiのスペルミスしてないかちょっと心配でした。

以下コード

n = int(input)
taka, aoki = 0, 0
for i in range(n):
    x, y = MII()
    taka += x
    aoki += y
if taka > aoki:
    print("Takahashi")
elif taka < aoki:
    print("Aoki")
else:
    print("Draw")

B問題

横を見比べてアルファベットが逆順に並んでいる部分があるか判定しました。
本番中には気づきませんでしたが、わざわざこんな書き方しなくても、"BA" in s or "CA" in s or "CB" in s とかで良かったです。
解説にもありましたが、ソートされているか判定するのが一番綺麗な気がします。

以下コード

s = input()
tmp = s[0]
for i in s:
    if (
        (i == "A" and tmp == "B")
        or (i == "A" and tmp == "C")
        or (i == "B" and tmp == "C")
    ):
        print("No")
        exit()
    tmp = i

print("Yes")

C問題

ぱっとみ簡単なのに、少してこずりました。
自身をキーに、自身の後ろの人を要素に持つ辞書を用意して、それを辿って答えを作りました。

以下コード

n = int(input))
a = list(map(int,input().split()))
d = {}
for i, j in enumerate(a):
    if j == -1:
        s = i + 1
    else:
        d[j] = i + 1

ans = [s]
num = 1
while num != n:
    ans.append(d[ans[-1]])
    num += 1
print(*ans)

D問題

問題文をそのままやりました。
xは置き換えれないのでsplit("x")で分割してから累積和を取ってKの長さの区間を全探索、って発想がすぐ出たのは良かったです。

以下コード

h, w, k = map(int,input().split()
s = [list(input()) for _ in range(h)]

# 転置
def tenti(l):
    l = list(zip(*l))
    return l

s_r = tenti(s)
ans = inf

for i in s:
    tmp = "".join(i).split("x")
    for j in tmp:
        if len(j) < k:
            continue
        prf = [0]
        tmp = 0
        for l in j:
            if l == "o":
                tmp += 1
            prf.append(tmp)
        for l in range(len(prf) - k):
            tmp = prf[l + k] - prf[l]
            ans = min(ans, k - tmp)
for i in s_r:
    tmp = "".join(i).split("x")
    for j in tmp:
        if len(j) < k:
            continue
        prf = [0]
        tmp = 0
        for l in j:
            if l == "o":
                tmp += 1
            prf.append(tmp)
        for l in range(len(prf) - k):
            tmp = prf[l + k] - prf[l]
            ans = min(ans, k - tmp)

if ans == inf:
    print(-1)
else:
    print(ans)

E問題

logっぽいなーとは思うものの、実装方針が立たず。
愚直に考えて、一個は飲まないジュースが存在しても良さそう、3本のジュースを2人で飲めば、毒入りジュースは一意に定まりそう、みたいな考察をしていましたが、見当はずれでした。
解説ACはしましたが、まだ理解しきれていない気がします。
log2(ジュースの本数)の人数で判定できるのは、直観に反していて面白いなぁと思った問題でした。

ABC336参加記

結果

2ペナ4完でした。
温まったので良し。

各問題の感想・解法

A問題

書くだけですね。
以下コード

II = lambda: int(input())
n = II()
print("L" + "o" * n + "ng")

B問題

2進数に変換した文字列の並びを逆にしてから、前から見て0の数を数える。
bitをそのまま扱うってことが全然出来ないので、お勉強が必要ですね。
bit関連の演算子さえ怪しいので...
以下コード

II = lambda: int(input())
n = II()
bin_n = bin(n)[2:]
r = bin_n[::-1]
ans = 0
for i in r:
    if i == "0":
        ans += 1
    else:
        break
print(ans)

C問題

すぐに5進数で考えれば良いことに気づけた。
5進数変換のコードはAIに丸投げしてそのまま動いた。
最初Nをそのまま変換してしまっており、焦ったがすぐ修正できたので良し。
以下コード

def decimal_to_quinary(decimal_number):
    if decimal_number == 0:
        return "0"

    quinary_number = ""
    while decimal_number > 0:
        remainder = decimal_number % 5
        quinary_number = str(remainder) + quinary_number
        decimal_number //= 5

    return quinary_number


II = lambda: int(input())
n = II()
quinary_result = decimal_to_quinary(n - 1)
ans = ""
for i in quinary_result:
    ans += str(int(i) * 2)

print(ans)

D問題

難しかった。
最初は真ん中を頂点と決め打った判定を行ってWA。
次に階段を左右の端から順当に飛ばしたものと比較して、実際の階段の高さと比較して云々～みたいな謎の判定でWA。
Aを左右それぞれから見ながら、各地点における左右に延ばせる距離を保存する。その後、保存したものを重ね合わせて、最小値を取る。これが各地点を頂点としたときのピラミッドのサイズになる。頂点の位置は任意なので、その中の最大値が答えとなる。

頑張って考察して通せたので良かったです。考え方も概ね解説通りでしたし。
ふわっとした感触だけで通していたので、もっと自信もって判断できるようになりたいなぁ、というお気持。

以下コード

II = lambda: int(input())
LMII = lambda: list(map(int, input().split()))
n = II()
a = LMII()
l, r = a[:], a[::-1]
count = 0
kaidan_l = []
for i, x in enumerate(l):
    if count < x:
        count += 1
    else:
        count = x
    kaidan_l.append(count)

count = 0
kaidan_r = []
for i, x in enumerate(r):
    if count < x:
        count += 1
    else:
        count = x
    kaidan_r.append(count)

kaidan_r = kaidan_r[::-1]
kaidan_lr = []

for i, j in zip(kaidan_l, kaidan_r):
    kaidan_lr.append(min(i, j))

print(max(kaidan_lr))

E問題

何も分からない
解説によると桁DPらしい。名前は聞いたことある（）
水色行くには、DP関連が一つの壁っぽいので、鉄則本とEDPCで精進します。

ABC335参加記

結果

新年初のABC。ノーペナ4完でした。
温まったので良し。

各問題の感想・解法

A問題

誤読してました。
文字列の中で、最後に現れる2023を2024に変換かと勘違いしてました。
そのせいで少し時間食ったの勿体ない。
以下コード

s = input()
tmp = 0
for i in range(len(s)-3):
    if s[i:i+4] == '2023':
        tmp = i
        
print(s[:tmp]+"2024"+s[tmp+4:])

B問題

制約小さいので全探索をそのまま書きました。
以下コード

def II(): return int(input())
n = II()
for i in range(n+1):
    for j in range(n+1):
        for k in range(n+1):
            if i+j+k <= n:
                print(i,j,k)

C問題

頭に追従して体は動くことから、頭の動きのみシミュレーションすればよい。
また、各パーツと頭との距離の分だけ、遡った座標がパーツの座標と一致する。
普段の二次元平面探索時の上下左右の座標の差分と異なっていたため、その修正も必要で少してこずった。
以下コード

def MII(): return map(int, input().split())
n,q = MII()

a = []
for i in range(n,0,-1):
    a.append((i,0))
    
around4 = ((0,1), (0, -1), (-1, 0), (1, 0))
UDLR = {"U":0,"D":1,"L":2,"R":3}
x,y = 1,0
for i in range(q):
    u,v = input().split()
    if u == "1":
        v = UDLR[v]
        a.append((x+around4[v][0],y+around4[v][1]))
        x += around4[v][0]
        y += around4[v][1]
    if u  == "2":
        print(*a[int(v)*-1])

D問題

サンプルに実質答えがあり、それを頑張って実装する。
右->下->左->上の動きをN//2回繰り返せば良いので、指定した方向にぶつかるまで更新を続ける関数を作って、それを各方向に呼び出すことで実装した。
以下コード

around4 = ((-1, 0), (1, 0), (0, -1), (0, 1))  # 上下左右
def II(): return int(input())
n = II()

ans = [["T"]*n for _ in range(n)]

def guru(x,y,vec):
    num = ans[x][y]
    while is_not_Index_Er(x+around4[vec][0],y+around4[vec][1],n,n) and ans[x+around4[vec][0]][y+around4[vec][1]] == "T":
        ans[x+around4[vec][0]][y+around4[vec][1]] = num+1
        num += 1
        x,y = x+around4[vec][0],y+around4[vec][1]
    return x,y

ans[0][0] = 1 
x,y = 0,0
for i in range(n//2):
    x,y = guru(x,y,3)
    x,y = guru(x,y,1)
    x,y = guru(x,y,2)
    x,y = guru(x,y,0)

for i in ans:
    print(*i)

E問題

とりあえずDFSで実装->TLE->知ってた。
使ったことはなかったが、名前は知っていたのでダイクストラのコードをqiitaからコピペして修正してみる。色々と直しているうちにサンプルは通る->提出->TLE。
それ以外の解法は思いつかないので、高速化を試みる。
最初は無方向グラフとして入力されたものを全て隣接リストに保存していたが、広義増加していない場合は保存しないようにする。->少なからず高速化はできているはずだがTLE。
コンテスト時間はこれで終了。

解説を読むとDPのようだが、読んでも理解できないし、水上位パフォということで解説ACは諦め、どうにかダイクストラで通せないか考えてみる。
heapqから取り出したノードの持つ整数の種類数が、そのノードの持つ現時点でベストな整数の種類数未満の場合、探索を続ける意義がないので、その場合はその時点で探索を打ち切ることで、無事AC。
何とか通せたものの、ダイクストラをほぼ理解できていないまま適当に実装したものが何故か通った、というのが率直な感想なので、ダイクストラ法についても追々勉強しようと思います。
以下コード

def MII(): return map(int, input().split())
def LMII(): return list(map(int, input().split()))
n,m = MII()
a = LMII()
dd = defaultdict(list)
for i in range(m):
    u,v = MII()
    if a[v-1] >= a[u-1]:
        dd[u].append((v,a[v-1]))
    if a[u-1] >= a[v-1]:
        dd[v].append((u,a[u-1]))
    
import heapq
def dijkstra(edges, num_node):
    node = [0] * num_node    
    node[0] = 1     

    node_name = []
    #頂点の値、場所、種類数
    heapq.heappush(node_name, [a[0],1,1])

    while len(node_name) > 0:
        print(node_name)
        #ヒープから取り出し
        val, pos,num = heapq.heappop(node_name)

        if num < node[pos-1]:
            continue
        for factor in edges[pos]:
            goal = factor[0]   #次の頂点
            cost  = factor[1]   #頂点の値
            #更新条件
            if val < cost and node[goal-1] <= num  :
                node[goal-1] = num + 1     #更新
                #ヒープに登録
                heapq.heappush(node_name, [a[goal-1], goal,num+1])
            elif val == cost and node[goal-1] < num:
                node[goal-1] = num
                heapq.heappush(node_name, [a[goal-1], goal,num])
    return node

print(dijkstra(dd,n)[-1])

ABC334参加記

• 結果

ノーペナ5完＆自己最高パフォで年内での入緑を達成できました。

色変記事に関しては後日書く予定です。

苦手なDPが出なかったこと、比較的得意な貪欲的な考え方を要する問題が多かったのが勝因のような気もします。

考察に要した時間がB > C > E > D > Aとなっており、BC問題を解いている時は少なからず焦っていました。

• 各問題の解法、感想

  A問題

  これはそのまま条件分岐を実装するだけです。

  以下コード

  b,g = MII()

  
  

  if b > g:

      print("Bat")

  else:

      print("Glove")

  
  B問題
  中々に難しかったです。
  制約の数字が大きいので、whileでaを移動させながら見るのは無理そう、上手いこと計算して答えだす感じかなーと思いながら具体的な実装はすぐに思いつけず...
  結局、基準点をl,rの中に移動させて、基準点から左右に見たときのそれぞれのツリーの置ける数を調べることで対処しました。

  以下コード

  a,m,l,r = MII()

  
  

  temp = r - l

  if l <= a <= r:

      st = a

  elif a < l:

      st = a + m*math.ceil((l-a) // m)

  elif r < a:

      st = a - m*math.ceil((a-r) // m)

  
  

  ans = ((a-l)//m + (r-a)//m +1)

  print(ans)

  
  
  C問題

  証明しないまま提出したので、ジャッジ中はお祈りしていました。
  （通ってよかった）
  解法としては、まず全ての存在する靴下を昇順に並べたものを用意します。
  その中でペアを作っていくわけですが、存在する靴下の数が奇数の場合、少し面倒な処理が必要になります。
  偶数の場合、頭から二個のペアを作っていき、その差の絶対値の和が答えです。
  奇数の場合、靴下を0番目から数えたとき、偶数番目の靴下を使用しないことが、奇妙さを最低にするための条件となります。よって、全ての奇数番目の靴下を使用しないときの場合についての奇妙さを求めればよくなります。
  しかし、それをそのまま実装すると、計算量がO(N^2)となりTLEします。それを防ぐために、奇妙さについての累積和を偶数始まり、奇数始まりそれぞれで取ることでO(N)の落とすことができ、無事ACできました。
  以下コード
  

  n,k = MII()

  a = set(LMII())

  s = []

  for i in range(1,n+1):

      s.append(i)

      if i not in a:

          s.append(i)

  len_s = len(s)

  ans = 0

  if len(s) % 2 == 0:

      for i in range(0,len_s,2):

          ans += s[i+1] - s[i]

  
  

  else:

      g_r = [0]

      k_r = [0]

      temp = 0

      for i in range(0,len_s-1,2):

          temp += s[i+1] - s[i]

          g_r.append(temp)

      temp = 0

      for i in range(1,len_s,2):

          temp += s[i+1] - s[i]

          k_r.append(temp)

      ans = inf

      for i in range(len_s):

          if i % 2 == 0:

              ans = min(g_r[i // 2] + k_r[-1] - k_r[i // 2],ans)
  
  
  print(ans)

  D問題
  これは瞬殺できたので良かったです。
  必要なトナカイが少ない順にソリを並べ、その順でソリを引けばよいです。
  よって、ソートしたRの累積和を取り、後は二部探索で挿入位置を探せばそれが答えになります。
  以下コード

  n,Q = MII()

  r = LMII()

  q = [II() for _ in range(Q)]

  r.sort()

  
  

  temp = 0

  rui = []

  for i in r:

      temp += i

      rui.append(temp)

  
  

  for i in q:

      temp = bisect_right(rui,i)

      print(temp)

  E問題

  それぞれの赤マスが緑になった場合の緑の連結成分数を高速に求めることができれば、答えは求まります。
  赤マスを緑にすることで、増減する連結成分の数は、予め緑の連結成分をグループ分けしておくことで高速に求められます。よって、赤マスそれぞれの場合において、元の連結成分数とその増減を加味したものを求め、後は期待値のmodに変換すれば答えです。
  発想自体はすぐ浮かんだのですが、実装ミスやバグの改修に苦戦し、時間がかかってしまったのが心残りです。
  以下コード
  
  h,w = MII()

  s = [input() for _ in range(h)]

  
  

  visited = set()

  dd = defaultdict(set)

  def dfs(x,y,g):

      deq = deque([(x,y)])

      visited.add*1

      dd[(x,y)] = g

      while deq:

          x,y = deq.pop()

          for i,j in around4:

              if is_not_Index_Er(x+i,y+j,h,w):

                  if s[x+i][y+j] == "#" and (x+i,y+j) not in visited:

                      visited.add*2

                      dd[(x+i,y+j)] = g

                      deq.append*3

  temp = 0

  
  

  for i in range(h):

      for j in range(w):

  
  

          if s[i][j] =="#" and (i,j) not in visited:

              temp += 1

              dfs(i,j,temp)

  
  

  ans = 0

  ren = temp

  
  

  num = 0

  for i in range(h):

      for j in range(w):

          if s[i][j] ==".":

              num += 1

              l = set()

              for x,y in around4:

                  if is_not_Index_Er(x+i,y+j,h,w):

                      if s[x+i][y+j] == "#":

                          l.add(dd[(x+i,y+j)])

              if l:

                  ans += (ren - len(l) + 1)

              else:

                  ans += ren + 1

  
  

  denominator = pow(num, -1, mod)

  print(ans * denominator % mod)
  
  
  

*1:x,y

*2:x+i,y+j

*3:x+i,y+j