AHC026(23/11/05)参加記録(545位)

はじめに

AHC026(23/11/05)に参加しました。
最終スコア1337524で545位 / AC739人でした。

へなちょこAHC初心者です。そもそもプログラミングも初心者です。
内容としてはかなり初心者向けかもしれません。
手練れの方々にとっては蛇足となるような基本的な説明、また抽象的で正確ではなさそうな説明が多々混ざっています。
指摘は優しめに、あなたの好きな人が放課後に自分のところに質問しに来てくれたときに答えるくらい優しめにお願いします。

書いた人略歴

大学4年。文系。使用言語はpython。
ABCは茶色、AHCは実質初参加。

問題のおさらい

https://atcoder.jp/contests/ahc026/tasks/ahc026_a

1からn(=200)までの番号がつけられた箱が、m(=10)個の山に分けられている。
高橋社長はこれから、箱についている番号が小さい順に箱を運び出したい。
可能な操作は次の2つ:
○操作1:箱を移動
ある箱を1つ選んで、その箱とその上に載っている箱をまるごと、どこかの山に移動させる。持てる箱の数に制限はない。
山の数を11個以上にすることはできない。つまり、新たに11個目の山を作ることはできないが、最初に山だった跡地には置くことができる。
○操作2:段ボールを搬出
残っている箱の中で一番小さい番号を持つものが山の一番上にあるなら、それを運び出すことができる。

高橋社長は、操作1と操作2を合わせて5000回しか行えない。
高橋社長には10000の体力がある。
操作1を行うたびに、「持ち上げた箱の個数+1」の体力を失っていく。
操作2を行っても体力は減らない。
このとき、体力ができるだけ残るようにするにはどうしたらいいか。

より厳密な情報は問題ページをご参照ください。


ざっくりの方針

・これはほぼソリティアかハノイの塔じゃね?
特殊ルールとして、困ったら小さいのの上に大きいの置いてもいいよ。

・操作2が行える時は操作2を行うのがよさそう。
・操作1を行う場合、一度に動かす箱の数はできるだけ多いほうがよさそう。
というのも、たとえば同じ山に積まれている5個の箱を1個ずつ動かすのと、5個まとめて動かすのでは、体力消費量は(1+1)*5=10と(5+1)=6で結構違う気がする。
・山の状態として、「上にあるほど番号が小さくなっている」のが望ましそう。ソリティアだとしたらそっちのほうがいいよねえ。
・「いっぺんにたくさん動かすこと」と「番号が大きい箱の上に番号が小さい箱が来ること」はトレードオフに見えるので、ここのバランスが焦点になりそう。

・この方針はAHCっぽくなくないか…?

提出コード

https://atcoder.jp/contests/ahc026/submissions/47306621

import bisect


n,m = map(int, input().split())
b = [list(map(int, input().split())) for i in range(m)]

top = sorted([b[i][-1] for i in range(m)])

def outputmove1(a,i):
    print(a,i)
def outputmove2(a):
    print(a,0)

turn = 0
target = 1
while (turn == 5000) or max(top) != 0:
    turn += 1

    if target in top:
        outputmove2(target)
        for i in range(m):
            if b[i] and b[i][-1] == target:
                b[i].pop(-1)
                top.remove(target)
                top.append(b[i][-1] if b[i] else 0)
                target += 1
                break
        continue

    for i in range(m):
        if target in b[i]:
            movefrom = i
            break
    
    q = len(b[movefrom])-1
    t = b[movefrom][q]
    while 1 <= q and b[movefrom][q-1] > t:
        q -= 1
        t = b[movefrom][q]

    z = b[movefrom][q:]
    w = z[0]

    e = bisect.bisect(top,w)

    if 0 in top:
        for i in range(m):
            if len(b[i]) == 0:
                top.remove(0)
                moveto = i
                break
    elif e == m:
        u,v = 0,n+20
        for i in range(m):
            if i == movefrom:
              continue
            if v > len(b[i]):
                moveto = i
                v = len(b[i])
        top.remove(b[moveto][-1])
    else:
        for i in range(m):
            if b[i][-1] == top[e]:
                top.remove(b[i][-1])
                moveto = i
                break

    b[moveto] += z
    b[movefrom] = b[movefrom][:q]
    outputmove1(t,moveto+1)
    
    top.append(b[movefrom][-1] if b[movefrom] else 0)
    top.sort()

