yatabis' Archives

後世のために書き記しておく

AHC012 振り返り記録

AHC012 AHC参加記 AHC AtCoder 参加記録 マラソン 山登り法 焼きなまし法

こんにちは、yatabis です。
今回 AHC012 に参加したので、やったことなどを書き残しておきます。

AHC012 は 4時間の短期コンテストでした。
4時間というのは Heuristic の問題を解くには短く、スピード感がとても大事になると思っています。
ABC などより時間が長くて大変なのですが、それでも時間いっぱい使わないと間に合わないことがほとんどです。
また、多くの人が時間いっぱい使っているため、長期のコンテストに比べて費やす時間に差が出にくく、より経験や実力がダイレクトに反映される気がします。

さて、結果ですが、90.0M のスコアで 105位で終了しました。
今回で Heuristic のレーティングが 1500 になりました。
（これは Algorithm のレーティングより上です！）

問題の概要

今回の問題はこちらです。

atcoder.jp

いくつかのイチゴが乗った円形のケーキを、何本かの直線で切り分けます。
特定の数のイチゴが乗ったケーキのピースが欲しい人に対して、なるべくの多くの人の希望を叶えられるよう、ケーキの切り分け方を最適化します。
希望通りのピースを受け取れた人の割合がスコアになります。

やったこと

本番中にやったことや考えていたことを時系列順に書いていきます。

最初の解答

ぼくはいつも、最初の解答はとにかく正の得点が取れるものを爆速で出す戦いをしているのですが、今回の問題では自明解が簡単には作れなそうな感じでした。
諦めてちゃんと考察をしようと思ったのですが、とりあえず縦に細く切っていく方法をまず思いついたのでそれを実装しました。
左端からカット線を徐々に右に動かしていき、その数が欲しい人がいるイチゴの数になった時点でカットします。
100回しかカットできないので、どうしようもなく左端の方で極細のピースが 100個だけできて終わるのですが、とりあえず最初の解なのでこれを提出します。
人は平均 500 人、最大 1000 人いるのでもちろん点数は低いです。 20M ぐらい。
これを提出した時点で開始から 23分ぐらい経っていました。

最初の解答のビジュアライズ

atcoder.jp

縦横に切る

縦にしか切らないとすると、明らかに 101個のピースしかできません。
なので、どうしても縦にも横にも切る必要があります。
もちろん斜めに切る方法もあるのですが、そうすると各ピースに含まれるイチゴの数を数えるのがとても大変になるので考えないことにします。
とりあえずランダムで縦横に合計 100回切ってみたらなんとなく良さそうなスコアが出たので、一旦提出してみました。
60M ぐらいになりました。ここまでで 41分です。
ちなみにスコア計算はまだ作っていません。

ランダムに縦横に切った図

atcoder.jp

ランダムサーチ

ランダム性をもたせたら、それを繰り返し生成してもっとも良かったものを提出することで、安定化できます。
ぼくはこれをランダムサーチと呼んでいますが、サーチというにはあまり頭は良くないですね。 せいぜい事故を防ぐ、ラッキーを狙うぐらいの効果しかありません。
それでもぼくがこれをやるのは、スコア計算があれば時間いっぱい回すだけで良いのでラクなのと、スコア計算を作ったらなんか一旦提出したくなるからです。
というわけでスコア計算を作ります。

今回の問題はスコア計算自体がものすごく難しい問題だったと思います。
結局、縦横にしか切らないことにして、各イチゴに対してどのピースに含まれるか、すなわちどの線とどの線の間にあるかを二分探索して求めました。
計算量としては、 O(N \log(K)) になりますかね。
制約から N \lt 10^{4}, K = 100 なので、まあ全然計算できるけど何回もやるのは厳しいといった感じですね。

なんとかスコア計算ができたので、提出します。
今まで Python で提出していましたが、こういう系は試行回数が大事なので PyPy で提出します。
それでも 1000 回ぐらいしか回っていませんでした。スコア計算がやはり重いので。
スコアは 68M ぐらいでした。あまり変わらないかと思ったけど、思ったより伸びましたね。
ここまでで 55分です。意外とすんなりスコア計算できました。

ランダムサーチの結果　seed=0 は苦手らしい

atcoder.jp

山登り法

