htkb-proconの日記

初心者がPythonで問題解いた記録

AISing Programming Contest 2019

ooo-- 1607 -> 1604

反省しきり。

A - Bulletin Board

AC: Submission #3983509 - AISing Programming Contest 2019 / エイシング プログラミング コンテスト 2019

縦と横それぞれいくらずらせるかを掛ければいい。

B - Contests

AC: Submission #3984497 - AISing Programming Contest 2019 / エイシング プログラミング コンテスト 2019

そのまま3回走査しただけ。

C - Alternating Path

AC: Submission #3988567 - AISing Programming Contest 2019 / エイシング プログラミング コンテスト 2019

誤読で何度も実装方針を変えるハメになった。求めるべきは黒のマスから始まって白のマスで終わる経路だけなので、黒・白・黒……とたどっていける連結成分の中の黒と白の数を数えるだけの話だった。問題文を流し読みして、交互に色違いをたどって行ける任意の頂点の組み合わせ数を求めるのかと思い、上に戻ったり左に戻ったりするのを数えるためにどっちから来たのかも持つdp[y][x][4]みたいなdp組むのかな……みたいなことを考えていた。アホすぎる。

実装は同じ連結成分に同じ数字を振っていって、その代わり白のマスだったら符号をマイナスにする。で数字を振った二次元配列をchain.from_iterable()でflattenしてcollections.Counterに食わせて数を数えさせ、各iについてcounter[i] * counter[-i]を足していった。

D - Nearest Card Game

高橋くんが右から取る数について二分探索するところまではたどり着いていたので、Cで時間を溶かさなければ……と悔やんだが、実際にACするまでかなりバグらせて時間がかかったのでどっちみち多分無理。

ちょっと手でシミュレートしてみるとすぐ気付くが、高橋くんが1で青木くんが0とすると、カードの取り方は

01010100000001111111

のような感じになる。01交互のゾーンと0000011111のゾーンが、xによってはどちらか片方のみ、あるいは両方現れる。青木くんがx周辺をウロウロしている間に高橋くんが右を全て取り終えるまでが0000011111のゾーンで、高橋くんが青木くんを飛び越えた以降は010101になる。

右のゾーンの範囲が定まれば01交互ゾーンも定まるので、右のゾーンについて二分探索を考える。最初は高橋くんが取る長さについて二分探索を考えていて、高橋くんの一番左のカードの左隣(つまり青木くんの取る一番右のカード)とxの距離を数えて、二分探索で同じだけ左に行ったときのインデックス番号を取ろうとしたんだけど、この距離は負になりうるしうまくいかない。

で考え直してみると、0000011111ゾーン全体の長さ全体についての二分探索を考えれば、青木くんの右端のカードと左端のカードも定まる(高橋くんが先手なので青木くんゾーンは全体の長さの半分切り捨て)。で、|左端のカード-x| <= |右端のカード-x|の場合は青木くんゾーンがもっと左にある、もしくは正しい位置と考えられ、|左端のカード-x| > |右端のカード-x|ならば青木くんゾーンはもっと右にあると考えられる。

f:id:htkb:20190113053828j:plain

上の図でいうとmid=4のときも7のときも青木くんゾーンの位置は正しくないんだけど、|左-x| <= |右-x|を満たす範囲で最大のmid(=6)のときが答えになるのでこれをOK、そうでなければNGとし、二分探索でこれを求めた。

AC: Submission #3994020 - AISing Programming Contest 2019 / エイシング プログラミング コンテスト 2019

予想に反しこれでも時間ギリギリで、二分探索 in 二分探索解はpypyでも通らなさそう。

Educational DP Contest S - Digit Sum 桁DP

めんどくさすぎるイメージを持っていた桁DP、久しぶりに遭遇して解いたら割とソラで書けたのはいいけどTLEで、考察したらそもそも無駄に配列の次元を深くしたりしなくていいんじゃないの??と思ったので書き残してみる。

f:id:htkb:20190109210051j:plain