汚いコードで恐縮ですが・・・ひとつずつご説明します。

太字は中心となる方針を示している部分です。
忙しい方はここだけ読んでいただければわかりそう。

1行目

import bisect

このあと使うモジュールをインポートしています。
モジュールというのは、便利な道具をジャンルごとに詰め込んだパッケージみたいなものです。

bisectモジュールは、二分探索をうまいことやってくれるモジュール。
二分探索というのは、順番通りに並んでいる配列(=リスト)の中で、この子は何番目くらいに入れますかね?というのを素早く教えてくれるものです。
二分探索の技術はABCでは頻出で、配列がとんでもなく長い場合、配列の最初から最後まで毎回追っかけて確認していると凄まじい時間がかかってしまうので、その回避に使えます。

今回は対象にする配列の長さが全然大きくないので別に使わなくてもよかった気はしますが、なんとなくあると便利なので入れておきました。

4-5行目

n,m = map(int, input().split())
b = [list(map(int, input().split())) for i in range(m)]

入力を受け取っています。
5行目、「b=・・・」で受け取っているのは、二次元配列です。
二次元配列はリストの中にまたリストが入ってるイメージ。たんすの中を、靴下用と下着用と…と分けていくような。
リストの中でfor文を回す、いわゆるリスト内法表記で書くと1行で書けてうれしいです。

7行目

top = sorted([b[i][-1] for i in range(m)])

ここからが本題です。
まずは、それぞれの山の一番上にある箱の番号を確認して、持っておきます。
b[i][-1]は、bのi番目の山の-1番目ということ。
配列に対して「-1番目」を指定すると、後ろから1番目を指すことになります。-2番目は後ろから2番目になります。

また、この時点でいったんソートしています。
のちのち、先に紹介した二分探索を利用するところがあるので、その準備のためです。
その番号の箱がどの山にあるものなのかが分からなくなりますが、箱の番号がそれぞれ異なるおかげでまあどうにでもできる。

このリストは、あとで更新されていく予定です。またそのときに。

9-12行目

def outputmove1(a,i):
    print(a,i)
def outputmove2(a):
    print(a,0)

ふと思い出したので、出力用の関数を定義しておきます。
関数の中身がprint関数だけで大したことないので関数定義するほどでもないんですが、バグ取りの段階においてコード中にいろいろprint関数を紛れ込ませることになりそうなので、それと区別つかなくならないように先に分けておきました。
それぞれ、操作1、操作2を表しています。

14-17行目

turn = 0
target = 1
while (turn == 5000) or max(top) != 0:
    turn += 1

変数turnはターン数を、targetは今取り出したい箱の番号を表します。
また、whileの中でターン数を1つずつ増やしていくことでカウントしていきます。

while文で長いループを回していきます。
終了の条件は、ターン数が5000回に達するか、それぞれの山の一番上が全部0になる(=どの山もからっぽになる)こと。
からっぽになった山の一番上を0とするコードは後ろに書いています。

変数turnについて、正直なところループを5000回も回すことはないし、そもそも5000回やってまだ完了してなかったらWAを返されるので、実効的な意味は本当に何もありません。
ただ、while文は終了条件が達成されないと無限ループするわけで、バグがある間は終了条件が達成されないことはかなりよくあると思います。
バグを取りきるまで実行の打ち切りをシステム側に任せて待ちぼうけになるのはストレスなので、こちらで適当に打ち切るために置きました。
適当なところで打ち切る方法として、時間を測れるモジュールを導入する方法もあります。というかそっちのほうがAHCでは一般的な気がしますが…

19-28行目

    if target in top:
        outputmove2(target)
        for i in range(m):
            if b[i] and b[i][-1] == target:
                b[i].pop(-1)
                top.remove(target)
                top.append(b[i][-1] if b[i] else 0)
                target += 1
                break
        continue

while文の本格的な中身に入っていきます。

もし、今取り出したい箱が山の一番上にあるのなら、操作2を実行して、それをさっさと搬出することにしてしまいます。