ここまで来たら、次は山登り法を試します。
近傍への遷移は、とりあえずカット線を一本適当に動かす感じにしましょう。
細かいことは後で考えます。
その前に、スコアの差分計算をしないといけないですね。
さすがに試行回数 1000 回程度だと解の改善が全然間に合わない気がします。

今のスコア計算の方法だと差分更新にするのが難しいです。
近傍を考えると、線を 1本外して別のところに付け替えるので、その周辺のみ更新できれば... とか色々考えたのですが、結局差分計算は諦めました。
諦めた理由は、近傍を作った時点で、スコア計算なしでも 2000回ぐらいしか回らなかったからです。
近傍を作るのに 100 \times 100 ぐらいの配列を deepcopy しており、さすがにもっと上手くやれば速くなるんだとは思うのですが、心が折れてしまいました。

このままだと何ともならないので、封印を解いて Rust で書き直してみました。
そうすると差分計算なしで 10000回以上回ったので、 Rust でやることにしました。卍Rust 最強卍

普段は長期コンテストでは Rust で書くこともあるものの、短期コンテストで時間的な制約で Python で走り抜けることが多いのですが、今回は久しぶりに短期コンテストで Rust を使うことになりました。

山登り法、書きました。
近傍への遷移は、上述の通りカット線を 1本ランダムに選んでランダムに動かします。
移動先は左右の線の間からランダムに選びました。
結果は 83M。かなりいい感じですね。（やや白いラインが目立ちますが。）
休憩も挟みつつですがすでに3時間が経過しています。
残りあと 1時間で、ここから焼きなましていきます。

山登り法の結果　見た目ではもう良し悪しがわからん

atcoder.jp

焼きなまし法

最後に焼きなまし法を試していきます。
時間的にも、方針としてはこれが最後の方針となるでしょう。

山登り法から焼きなまし法への変換はある程度機械的にできて、温度の調節と遷移確率を決めるだけです。
基本的にはこちらの記事を参考にしました。

gasin.hatenadiary.jp

なんだかんだ焼きなましはあまりやったことがないので、結局ほぼ 1時間丸々温度調節（& バグ取り）に使い、最終提出をしました。
これで 90.0M 最終 105位の結果です。

最終提出のビジュアライズ　やはりseed=0は鬼門ケースなのでは？

atcoder.jp

さいごに

以上が今回の AHC012 で自分がやったことのすべてになります。

ランダムサーチから山登り法、焼きなまし法という流れでスムーズに進められたので、とても満足です。
結構今まで山登り法まで辿り着けなかったり、焼きなまし法ができなくてビームサーチや乱択DFS みたいな方向に行くことが多くて、何気に今回初めて満足に焼きなまし法が使えたかなという気がしています。

一つ心残りがあるとすれば、スコアの差分計算を諦めてしまったことです。
終わってからも少し頑張ってみたのですが、結局できずじまいです。

あとは、今回自分は縦横だけで切ったのですが、やはりほとんどの人が縦横だけで戦っている印象でしたね。
縦横だけでも十分に条件を満たす切り方があるというのは興味深いです。
最終スコア 99.7M とかの解答や、あるケースで満点が出る解答などもあってとても驚きました。 みなさんすごいですね。

個人的には、今回よく戦えたかなと思っています。
特に、短期マラソンには実は苦手意識があったのですが、今回は満足のいくスコアが出せてよかったです。
今夜は気持ちよく眠れそうです。

久しぶりに文章を書いたので、長々と駄文を垂れ流してしまいました。
今回はここまでにしておきたいと思います。
最後まで読んでいただきありがとうございました！

【AtCoder】 ABC178 参加記録

AtCoder 参加記録 ABC ABC178

はじめまして。yatabis です。 私事ですが、先日参加した ABC178 で初の全完を達成し、驚異の1 228位・パフォーマンス2092 という結果を叩き出して水色に突入しました。

これを記念して、ブログを開設しました。 今回は、ABC178 で出題された問題について振り返ります。
（全問題についてかなり丁寧に振り返ったので、そこそこの分量あります。）

前提

私は基本 AtCoder には Python で参加しています。 そのため、問題に対する考え方等が Python に寄っている部分があります。 また、付記するソースコードはすべて Python で記述します。

問題A - Not

0 か 1 の入力 x が与えられて、 x が 0 ならば 1を、x が 1 ならば 0 を出力するという問題です。