桁DPの状態遷移はこのように上の桁から見ていって、次の桁に取る数を考えながら1桁ずつ数字の総数をDPでまとめて数えていく。でこのときに面倒なのが境界ギリギリの数字のことで、上の例で言えば10の位が0〜2のときは1の位に0〜9を取れる(ただし問題では1以上N以下の数なので00は後で除外)んでまとめてループしちゃえばいいのだけど、10の位が3のときは1の位は0〜2までしか取れない。だからこの境界ギリギリの部分を別口に処理しなければならないわけ。

これのやり方を、巷では一般的に

dp[桁][境界ギリギリかどうか][数えたい数の種類(今回の問題ではmod D)]

みたいに取るように書いてあることが多く、次の桁が2だとすると

dp[0][境界ギリギリ][x] → dp[1][境界ギリギリじゃない][x]
dp[0][境界ギリギリ][x] → dp[1][境界ギリギリじゃない][x+1]
dp[0][境界ギリギリ][x] → dp[1][境界ギリギリ][x+2]

みたいに遷移させるようだ。自分もそのように覚えていたけど、dpの次元が増えすぎて混乱するし速度的にもメモリ的にもキツイ。何より境界の数ってのは桁ごとに1種類しかないのだから、dp[d][境界ギリギリ]は常に一つの要素だけ1で他全部0なわけで、これわざわざdpを一段深くする必要あるの??と境界の数を変数にそのまま持たせてみたら普通にうまく行った。

コメント付けたので詳しくはソースのほうを
Submission #3967551 - Educational DP Contest / DP まとめコンテスト

borderが境界ギリギリの数のそれまでの桁和 mod Dを持ってるので、+0〜(次の桁-1)まではdpのほうに合流させてborder += 次の桁して遷移させていく。めちゃくちゃ見通しが良くなって自分のように脳のメモリ控えめの人にも優しい。

わざわざdpの次元一つ掘って保持するのが桁DPの定番の持ち方になってるのは多分難しい問題ではそれが必要だからだと思うので、定番の方も覚えておくべきと思うけど、易しめの桁DP問題はこっちのが実装が軽いだけじゃなく何やってるか明確なので混乱しにくいと思う。

同じように解けた桁DP問題

AtCoder青になるまで使ったPythonパフォーマンス小ネタ

f:id:htkb:20190107210932j:plain

AtCoder青になったらなんか書こうと思っていて、12/22に無事青になれたのですが、よく考えたらあんま書くことないな……と思ってる間に年が開けてしまいました。知識披露でもサクセスストーリー的な話でも既に109+7人くらいいる青コーダー達が語り尽くしてしまっているのですが、知識の整理を兼ねてPythonという遅い言語で競プロをやる上でのパフォーマンス関連の小ネタを少しまとめてみました。きっとどこかで見たような話ばっかりですが。

残念ながらPython競プロにおいて重要なnumpy/scipyネタは語れるほど知らないのでありません。LLだとnumpy/scipy使わないとほぼ絶対通せない系の問題がたまにあるのでいずれちゃんとやらねばと思っていますが……。

以下でのベンチの数字は Core i5-8259U, DDR4-2400 8G, Ubuntu 18.10 x64, Python 3.7.0 でのデータです。


リストのindexingを極力避ける

リストaに対してa[0]のようにしてアクセスするアレですが、何故かPythonはこれが異様に遅いです。

a = list(range(10**6))

%%timeit
ans = 0
for i in range(len(a)):
    if a[i] % 2 == 0:
        ans += 1

リストa内に偶数の要素が何個あるか愚直に数えている感じですが、これをipythonで実行すると

72.7 ms ± 910 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

こんな感じに実行時間が出てきます。ではaの要素を直接変数で受けて判定したらどうでしょう。

%%timeit
ans = 0
for n in a:
    if n % 2 == 0:
        ans += 1

45.7 ms ± 282 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

と6割くらいになりました。実は最初の書き方、

%%timeit
ans = 0
getitem = a.__getitem__
for i in range(len(a)):
    if getitem(i) % 2 == 0:
        ans += 1