その後、実際に二次元配列bをいじっていきます。
22行目(ここでは3行目)のfor文で、どの山の一番上に目的の箱があるのか見つけます。
そして、その山の一番上を取り除きます。
さらに、リストtopも更新していきます。まずは搬出した箱をremoveで消去。そして、新たに一番上になった箱をtopに入れます。このとき、搬出した箱がその山のラスト1個だった場合には、後に何も残らない更地になるので、一番上の箱の代わりとして0を入れておくことにします。
最後に、取り出したい箱の番号を1つ増やしてから今回のループは終了します。breakで22行目(ここでは3行目)のforから抜け出し、continueでwhileループ自体からも抜け出します。

30-33行目

for i in range(m):
    if target in b[i]:
        movefrom = i
        break

先ほど、操作2を行いたい場合の処理を終えたので、そうでないなら操作1を行っていきます。そのためには、「どの箱を持ち上げるか」と「どの山に動かすか」が必要です。
準備として、取り出したい箱がどの山に埋まっているのかを確認しておきます。
それぞれの山を見ていき、その山に取り出したい箱があったら、変数movefromにその山の番号を記録します。
山の番号は0-indexed、すなわち1番目の山は0番、2番目の山は1番…と0から始まる添字で管理していることに注意してください。

35-39行目

q = len(b[movefrom])-1
t = b[movefrom][q]
while 1 <= q and b[movefrom][q-1] > t:
    q -= 1
    t = b[movefrom][q]

ここから、今回のループでいくつの箱をまとめて動かすかを決定していきます。
まとめて動かす際の方針として、上のほうから小さい順に順番通り並んでいる箇所はまとめて持ち上げてるのがよさそう、と考えています。
つまり、ある山が上から順に「(下)1,13,23,11,7,5,3,2(上)」と並んでいるときに、「23,11,7,5,3,2」の部分をまるごと持ち上げたい、ということです。

移動先についてはまた後ほど。

さて、変数qに、取り出したい箱が埋まっている山の高さを持っておきます。
これも0-indexedで管理するために、-1しておきます。
たとえば高さ5の山の添字は、下から順に[0,1,2,3,4]ということになりますので。
また、変数tに、取り出したい箱が埋まっている山の一番上にある箱の番号を持っておきます。

そして、37行目(ここでは3行目)からのwhileループを回し、山が上方から昇順に並んでいる限りqとtを更新します。
movefrom番目の山の、下からq段目の箱よりも、一つ下にあるq-1段目の箱のほうが番号が大きいなら、q = q-1に、t = q-1段目の箱の番号に更新します。

whileループを抜けたときには、qはまとめて持ち上げたい分の一番下にある箱が下から何段目なのかを、tはその箱の番号を表していることになります。

41-42行目

z = b[movefrom][q:]
w = z[0]

やっとコードの半分すぎあたりですが、内容的にはまだ3分の1くらいかも。がんばっていきましょう。僕もがんばって書いています。

さて、すぐ上のコードで割り出した変数qを利用していくつか準備をしておきます。

リストzとして、持ち上げる分の箱の情報を持っておきます。先の例で言えば、「23,11,7,5,3,2」の情報です。
また、変数wとして、zの0番目、つまり持ち上げる分の一番下の箱の番号を持っています。

ん…?

書いている最中に気づきましたが、先に作った変数tとこの変数w、全く同じものじゃないか。何やってるんだ。
同じ値を示す変数を複数作ってても別にバグるわけではないのでどうでもいいと言えばどうでもいいけど、なんか草。

44行目

e = bisect.bisect(top,w)

先の処理で、どれだけまとめて持ち上げるかは決定しました。
それでは、持ち上げた分をどこに動かしていくかを考えていく必要があります。
ここでは、「まとめて持ち上げる分の一番下の箱の番号より大きくて一番近い番号の箱が山の一番上にあるような山」に動かすことを考えました。
そうするのが、上方に若い番号の箱が置かれるような、ハノイの塔的な並びを作るのに手っ取り早いと思ったからです。

44行目、変数eとして、「まとめて持ち上げる分の一番下の箱の番号より大きくて一番近い番号」がどれなのかを確認しています。
ここでbisectモジュール。二分探索は便利です。for文を回してもよいですが、楽にコード書けるならそっちの方が嬉しい気がするので。
たとえば、top = [1,3,5,7,9,11,13,15,17,19]で、wが10だった場合、wがどこに入ればいいですか~と聞くと、9と11の間(=0-indexedで5番目)だよ~んと答えてくれる、というものです。
こうして出てきたeのおかげで、移動先の山の一番上にある箱の番号がわかりましたので、すなわちどこに動かせばよいかが分かりました。