これは単純に 1 - x を出力すれば良いです。フラグの立て下ろしの時とかによくやりますね。

\mathrm{not}\, x や x \,\mathrm{xor}\, 1 などの方法もありますが、個人的には 1 - x が一番好みです。

結果は 39秒で AC でした。A問題を 1分以内に解けるのは悪くはないです。 ただ、問題自体がシンプルであることに加えてタイプ量も少なく最も早く解ける類の問題でしたが、そのわりに時間がかかってしまったなという感じはします。まあそこまでこだわるところでもないでしょう。

問題B - Product Max

a \le x \le b, c \le y \le d を満たす整数 x, y について、x \times y の最大値を答える問題です。

x \times y が最大になるためには、 x と y は取りうる値の範囲の境界値であるはずなので2、 (a \times c,\, a \times d,\, b \times c,\, b \times d) のうち最も大きいものを答えました。

a,\, b,\, c,\, d の符号によって場合分けすることも考えましたが、かなりめんどくさいことになりそうだという直感のもと、楽な実装を選びました。 今考えても、符号で場合分けする方法にメリットはあまりないように思います。

結果は 1分45秒で AC でした。この問題に 1分6秒かけたことになります。 複数思いついた解法の中から最善だと思われるものを迅速に選び、ミスなく解答できたので上々の結果だと言えるでしょう。 タイポとかの単純ミスでペナルティを出さなくてよかったです。本当に。

問題C - Ubiquity

0以上9以下の N 個の整数からなる数列のうち、0 と 9 がそれぞれ 1回以上現れる数列のパターン数を 10 ^ 9 + 7 で割った余りを答える問題です。

ほとんど公式の解説と同じことを書きますが、まず長さ N の数列のパターン数は 10 ^ N 個あります。
そして、0 が 1回も現れない数列のパターン数は 9 ^ N 個です。
9 が 1回も現れない数列のパターン数も同じく 9 ^ N 個です。
さらに、0 も 9 も 1回も現れない数列のパターン数は 8 ^ N 個です。
よって求めるパターン数は、すべてのパターン数から 0 が現れないパターン数と 9 が現れないパターン数を引き、この時点で 0 も 9 も現れないパターン数が重複して 2回引かれているので、これを足したものとなります。
すなわち 10 ^ N - 2 \times 9 ^ N + 8 ^ N です。

数学的にはこれで良いのですが、これをそのまま実装してしまうと TLE になります。 制約上 N は 10 ^ 6 まで大きくなり得るため、多倍長整数の計算となってしまうためです3。

とはいえ、Python での実装は少し工夫をするだけで大丈夫です。 計算の都度 10 ^ 9 + 7 で割る操作を入れるだけです。

特に N 乗の計算が重いですが、Python だと pow(base, exp, mod) が使えます。

Python での実装例 https://atcoder.jp/contests/abc178/submissions/16682422

n = int(input())
mod = 10**9 + 7
print((pow(10, n, mod) - 2 * pow(9, n, mod) + pow(8, n, mod)) % mod)

結果は 6分2秒で AC でした。この問題に 4分17秒かけたことになります。かなり早いんじゃないでしょうか。まあ数学を知っていればこれぐらいでできるのかもしれません。この問題に対しては特に感想はないです。Python は余りの計算も簡単にできて便利ですねというぐらいです。

問題D - Redistribution

3 以上の整数からなる数列のうち、その総和が S であるような数列のパターン数を 10 ^ 9 + 7 で割った余りを答える問題です。

公式の解説では DP による解法が挙げられていましたが、私は数学的に解きました。

まず、数列の項数 n の制限について考えると、n は \left\lfloor\frac{S}{3}\right\rfloor 以下であることがわかります。 n が \left\lfloor\frac{S}{3}\right\rfloor より大きければ、すべての項が 3 であってもその総和は S を超えてしまうからです。 よって数列の項数 n について 1 から \left\lfloor\frac{S}{3}\right\rfloor まで forループを回し、各 n についてのパターン数を計算して足し合わせていきます。