76.8 ms ± 1.69 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

特殊メソッドを呼んで要素を得るのに近いくらい遅いです。なんとなくカジュアルにa[0]とかやってたのが関数呼び出しくらい遅いとかヤバヤバですよね。インデックスが欲しい場合でもenumeratezipでインデックス用のrangeをまとめて回すなどしたほうがかなり速いです。

これは差が大きいのでどのような用途であれ不必要にリストを直接触るのを避けたほうがいい(受ける変数名に適切な名前を付ければコードの見通しも良くなる)ですが、特に滅茶苦茶影響が大きいアルゴリズムとしてワーシャルフロイド法があります。

D - バスと避けられない運命
Submission #3917065 - AtCoder Beginner Contest 012
Submission #3917007 - AtCoder Beginner Contest 012

ほぼワーシャルフロイドやるだけの問題でTLは5秒。上は教科書的なワーシャルフロイドで下はindexingを極力避けて最適化したものですが、最適化版は3秒でACなのが普通にやると5秒あってもTLEです。ワシャフロはソラで書ける実装の軽さで女子高生にも人気ですが、Pythonの場合は最適化したものをライブラリに持っておいたほうがいいです(上のリンク先の自作ワシャフロ使っていいよ!エッヘン)。


組み込み関数・標準ライブラリを使いこなそう

PythonはCで書かれており、組み込み関数や標準ライブラリで完結する処理はCにやらせてるようなもん(超適当)なので、Pythonの世界内で自前実装するより遥かに高速であることが多いです。

In [71]: %%timeit
    ...: ans = 1
    ...: for i in range(2, 10**5+1):
    ...:     ans *= i
    ...:
1.82 s ± 3.53 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

In [72]: %%timeit
    ...: ans = math.factorial(10**5)
    ...: 
108 ms ± 303 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

105!は456573桁にも上るとんでもない数ですが、math.factorialを使うと一度きりなら十分高速にmod無しで計算しつくすこともできます(メモリもそれほど食いません)。さすがにバカでかい数を何度も取り回してると遅いので、繰り返し階乗を求める場合はループで逐一modを取ったり1からNまでの階乗をループ回しながらリストに保存していくなどする必要があり、そういった標準で提供されない機能に限り自分で実装するわけですが、意外と競プロ的に都合のいい関数やオプションが標準で用意されていたりします。

お恥ずかしながら私も最近まで知らなかったのですが、Pythonのべき乗を求めるpow()は第三引数にmodを与えることでmodを取りながら計算することができ、おそらく内部的に繰り返し二乗法のような効率的な実装がなされているので、繰り返し二乗法も自分で実装する必要はありません。

In [88]: %%timeit -n1 -r1
    ...: # 12345678 ^ 1000000000000 % 1000000007
    ...: n, exp, mod = 12345678, 10**12, 10**9+7
    ...: ans = 1
    ...: 
    ...: while exp:
    ...:     if exp & 1:
    ...:         ans = (ans * n) % mod
    ...:     n = (n * n) % mod
    ...:     exp >>= 1
    ...: print(ans)
    ...:
174484875
20.3 µs ± 0 ns per loop (mean ± std. dev. of 1 run, 1 loop each)

In [89]: %%timeit -n1 -r1
    ...: print(pow(12345678, 10**12, 10**9+7))
    ...: 
174484875
14.9 µs ± 0 ns per loop (mean ± std. dev. of 1 run, 1 loop each)

他によく使う例として、二点間のユークリッド距離を求めるときにピタゴラスの定理を使いますが、自分で二乗してルートしたりしなくてもmath.hypot()にx軸の距離とy軸の距離をぶん投げるだけでよく、距離がマイナスでもよしなに取り計らってくれます。

In [94]: math.hypot(1, -1)
Out[94]: 1.4142135623730951 

小数を返す関数は、小数の精度の面でも自前であれこれやるよりメリットがあります。