46-66行目

if 0 in top:
    for i in range(m):
        if len(b[i]) == 0:
            top.remove(0)
            moveto = i
            break
elif e == m:
    u,v = 0,n+20
    for i in range(m):
        if i == movefrom:
          continue
        if v > len(b[i]):
            moveto = i
            v = len(b[i])
    top.remove(b[moveto][-1])
else:
    for i in range(m):
        if b[i][-1] == top[e]:
            top.remove(b[i][-1])
            moveto = i
            break

長いですが、ひとかたまりのif文なのでまとめてご説明さしあげます。
どのif文も、変数movetoとして「どの山を移動先にするか」を決めることを目的にしています。

if 0 in top:
    for i in range(m):
        if len(b[i]) == 0:
            top.remove(0)
            moveto = i
            break

まず1つ目のif。
さっきeを求めたけど、どっかからっぽの山があるならそっちに動かせばええやん!ということです。
先に申し上げたとおり、リストtopに0が入っている場合には、どこかにからっぽの山があるということです。
その場合には、その跡地に移動させようということです。

ん?と思った方もおられるかと思いますが、私もそう思います。
これは疑問手
別にどこか空きがあろうが、順番通りになるなら普通に乗せればええやん。
当時の私は、のちに挙げる条件と混同していた可能性があります。かなしい。

elif e == m:
    u,v = 0,n+20
    for i in range(m):
        if i == movefrom:
          continue
        if v > len(b[i]):
            moveto = i
            v = len(b[i])
    top.remove(b[moveto][-1])

気を取り直して、elif文です。
このケースは、もしe==mなら、すなわち「持ち上げた分の一番下にある箱の番号」が「どの山の一番上にある箱の番号よりも大きかった」場合の話です。

この場合、方針通りの置き方はできないことになります。困っちゃった。
とはいえ、持ち上げた分はどこかに移さないといけません。
ということでとりあえず、現時点で山の高さがいちばん低いような山に移動することにしました。
もっと好ましい選びかたが数多あるはずですが、少なくともすでに大量に積みあがってる山に移すよりはよかろう。
(もっと好ましい選びかた・・・たとえば、それぞれの山で番号が最少の箱の番号を比べてみて最大の山を選ぶとか、山ごとにその山にある箱の番号の合計なり何かの評価値なりで評価して選ぶとか…先ほどの疑問手もこちらの一環として入れておけばよかった気がします。
問題はこれを適切に実装できる腕があるかどうかが微妙ということで、ここがヒューリスティックコンテストにおいて一番大事なところなんだと思います)

変数movetoとvをおきます。55行目(ここでは2行目)にu,vとありますが、uはmovetoの間違いです。変数名をいろいろいじっていたら変え忘れていたやつです。バグらないと気づいてあげられないの。

movetoとvはそれぞれ、その時点で調べ終わっている中で一番低い山が何番目かと、その山の高さを持っています。
そして、for文でそれぞれの山を調べます。
i==movefrom、つまり持ち上げた箱がもともとあった山はスキップ。ただ持ち上げて戻すだけになるので。
それ以外の山についてはひと通り調べてみて、もしvが更新される場合には合わせてmovetoも更新していきます。
こうして、movetoが山の高さが一番低い山の番号、すなわち移動先として指定したい山の番号を持つ変数になりました。

ここで、移動先の山の一番上にある箱は、これからその上に別の箱が乗ることになり、一番上の箱ではなくなってしまいます。
ということで、リストtopから、移動先の山の一番上の箱の番号を消去しておきます。

else:
    for i in range(m):
        if b[i][-1] == top[e]:
            top.remove(b[i][-1])
            moveto = i
            break

else文です。
ここまでの条件に当てはまらなかったということは、特に問題なく移動させることができるということなので、先に求めたeを用いて、movetoを求めつつ、先ほどと同じ要領で、移動先として選ばれた山の一番上にある箱をリストtopから消去します。

68-73行目