数列の項数が n のときの求める数列のパターン数は、単純な組み合わせ計算になります。 すべての項は 3 以上なので、残りの S - 3n をどこに振り分けるかを考えます。m = S - 3n とおきます。 この組み合わせ数は m 個のボールを n - 1 個の仕切りで分ける組み合わせと同じで、m + n - 1 個の ボール / 仕切り の候補から n - 1 枚の仕切りの位置を選ぶ組み合わせと同じです。
すなわち _ {m + n - 1} \mathrm{C} _ {n - 1} です。

数学的にはこれでOKで、次に実装について考えます。こちらも数が非常に大きくなるので 10 ^ 9 + 7 で割ったあまりを答えるのですが、そのまま計算すると時間がかかります。 具体的には、 _ {m + n - 1} \mathrm{C} _ {n - 1} を高速に計算したいです。 _ {m + n - 1} \mathrm{C} _ {n - 1} = \frac{(m + n - 1)!}{m!(n - 1)!} なので、階乗の計算を多数回行うことになり、これをまとめて先に計算しておくと良いです。 割り算もあるので逆元も同時に求めておきます。 これをしておくことで組み合わせ数が O(1) で計算でき、十分高速に解くことができます。

Python での実装例 https://atcoder.jp/contests/abc178/submissions/16703788