上で述べたリストの参照回数を減らすためのenumeratezipなども含め、Pythonが用意してくれている便利機能を知り使いこなすことは競プロにおいても非常に重要です。競プロ中級以降へ進み速度面からC++へ移行したとしても、幅広い知識を持って使うPythonは素早い雑魚散らしに変わらず役立つことでしょう。公式リファレンスは一通り読んでおいて絶対に損はありません。

Python 標準ライブラリ

ちなみに、math.gcd()など一部の比較的新しいバージョンで追加された関数は、Python3.4環境であるAtCoderでは使えません。3.5から追加された機能は多いのでバージョン問題には気をつけてください。


itertoolsを使いこなそう(ただしパフォーマンス上の懸念あり)

上と被りますが、Pythonのとっても便利なライブラリitertoolsイテレータをうまいことアレコレしてくれる便利なツールで、特に競プロ的には便利極まるものです。

In [31]: for a in itertools.permutations(range(3)):
    ...:     print(a)
    ...: 
(0, 1, 2)
(0, 2, 1)
(1, 0, 2)
(1, 2, 0)
(2, 0, 1)
(2, 1, 0)

In [32]: for a in itertools.combinations(range(3), r=2):
    ...:     print(a)
    ...: 
(0, 1)
(0, 2)
(1, 2)

In [33]: for y, x in itertools.product(range(3), repeat=2):
    ...:     print(f"x={x}, y={y}")
    ...: 
x=0, y=0
x=1, y=0
x=2, y=0
x=0, y=1
x=1, y=1
x=2, y=1
x=0, y=2
x=1, y=2
x=2, y=2

これらを使わなくても愚直に書けますが、多重ループにした上に重複チェックが必要になったりとネストが深く煩雑になりがちなところをスッキリ書けるメリットは大きく、使えるところでは積極的に使っていきたいライブラリです。

また、itertools.permutationsitertools.combinationsでは重複のないイテレータを返してくれるため、自前でループ内で重複チェックするよりかなり定数倍が抑えられるのでは?と思い、もともとこの記事を書こうと思ったときはパフォーマンス最適化の側面からもこれらのライブラリを推そうと思っていました。ところがコードを試してみると……

てな感じで愚直に多重ループなどで書き下すより遅くなる場合があることが判明してしまいました。リプにてヒントを頂けました(はっほーさんありがとうございます!)が、どうもitertoolsのこれらの関数は引数を展開して内部に持っておくような感じで、極端な例でいうと

f:id:htkb:20190107140009j:plain

rangeを先にリストに展開している3番目のケースとitertoolsを使った左2ケースのメモリ使用量に注目してください。内部的には同じように展開して保持しているものと思われるため、ある程度以上の長さのイテレータ等を投げるとメモリ使用量やメモリアクセスが足を引っ張るような感じです。というか展開しないと順列や組み合わせを作れないのでよく考えればあたりまえの挙動な気もしますが……。

実際のところこんなに長いrangeイテレータを与えることはなく、もしそういうケースがあるならそもそもPythonではどうやってもTLEなので、基本的にはitertoolsを使って楽をしていくのがいいと思いますが、このようなメモリ上の問題があることは知った上で使ったほうがよさそうです。特にどうもproductは遅いようなので定数倍が気になる問題では避けたほうがいいのかも。便利なんですけどね。


属性アクセスをキャッシュする

例えばリストのお尻にどんどん要素を追加していく場合、ループ内でa.append(x)などとするわけですが、ループ外でa.appendを変数に取っておくと少し速くなります。

%%timeit
a = []
for i in range(10**6):
    a.append(i)

62.1 ms ± 337 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

%%timeit
a = []
append = a.append
for i in range(10**6):
    append(i)

47.1 ms ± 278 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

この差は何でしょうか?私は低レイヤわからないマンですが、disライブラリを使って逆アセンブルのまねごとをしてみます。

In [50]: import dis
In [51]: a = []

In [52]: append = a.append

In [53]: dis.dis(lambda: a.append(1))
  1           0 LOAD_GLOBAL              0 (a)
              2 LOAD_METHOD              1 (append)
              4 LOAD_CONST               1 (1)
              6 CALL_METHOD              1
              8 RETURN_VALUE