b[moveto] += z
b[movefrom] = b[movefrom][:q]
outputmove1(t,moveto+1)

top.append(b[movefrom][-1] if b[movefrom] else 0)
top.sort()

ようやくループの終わりです。お疲れさまでした。
必要な情報は出揃ったので、ここからはまとめのフェーズになります。

まずは、移動先となった山の上にリストz(=まとめて持ち上げた箱たち)を結合します。

そして、移動元だった山からは、移動した分を取り除きます。
for文でremoveを回すような方法などで実際に取り除いていくのは時間がかかりがちな気がするなので、スライス([:q]みたいなやつ、範囲指定)でやってみてます。

そして、最初に作っておいた結果を出力する関数で出力。
movetoは0-indexedで計算していたものでした。問題では山の番号は1-indexedとなっているので出力の際には+1しておくことを忘れずに(1敗)。

最後に、箱の移動により晴れて新たに山の一番上になった箱の番号をリストtopに入れます。
移動元だった山がからっぽなら0を、そうでなければ移動元の山で新たに一番上になった箱の番号を入れます。
ここわざわざ条件分けしていますが、今思うと操作1で移動した後の山がからっぽになることはありえない(必ず今取り出したい番号の箱を含めた1つ以上の箱が残る)ので、別に必要ありませんでした。無駄。

それはそうと、「a if (条件式) else b」という書き方は、結構便利です。
処理としては「条件がTrueならa、そうでなかったらbにしてください」というシンプルなものですが、普通にif文を使うと数行にわたるコードになってしまうものを1行で書けるのは魅力かと。
ABCでも「あてはまるなら”Yes”を、あてはまらないなら”No”を出力せよ」という問題がしばしばありますが、あれも「print("Yes" if (条件式) else "No")」と1行で書けるのです。初めて知ったときには目からうろこでした。スマートなものにはやはり憧憬の念を禁じ得ないものです。

閑話休題。
リストtopはループの間にいろいろ操作されて昇順になっておらず、このままだと道中の二分探索で困るので、この時点でソートをかけておきます。

これでループ終わり!
晴れてACに漕ぎつけました(この時点で開始から3時間経過)。

高橋社長の体力を残す方法について考えていたら、自分の体力も集中力も失われていたためここで断念。
苦し紛れの最後っ屁として、山の高さの計測の際に、同じ高さだった場合に山の番号が小さい方を採用するか大きい方を採用するかを変更しましたが、点数が下がりました。草。

ちなみに、ビジュアライザを乗っけようかと画策したのですが、上手くいきませんでした。残念。
いろいろ説明は書きましたので、想像してみてください。

高得点のためにできそうなこと

コードの説明の中でもいくつか触れましたが、あらためてまとめてみます。先の説明で、『「どの箱を持ち上げるか」と「どの山に動かすか」が必要です。』と書きましたが、やはりこの2点でそれぞれに考える必要がありそうです。

・持ち上げる箱の選びかた
正直なところこれについては、更新の余地があるとはあまり思えません。現時点でもかなり最適解には近そう。少なくとも、後述する検討ポイントに比べれば些末な問題であるように思います。
もちろん、更新の余地がないわけではありません。
たとえば、説明のためだけに適当ではない例を挙げることになりますが、
今のやり方だと、山としていずれも上から1:[5,7,1,…]、2:[6,10,…]、3:[8,9,…]という2つがあったとき、山1から[5,7]を持ち上げて山3に乗せることになります。ただなんとなく、いったん[5]を山2の6の上に乗せてから、[5,6]を山1の7の上に乗せて、[5,6,7]を山3の8の上に乗せる…というやり方のほうが効率が良くなる場面もあるような気がします。この例は適当ではないので元のやり方のほうがよさそうですが、もっと大きなケースでも正しいとは僕は言い切れません。

・山の跡地や低い山の扱い方
「どの山に動かすのか」という問題。これが一番大きいように思います。
中盤あたりから、ときたまではありますが何も置かれていない場所が現れます。また、何も置かれてないわけではないけど、極端に高さが小さいような場所は頻繁に現れます。
今回のコードではそれを適当に埋めていたのですが、もう少し大切に扱ってあげればよかったのかもしれません。
言うなればこれは「番号がとてつもなく大きい箱を簡単に下のほうに送れる」チャンスであり、これをフイにすることの損失は結構あったような気がします。