def main():
    s = int(input())
    if s < 3:
        print(0)
        return
    mod = 10**9 + 7
    f = [1] * (s + 1)
    for i in range(s):
        f[i + 1] = (f[i] * (i + 1)) % mod
    inv = [0] * (s + 1)
    for i in range(s + 1):
        inv[i] = pow(f[i], mod - 2, mod)
    c = 0
    for n in range(1, s // 3 + 1):
        m = s - 3 * n
        c = (c + (f[m + n - 1] * inv[m] % mod) * inv[n - 1] % mod) % mod
    print(c)

if __name__ == '__main__':
    main()

結果は 49分17秒で AC でした。この問題に 43分15秒かけたことになります。全問題の中で一番時間がかかりました。

私は以前 maspy さんの以下の記事を読んだことがあったので、形式的冪級数を用いた解法で考えていましたが、式変形で詰まっていました。

やはり付け焼き刃の知識を信用して時間を使いすぎるのは良くないなと思い、一から考え直すと上記の方法を思いつきました。助かりました。

ちなみに、形式的冪級数を用いたこの問題の解法は maspy さんが以下の記事で解説されています。読んでおきます。

問題E - Dist Max

二次元平面上にある N 個の点 (x_i,\, y_i) のうち異なる二点間のマンハッタン距離の最大値を求める問題です。

厳密な証明は公式の解説にある通り 45度回転と呼ばれる式変形を用いて行うようですが、コンテスト中は私はそこまでしませんでした。 代わりに以下のようなふわっとした考察を以て解答しました。

1 \le x_i,\, y_i \le 10 ^ 9 という制約より、N 個の点は正方形の領域の中に散らばっているというイメージを持ちます。 すると、その正方形の四隅に最も近い点を選べばいいような気がします。 すなわち、領域の右下に最も近い点と左上に最も近い点の距離か、右上に最も近い点と左下に最も近い点の距離の大きい方が答えであると思いました。
数学的な二次元の直交座標系にあてはめると、左下に最も近い点とは x_i + y_i が最も小さい点であるといえます。
同様に右上に最も近い点とは、左下から最も遠い点ということで、x_i + y_i が最も大きい点となります。
さらに右下に最も近い点は x_i が大きくて y_i が小さいということなので x_i - y_i が最大の点で、同様に左上に最も近い点は x_i - y_i が最小の点です。
最終的に求める答えは x_i + y_i の最大値と最小値の差と x_i - y_i の最大値と最小値の差の大きい方になります。

そうとわかれば、入力を読みながら x_i + y_i と x_i - y_i の最大最小を持っておき、最後にその差を計算して大きい方を出力すれば良いです。

Python での実装例 https://atcoder.jp/contests/abc178/submissions/16705230

def main():
    n = int(input())
    s = [0] * n
    d = [0] * n
    for i in range(n):
        x, y = map(int, input().split())
        s[i] = x + y
        d[i] = x - y
    print(max(max(s) - min(s), max(d) - min(d)))

if __name__ == '__main__':
    main()

結果は 53分35秒で AC でした。この問題に 4分18秒しかかかっていないということです。速い！B問題と同じぐらいの時間でできました。
まあもちろんちゃんと証明していないのでペナる可能性はあるなとは思っていましたが、直感を信じて出してよかったです。 証明しようと思うと 5分以上はかかっていたと思うので。
あと実装が凄まじく軽かったのも助かりました。考察のみで解ける問題を直感のみで解いた形ですかね。

問題F - Contrast

長さが N の数列 A,\, B に対して、すべての i について A_i \ne B_i になるように B を自由に並べ替える問題です。

※はじめに断っておきますが、私がこの問題をコンテスト中に解けたのはたまたま運が良かったからだと思います。 考察もかなりいい加減であり、嘘解法かもしれません。

まず、B をうまく並べ替えることで A_i \ne B_i を満たすことができるかを判定する必要があります。
ある値 x について、B に含まれる x の個数が A に含まれる x でないものの個数よりも多い場合、明らかに不可能です。
そうでない場合は必ず可能なのかはコンテスト中に判断できませんでしたが、どうやらそうらしいです4。

とにかく条件を満たすような B の並べ替え方が存在すると仮定して、その並べ替え方を探すことを考えたわけですが、A も B もソートされているということなので、B をいくつかシフトしたものの中に条件を満たす並べ替えがあるだろうと思いました。
というわけで、B を順番にシフトしつつ、すべての i について A_i \ne B_i となるまで繰り返しました。
ただし、1つずつシフトしていくと最悪のケースで間に合わなかったので、B に含まれる値のうち A に含まれる個数の最大分ずつずらしていくことにしました。（本当は A_i = B_i となっている値の最大個数分ずつシフトしているつもりだったが、そうはなっていないことにコンテスト中は気付いていなかった。テストケースは通ったが、場合によっては間に合わないケースもあるかもしれない。）

この解法は計算量が重く見えますが、numpy の力を借りれば間に合います。A_i = B_i の項があるかの判定は

any(a == b)

を使い、B のシフトは

b = np.role(b, shift)

としました。numpy 便利ですね。

Python での実装例 https://atcoder.jp/contests/abc178/submissions/16757729
上記の通りで、この解法だとケースによっては落ちるかも。

from collections import Counter
import numpy as np

def main():
    n = int(input())
    a = np.array([int(i) for i in input().split()])
    b = np.array([int(i) for i in input().split()])
    ca = Counter(a)
    cb = Counter(b)
    for k in cb.keys():
        if cb[k] > n - ca[k]:
            print("No")
            return
    shift = max(ca[k] for k in cb.keys())
    while any(a == b):
        b = np.roll(b, shift)
    print("Yes")
    print(*b)

if __name__ == '__main__':
    main()

結果は 73分34秒で AC でした。この問題に 19分59秒かけたことになります。早いですね。D問題より早いです。
もちろん証明をちゃんとせず直感で出したためです。立ち回りが上手い。

実はコンテスト中に意図的に 2ペナ出しています。Yes か No かの判定条件が必要十分になっているのか自信がなかったので、そこを確かめるためのコードを書いて提出しました。F問題だしそもそも解けない可能性もあったので、証明時間を省略するためにそのような手段を取りました。
このようなやり方が良しとされるものなのかは分かりませんが、まあプログラミングを使った競技ですしペナルティも受け、そのペナルティに見合ったリターンがあるなと感じたのでそうしました。

条件を満たす並べ替えは B をシフトさせるだけでよい、というところには正直自信はなかったのですが、コード中ですべての i に対して A_i \le B_i であることは確かめているので、答えが出れば AC だということはわかっていました。 その上で、いくつか適当なケースを作って試してみるとそこそこ速く結果が出ていたので、試しに提出してみると AC でした。興奮しました。

まとめ

全体的に運が良かったですねという感じですね。あるいは圧倒的に得意なセットだったか。 少なくとも精進の結果ではないような気がします。
そうだとしても、時間内に正しい結果を導き出せたというのは自分の中に根付いている AtCoder における感覚のようなものがうまく働いたということだと思うので、そこは素直に嬉しいです。

ただし今回の結果は決して実力に伴うものではなく、次回も同じようにいい成績を残せるわけではないということは理解しているので、慢心することなく次もベストを尽くせるように頑張りたいですね。

  1. 個人の感想です。↩

  2. ここについては公式の解説がとても親切です。↩

  3. Python の場合。↩

  4. 公式の解説に証明があります。Hall の結婚定理 などと呼ばれるようです。↩