In [54]: dis.dis(lambda: append(1))
  1           0 LOAD_GLOBAL              0 (append)
              2 LOAD_CONST               1 (1)
              4 CALL_FUNCTION            1
              6 RETURN_VALUE

a.append(1)のほうはグローバル変数aを読み込んだ後、appendメソッドをさらに探しています。ここで初めて指定のメソッドが存在しなければAttributeErrorを吐くなどのプロセスも踏んでいるでしょう(lambda定義時点では存在しないメソッドを指定しても怒られないため)。一方でappend(1)のほうはグローバル変数appendを読み込むだけで終わりです。つまりメソッドの名前探索やAttributeErrorの処理が全部終わった状態から始められるということです。

リストのindexing問題ほど生死を分かつようなことはあまりない気がしていますが、全探索やグラフの最短経路探索などでキューやスタックをぶん回すときは、おまじないとしてループ外でキャッシュしておくといいでしょう。また優先度キューでheapqを使うときや二分探索でbisectを使うときは

from heapq import heappush, heappop
from bisect import bisect_left

のようにしてimportすると同じ効果が得られ手間が省けます。ただし、import *はお行儀が悪いのでおすすめしません。競プロerがお行儀を語るとか噴飯ものと言われるかもしれませんが。


クラスのメソッドと関数の速度差

主にデータ構造は内部に実データを持つと取り回しが楽なのでクラスを定義して使いたいわけですが、鈍足のPythonではどうしてもパフォーマンスへの影響が気になるもの。ですが、結論から言うと若干の差はあるものの気にするレベルではありません。例としてUnionFind木のクラス版と関数版を比較してみます。

クラス版

class UnionFind(object):
    __slots__ = ["nodes"]

    def __init__(self, n: int):
        self.nodes = [-1]*n

    def get_root(self, x: int) -> int:
        if self.nodes[x] < 0:
            return x
        else:
            self.nodes[x] = self.get_root(self.nodes[x])
            return self.nodes[x]

    def unite(self, x: int, y: int) -> None:
        root_x, root_y = self.get_root(x), self.get_root(y)
        if root_x != root_y:
            bigroot, smallroot = \
                (root_x, root_y) if self.nodes[root_x] < self.nodes[root_y] else (root_y, root_x)
            self.nodes[bigroot] += self.nodes[smallroot]
            self.nodes[smallroot] = bigroot

関数版

def get_root(nodes, x: int) -> int:
    if nodes[x] < 0:
        return x
    else:
        nodes[x] = get_root(nodes, nodes[x])
        return nodes[x]


def unite(nodes, x: int, y: int) -> None:
    root_x, root_y = get_root(nodes, x), get_root(nodes, y)
    if root_x != root_y:
        bigroot, smallroot = \
            (root_x, root_y) if nodes[root_x] < nodes[root_y] else (root_y, root_x)
        nodes[bigroot] += nodes[smallroot]
        nodes[smallroot] = bigroot

クラス版の__slots__属性は、これがあるとここに列挙されている名前以外のインスタンス変数を取れなくなり、動的に追加することができなくなる代わりにメモリ消費量やパフォーマンスが改善されるというものです。この__slots__の有無についても効果を見てみます。

AtCoder Typical Contest 001 B - Union Find

集合の連結と連結判定を求められる、ライブラリのverifyに使える問題です。頂点数<=100,000, クエリ数<=200,000

クラス(__slots__あり) 515ms
Submission #3955762 - AtCoder Typical Contest 001

クラス(__slots__なし) 507ms
Submission #3955758 - AtCoder Typical Contest 001

関数版 430ms
Submission #3955770 - AtCoder Typical Contest 001

互いに素な集合 Union Find| データ構造ライブラリ | Aizu Online Judge

求められる出力フォーマットが違うだけでそれ以外は上と全く同じ問題。頂点数<=10,000, クエリ数<=100,000

クラス(__slots__あり) 0.34s
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3326955

クラス(__slots__なし) 0.40s
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3326956