・持ち上げた箱をどこに持っていくのかの評価のしかた
一番ヒューリスティックっぽいところな気がします。
思いつく可能性としては、「取り出したい箱がある山として次に選ばれるのが遅い山にする(あるいは次の次あたりやそれ以降まで見るか)」とか「その山にある箱の番号の和が一番少ない山にする(和じゃなくて積もありそう)」とか「その山にある箱の番号の平均が一番少ない山にする(積を箱の数で除した数もある?)」とかでしょうか…
シミュレーションしてみるといってもどうやってシミュレーションすんねんという気持ちもあります。どうしても、「実装にとんでもねえ時間かかりそうだなあ」という気持ちが先に来てしまいます。

もっと根本的な問題

・そもそもこの方針が正しかったのか、方針に見合った実装だったのか
ハノイの塔システム(今この瞬間に命名しました)を採用した今回ですが、結局のところ小さいハノイの塔を量産しているだけであんまり意味なかったのでは?という気もします。
問題は要するに、上にあるのに番号が大きい箱をいかに効率的に処理するか、という問題だったんだよな…と
ハノイの塔方針らしくするのであれば、小さいハノイの塔を大きなハノイの塔にしていくという努力も必要な気がしています。
いっそ、それぞれの山をひたすらソートしつづけて最後の200回で全て搬出するというパワープレイもありうるのか…?

・AHCの心構えが分かってなかった
なんども提出して精度を上げていくという感覚があまりよく分かってない中でやってたので、精度を上げるためにどこに目を付けたらいいのかという点でとても困った感覚があります。
ABCでは提出してAC出せたらとりあえずその問題はコンテスト中は終わりなので、そことの違いがあるんだなあという気付きがあります。
スタートダッシュが遅かったとはいえ、最初の提出まで3時間くらいかかっているので、そもそもそれ以前の問題という気もしますが…

・ガバが多い
何かとガバガバ。同じことを表す変数が大量にあるなど、後から見返すと無駄が多い印象がありました。
そもそも今まで、提出したACコードを後から見返すことがほとんどなかったので、こんなにガバがあるのか…とこれを書きながら衝撃を受けていました。
こうして人は成長していくのかもしれません。成長痛を忘れない。

・デバッグに時間かかりすぎ
やはりコードを書くうえでバグはつきもので、一発で思った通りの結果が得られることはほぼありません。「コードは思った通りには動かない。書いた通りに動くのだ。」という至言が身に沁みるところです。
そんなわけでバグを解決していかないといけないのですが、これがまた苦難の道のり。
コードテストにコードを投げ、実行してみて、エラー出力を見ながらどこがまずいのか探す。ぱっと見じゃわからないので適宜怪しそうなところをprintして確認。どこでループが変わるのか見えなくなってくるのでまたprintを追加。一つ解決して回したら他のところで不合理が出てまたエラー。
―――なにかよいデバッグの方法を考えないといけないのだと思います。
というか、知ってはいるけど、面倒で手がつけられてないだけではある。

・他の人のコードが読めない
正確に言うと別に読めないわけではないけど、何をしたいかがよく分からない。解説がついてないと何をやってるのか分かりません。みなさんもこういうの書いてください。
あとC++の方がやっぱり多い。実装速度速いらしいしな~
ますます読み取れなくなるのでもっと解説お願いします。

延長戦やってみた

この記事を書きながら思いついたいくつかの改善案のうち、簡単に実装できそうなものを書いて提出してみました。

プラン1:持ち上げた箱の移動先を、すぐにtargetになりそうな箱がある山以外の山のうち、箱の番号の平均値が最大の山にする。
スコアは1343211(時間内最終提出+5687、525位相当)


プラン2:持ち上げた箱の移動先を、その山にある箱の番号の最小値が最大の山にする。
スコアは1372210(時間内最終提出+34686、300位相当)


おわりに

駄文乱文ここまで読んでいただきましてありがとうございました。
結局どの層に向けたものなのかよくわからなくなってしまいましたが、
どなたかの参考になっていれば幸いです。

そして、執筆の勇気をくれた
競技プログラミングをするフレンズさん、ありがとうございました。


この記事が気に入ったらサポートをしてみませんか?