関数版 0.32s
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3326957

__slots__の効果が微妙な感じだったのが残念ですが(これも最適化ネタとして紹介したかったのに……)、とりあえず現実的な制約下ではクラスのメソッドを20万回くらい叩いても0.5秒程度、関数版との差は0.1秒未満なので、生のリストを持って関数に投げるような面倒な取り回しをするよりもクラス化してしまったほうがいいと思います。


for _ in [0]*x?

In [61]: %%timeit
    ...: for i in range(10**8):
    ...:     1+1
    ...:
1.46 s ± 74.9 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

In [62]: %%timeit
    ...: for _ in [0]*(10**8):
    ...:     1+1
    ...:
1 s ± 7.13 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

In [63]: %%timeit
    ...: for _ in [None]*(10**8):
    ...:     1+1
    ...:
1 s ± 9.58 ms per loop (mean ± std. dev. of 7 runs, 1 loop each) 

ループカウンタを参照しないときにrangeを回すより[0]*xを回したほうがほんの少し速いです。[None]のほうがさらに微妙に最速だったと記憶していましたが違いは出ませんでした。ぶっちゃけ無意味で邪悪なので使わなくていいです。ただ参照しないループカウンタは_で参照しないことを明示するのは有用と思います。IDEも先頭が_の変数名は未使用でも怒らなかったりするんでpepかなんかに書いてある気がします(適当


割り算を避けても速くならない

多くの言語では割り算や剰余計算が他の計算より桁一つ以上遅かったりするので、定数倍が気になる場面では偶奇判定に1とのandを取ったり、2で割って切り捨てるのをビットシフトに置き換えたりするテクがありますが、Pythonの割り算や剰余計算は他の演算とほぼ等速なのでそのような工夫をしても速くなりません。

In [11]: %%timeit -n1 -r1
    ...: ans = 0
    ...: for i in range(10**7):
    ...:     ans += i % 2
    ...: print(ans)
    ...: 
5000000
483 ms ± 0 ns per loop (mean ± std. dev. of 1 run, 1 loop each)

In [12]: %%timeit -n1 -r1
    ...: ans = 0
    ...: for i in range(10**7):
    ...:     ans += i & 1
    ...: print(ans)
    ...: 
5000000
550 ms ± 0 ns per loop (mean ± std. dev. of 1 run, 1 loop each)

In [13]: %%timeit -n1 -r1
    ...: ans = 0
    ...: for i in range(10**7):
    ...:     ans += i // 2
    ...: print(ans)
    ...: 
24999995000000
576 ms ± 0 ns per loop (mean ± std. dev. of 1 run, 1 loop each)

In [14]: %%timeit -n1 -r1
    ...: ans = 0
    ...: for i in range(10**7):
    ...:     ans += i >> 1
    ...: print(ans)
    ...: 
24999995000000
593 ms ± 0 ns per loop (mean ± std. dev. of 1 run, 1 loop each)

ビット演算は一般的に速いイメージですが、Pythonだと何故か割り算を含む四則演算よりほんの少し遅い感じなので、わざわざ避けるほどではないですが速度を稼ぎたいときにビット演算に直すテクは有効ではありません。

Hello 2019

ooo----- 1466 -> 1510

A. Gennady and a Card Game

AC: Submission #47904524 - Codeforces

それぞれについて1文字目と2文字目に分けて比較しましょう。

B. Petr and a Combination Lock

AC: Submission #47909911 - Codeforces

N <= 15なので215=32768の全列挙は余裕なのでビット列を利用したそれぞれについてプラスとマイナスを全通り試す全列挙をしましょう。どうやらTL情報ではmod 360を取ってない人をhackし放題の釣り堀だったらしいが…?そんなんpretest通るんかいな?

C. Yuhao and a Parenthesis

AC(3WA): Submission #47925456 - Codeforces

validかどうかわからない括弧列を2つ組み合わせてvalidな括弧列をできるだけ多く作ってねという問題。ただ左右のネストの深さだけ見ればいいんだったら簡単なんだけど、問題はどうやっても使いようのないゴミの存在。この問題は2つの文字列を組み合わせることしか許可されないので、)(のような左からも右からも閉じてもらえないとvalidにならない文字列は絶対にペアに含めないので取り除かなければならない。この条件に手間取って3WAを叩いた(むしろ中途半端に通らなくて良かったが)。

ポイントとしては、)を-1,(を+1と考えたとき、左から累積を取っていって途中で一度でも累積値がマイナスになった場合、左向きのネストを後の文字列で解消することができないため、その括弧列は必ず左から(で閉じてもらわないとvalidになり得ないということ。なので累積和を取った数列のminがマイナスになった括弧列は、必ず負(左向き)の括弧列としてしか採用できない。じゃあmin(累積値の数列) < 0 and 最終的な累積値 < 0ならばOKかというとまだ条件が足りない。)))(は累積値の最小が-3で最終的な累積値が-2だが、両向きに閉じ括弧を必要とするゴミだ。累積値のマイナスが最も大きいところからプラス側にいくらか戻して終わった場合、最小の地点から見て右向きの括弧のネストができているということなので、それを除くには負のネストが最深の状態で括弧列が終わらなければならない。

結局条件はmin(累積値の数列) == 最終的な累積値 < 0(左向きの括弧列)もしくはmin(累積値の数列) >= 0(右向きもしくは単体でvalidな括弧列)となる。あとは0は0同士、それ以外は符号を反転した数字の出現数同士を比べてペアを作る。

他の人のpythonのコードはもっと綺麗だったけどなんかもっとうまく条件付けられるのだろうか(ちゃんと読んでない)。なんか重そうな処理させそうだったので一応pypyで投げたけど、コンテスト後python3で投げ直したが余裕だった。

Good Bye 2018

ooo---- 1430 -> 1466

Codeforces久しぶりに出た。2018ラストなので。

A. New Year and the Christmas Ornament

AC: Submission #47733927 - Codeforces

あたまわるいのでこういう問題嫌いです。愚直に場合分けしたけどr, b-1, y-2の中で一番少ないものに引きずられるのは自明なので、min(r, b-1, y-2)*3 + 3で良いようだ。

B. New Year and the Treasure Geolocation

AC: Submission #47738516 - Codeforces

あたまわるいのでシミュレートして指してるマスが最多のマスを出力したが、「今回は目をつぶってやるが遅いpython使うならちったあ頭使えや」的な意思を実行時間から感じます。あたまのよい人は全ての座標を足して平均を出したり、x最小のオベリスク座標とx最大の距離座標を足したりしてO(1)で答え出してる模様。

C. New Year and the Sphere Transmission

AC: Submission #47747369 - Codeforces

なんとなく雰囲気で解いた問題。Nとkが互いに素だと結局全部の人を回ることになる?のでk=1のときと同じ結果になる。そうでなくkがNの約数だと、飛び飛びに回していってちょうど1周で1の手に戻ることになる。1-indexedで考えるとめんどくさいので一旦0-indexedで考えてみると、0 -> N * (k/N) * 1 -> N * (k/N) * 2 -> ...という感じ、例えばN=8, k=2だったら0 -> 2 (8*(2/8)*1) -> 4 (8*(2/8)*2) -> 6 (8*(2/8)*3)で0に戻る。各項の最後に掛けてある数は1〜N-1までの総和なのでN * (k/N) * (N-1) * N // 2となって、0-indexedにしていたのでその分回った人の数k/Nを足して1-indexedに戻して終わり。これを約数全てに対して行う。√Nまで見れば平方数を除き√Nを堺に約数が現れるので(略。もっと綺麗に解ける気がする。

AtCoder Grand Contest 030

o--- 1600 -> 1607

A - Poisonous Cookies

AC: Submission #3892026 - AtCoder Grand Contest 030

やるだけなんだけど解毒クッキーより毒クッキーが多い場合毒クッキーを食べる数は解毒+1になるとか、タイムアタックやってると足引っ掛けそうでおっかない問題。WAせずに早解きできたことで一命をとりとめた。

B - Tree Burning

最初から部分点狙いで行ったが、結局かなりの時間考えがまとまらなかった。最初はグラフ問題かとか距離を負にしてダイクストラでもすんのかとかスットコドッコイなことばっかりずっと考えていて、DPに行き着いてもどう状態を管理するのかピンと来なかった。dp[左端][右端]ってやるにしても現在左端にいる状態と右端にいる状態って別だしなあ……などと時間を潰してタイムアップ。

結局部分点解法はdp[l][r][2]として今左にいるか右にいるかを別に取れば良いのだった。ただpythonだとリストの使い回しや変数にキャッシュして不必要にリストにアクセスしないなど定数倍改善をかなり頑張らないと辛かった(本番ならpypyで通すけど)。

部分点: Submission #3897596 - AtCoder Grand Contest 030

満点は最初にx個の木を直進しながら燃やしてその後はジグザグ、という動きをすべてのxについて試す。最初からジグザグに進むのが最適なら思いつけたかもしれないけど、この考えはサンプル1で否定されていたので早々に捨てていたし、最初にいくらか直進するって発想は思いつけそうにない。

AC: Submission #3900730 - AtCoder Grand Contest 030


青から落ちず今年を終われたのは良かったけど、最後の最後で周りがみんな通してる典型DPを取れなかったのは本当に反省。もともとDPに苦手意識はあったし解けるDP問題も今までこんな感じにDP組んだのでこんな風に遷移させるんだろう(適当)という感じのところが多々あったので、単に問題を多く解くだけでなく状態遷移をしっかり意識してDP書くのをとりあえずの目標にしたい。

CADDi 2018

oox- 1560 -> 1600

C - Product and GCD

AC: Submission #3840276 - CADDi 2018

ん〜これxのN乗がPを割り切るか√Pから2まで試してみればいいだけなんじゃないの?と思いそのまま書いたらTLE、何でTLEなのかすぐにピンと来ずpypyで投げ直してみようかと思ったがそうする前に気づけてよかった。制約よりN <= 10^12なのでx^Nなんて計算するといくら多倍長のpythonでも死んでしまう。が逆に言えばNが少し大きくなると余裕でPの上限である1012を超えるので、そのようなケースは試すまでもなく答えが1になる。2^40 = 1099511627776 > 10^12なのでNが40未満のケースのみシミュレーションすればいい。

D - Harlequin

AC: Submission #3841148 - CADDi 2018

少し前までゲーム系問題の互いに最適に動くというのが頭こんがらがってアレルギーで、その時いろんなgrundy数などを説明しているサイトを見て回ったのがとっても役立った。↓は説明下手くそなのでわからない人はgrundy数でググって見て回るといいとおもいます。

勝敗が確定している状態から逆回しに考えてみる。例えばりんごが1種類のみ1個残っていた場合、それを食べれば勝ちなので勝ち確定の状態。そしてりんご1種類のみ2個残っていた場合、同じ種類のりんごを2個以上食べることはできないので、1個だけ食べて1種類1個の勝ち確の状態を相手に回さなければならないため負け確。そして1種類のりんごが3個、あるいは2種類のりんごの個数が{1, 2}個の場合、適切に食べることで1種類2個の負け確の状態を相手に渡せるため勝ち確。……という風に逆回ししていくと、手番で奇数個のりんごがあればそれを処理してすべて偶数個にして相手に回し続けることで、相手がどう動こうとも最終的に1種類が2個のような状態を作れるため勝ち。逆に偶数個のりんごしかないと相手に同様の戦法を取られるので負け。

E - Negative Doubling

このインデックスから左は符号マイナス、右はプラスに決め打ちするという発想はあったが、そのインデックスを動かしたときの必要な操作回数が下に凸になると思ったので(正しいか不明)三分探索を試してみたがpypyであえなくTLE。インデックスを決め打ちした後の貪欲の実装がぐっちゃぐっちゃになったのもあるが……。解説みながら組んでもなんか通らないので後でやる(いつまでも記事が公開できないため)。