ボードゲーム（Kalah）を一緒に遊んでくれるAIを作りたい 前編

1.はじめに

春休みの自由研究ということで、かねがねやりたいと思いつつも時間がないとかなんとかｺﾞﾆｮｺﾞﾆｮ言っていた「ボードゲームを遊んでくれるAI」に取り組んでみました。とりあえず一区切りつくところまで来たので途中経過の報告みたいな感じです。コードはそのうちGitHubに上げる予定です。

オセロや将棋を機械学習で強くした人工知能にやらせるというのは非常に魅力的で、割とそういうこともやりたいなぁと思って情報系に進んでみたものの、講義でやるのは理論寄りな話や泥臭い作業（人工的な設定のモンテカルロ木探索やありえんめんどい自動微分の実装など）ばかりで、自分からはかなり遠くのものに感じられてちょっとウ〜ンとなっていました。

そこで、せっかく長期休みなのだから自分で何かしらこういうのを作ってみよう、ということで取り組んでみたのがこれになります。題材とするボードゲームは"Kalah"（カラハ）です。Kalahはマンカラというゲームの亜種みたいなものです。
マンカラ - Wikipedia
カラハ - BGAうぃき - atwiki（アットウィキ）

ただ機械学習なんも分からんの状態からいきなり人工知能を作りましょう、も無理な話なので、とりあえず目標を細かく分けてみることにしました。以下がそれになります。

大目標：ボードゲームを作り、対戦相手として実際にプレイする思考ルーチンを機械学習で作る

・中目標A：コマンドライン上でKalahを遊ぶプログラムを作成
・中目標B：ゲームのUIを作成
・中目標C：エージェント（人工知能）を作成

現時点でエージェントの作成まで（中途半端ですが）終了したので、そこまでに何をしたかを記録として残しておきます。あと私は本を買っても全く読まない悪癖があるので、今回は本なしでインターネット全頼りでやってみることにしました。

2.やったことのあらまし
（1日あたりだいたい6~7hくらいです）

2-1.~GUI作成
・Kalahをコマンドライン上で対戦する環境を作成（1日）
・Tkinterを使ってKalahを遊べるGUIを作成（2日）

2-2.DQNでエージェント作成
・資料集め、tensorflowなんも分からんくて大泣き（2日）
・tensorflowに慣れるために、DQNで3*3の超絶シンプルな迷路を解くエージェント作成（2日）
・Kalahをコマンドライン上で遊んでくれるエージェント作成（2日）

3.やったこと

※実装は全てPython3です。

3-1.Kalahアプリ制作
なにはともあれまずはKalahのボードとか作らないと人工知能もクソもないので、とりあえずコマンドライン上でKalahを遊べるようにしました。以下のサイトを参考にしましたが、Classはふわっとした理解なのでちょっと心配です。
Python初心者は練習問題としてリバーシ(オセロ)を実装するべき - 勇気ある加藤の猛り

そしてプレイできるようになったはいいものの、自分が先手しか選べなかったり、なによりコマンドラインの味気ない背景でしか動かせないのも寂しいなあと思ったので、TkinterというPythonのライブラリを使ってGUIを作ってみることにしました。以下に（主に）参考にしたリンクを挙げておきます。
Pythonで「マインスイーパー」を開発 | だえうホームページ
tkinterを使ってはさみ将棋の将棋盤を作る - Qiita

できたものがこちらです（ここにGIFを貼る）

こうやってGUIを作るのは初めてなので慣れないこともあり、素人目に見てもかなりお粗末な感じのUIができましたが、それでもちゃんと動くものを作れた時はちょっとした達成感がありました。この時点ではCPUは合法手をランダムに打つだけのダメダメCPUです。

あと、開発環境はmacbook proなのですが、Tkinterを普通に使うと強制終了してしまうのでセーフモードで走らせていました。これどうにかならんかな......

コードは以下になります
warehouse/kalah_play_on_gui.py at main · Syuko4omi/warehouse · GitHub

3-2.tensorflowの導入

さて、いよいよKalahの対戦相手になってくれるAIを作ろうというモチベーションも湧いてきたわけですが、機械学習をフルスクラッチするのは無理！　勾配を手作業で出すのはもう勘弁して！　ということでライブラリにお任せするために、機械学習の分野では有名らしい（流石に何も知らん自分でも名前くらいは聞いたことがある）tensorflowを導入することにしました。退屈なことはPythonにやらせよう。Pythonすまん。

ウチのMBP君はtensorflow未対応だったので、これを機に入れてみました。AnacondaでPythonを使っていたので以下のリンクの知恵で救われました。
Python3 TensorFlow for Mac 環境構築 - Qiita
Anaconda PromptでのTensorFlowの導入に苦戦した話 - Qiita

3-3.DQNについてちょっと勉強

ボードゲームをプレイする思考ルーチンにも色々種類があると思います。n手先読みをするミニマックス法やネガマックス法、それこそ前述したモンテカルロ木探索等あると思いますが、そういう探索系アルゴリズムは結構授業でやったし正直しんどい実装が多かったので、学習する環境を整えて後は機械が自分でお勉強してねと丸投げする、いわゆる強化学習を実装してみることにしました。

概念的なこと（具体的に何をやっているのかの説明や、アルゴリズムに関すること）は以下のページを読んだり動画を見たりして理解したりしなかったりしました。
ゼロからDeepまで学ぶ強化学習 - Qiita
DQNの生い立ち ＋ Deep Q-NetworkをChainerで書いた - Qiita
【Pythonで再現】DeepMindのDQNアルゴリズムを再現してみた | ブログ一覧 | DATUM STUDIO株式会社
全力で人工知能に対決を挑んでみた（理論編） - ニコニコ動画
強化学習の基本的な考え方 - Qiita
https://book.mynavi.jp/manatee/detail/id=89691
高校数学で理解・実装するニューラルネットワーク - Qiita
https://book.mynavi.jp/manatee/detail/id=76390

ただコード見てても何も分からん......という感じで、1日粘ってみても自力で実装もできそうにない気配だったので、とても簡単なモデルで機械学習の練習をしてみることにしました。

3-4.DQNで3*3のシンプルな迷路を解く（チュートリアル）

次のページは、実際に実装した問題設定になります。DQNの説明も分かりやすかったので本当に助かりました。
DQN（Deep Q Network）を理解したので、Gopherくんの図を使って説明 - Qiita

要は3*3の正方形（9マス）の左下をスタートとして、上下左右の移動をして右上のゴールを目指すことを機械学習させよう、という内容です。1行2列の入力xを現在位置、上下左右の移動の価値を数値的に表現する1行4列の出力yをy = Wx+bとして、Wとbを学習することでxを入力したら適切なyを返すようにしましょうねというのが本旨になります。

例えば真ん中のマスにいるなら、目指すべきゴールは右上に存在するので、yの成分のうち右、もしくは上の移動を表す要素の価値が高くなり、左や下の移動に対する価値が低くなるようにしたい、という話です。

隠れ層なし（つまり入力xに重みWが掛けられ、バイアスbが足されるだけで出力yになる）の最も単純なモデルで1500回の移動を学習をさせてみたところ、結果は以下のようになりました。

Q値のリスト、マス目、 最もQ値の高い移動方向が各列に表示されています。Q値は簡単に言えば行動の価値を表しています。Q値のリストはそれぞれ右、左、下、上に移動する際のQ値を表示してあります。マス目を表す[0,0]は左上（上から数えて0行、左から数えて0列）、[2,2]は右下を表しています。

例えば[2,1]のマス目はスタートから一歩右に進んだマス目なのですが、そのマスで最もQ値が高いのは上方向への移動になっています。上に移動すると[1,1]のマス目になりますが、Q値最大の移動方向は上です。上に移動した[1,0]では右に移動するのが最も良いと出ているので、無事ゴールにたどり着けます。全体的に見ても上、もしくは右方向への移動が良さそうだと学習ができているので、うまくいっていそうな気配がします。

[[0.69636935 -0.30203688 -0.3140987  -0.0802336 ]] [0, 0] right
[[1.77409495 0.32050276 0.25299944 1.6524037 ]] [0, 1] right
[[2.85182055 0.9430424  0.82009758 3.385041  ]] [0, 2] up
[[1.53447878 0.71656002 0.5865594  1.1624039 ]] [1, 0] right
[[2.61220438 1.33909966 1.15365754 2.8950412 ]] [1, 1] up
[[3.68992998 1.9616393  1.72075568 4.6276785 ]] [1, 2] up
[[2.37258821 1.73515692 1.4872175  2.4050414 ]] [2, 0] up
[[3.45031381 2.35769656 2.05431564 4.1376787 ]] [2, 1] up
[[4.52803941 2.9802362  2.62141378 5.870316  ]] [2, 2] up

1500回の移動やしそんな時間かからへんやろ〜とか思っていたら余裕で二時間かかってひっくり返りました。tensorflowの演算が明らかに遅いのでもっと良いスペックのパソンココが欲しくなりました。

初めてtensorflowを使ってみて引っかかったところなどを以下にあげておきます。

・tensorflowのVariableを実行時に初期化しないと怒られが発生する（セーブした変数の情報をロードする際はこの限りではないです）
サルでもわかるtensorflow：基本的な変数の扱い方 - Qiita

・隠れ層がある場合、重みを全部1で初期化すると重みが全く変化しない（ことがある）。重みの初期化関連の情報でこういう言及を見たことがないのですが、なにか原因があったりするんでしょうか。そのうち調べてみるつもりです。

・experience replay、報酬のclipping、重みの反映を後回しにする等は実装しましたが、これが無いと本当に上手くいかないかどうかは検証していないので分かりません。

・最適化アルゴリズムは最急降下法を使いました。Adamの方がいいぞ（Adamおじさん）という声はちらほらあったのですがなぜかAdamは実行の時点で引っかかってしまいました。

参考にしたページを挙げておきます。以下の四つはかなり参考になりました。

NNの仕組み↓
ニューラルネットワークの基礎 — ディープラーニング入門：Chainer チュートリアル

tensorflowを使った機械学習のシンプルなやつ↓
TensorFlowのチュートリアルのチュートリアル - Qiita
TensorFlowを使ってシンプルなニューラルネットワークモデルを作ってみる - 株式会社ロカラボ

同じように迷路を解いていた例（問題設定は別）↓
DQNで自作迷路を解く - Qiita

実装したコードは以下になります
warehouse/meiro_nn at main · Syuko4omi/warehouse · GitHub

3-5.Kalahを遊ぶエージェントの作成

オセロでやってた方のページ（参考にしました）↓
Keras+DQNでリバーシのAI書く - Qiita
四目並べ（まだ読んでないけど面白そうなのでそのうち読みます）↓
kaggleで強化学習をやってみた - 機械学習 Memo φ(・ω・ )

いよいよエージェントの作成ですが、迷路の学習と本質的には同じです。とりあえず何も考えずに、自己対局によって生成した10000局面（およそ250試合）について学習を回しました。

Kalahはだいたい1ゲーム40手以内に決着が着くので、80手を終えるごとにニューラルネットワークの重みを更新することにしました。最序盤では40手ごとに更新でええか〜とか思っていたのですが、40手だと先手ばかり勝ったりして後手の勝つパターンが学習できていなかったので急遽こうなりました。言い忘れていましたが、このゲームは先手がかなり有利です。

マシンスペック的なアレなのかコードを書くのがヘタクソで思わぬ副作用が生じているのか何なのかよくわからないんですが、学習がありえん遅くて丸一日回していても10000局面（40手/1試合くらいなので250試合くらい？）しか学習できなかったというのが正直なところです.....。

最後に対ランダムで10000試合行わせました。先手勝率: 3642/5000(72.84%)、後手勝率: 4201/5000(84.02%)となりました。

ただ勾配の係数（optimizerの刻み幅的なアレ）が0.01とか小さすぎて実際は途中から学習が進んでいなかったようで、4000局面（約100試合）見た時点でも既に先手勝率: 3658/5000(73.16%)、後手勝率: 4115/5000(82.3%)となっていたので、あまり良い学習ができていなかったと思います。ちなみに自分も戦ってみましたが、先手後手いずれもこちらの勝ちだったので強さ的にはまだまだだと思います。

それでも自己対局しただけでもそこそこランダムには勝ち越せるようになっていたので、実装の方向性は間違っていなかったような気がします。ズブの素人に負けるAIはカッコ悪いので、後編ではバチバチに強く育てたものを作りたいです。あと作ったGUIと組み合わせてアプリ上で対戦できるようにもしたい。

後編へ続く

チュウニズム クリスタル（プラス）までを振り返って

ベスト枠平均が15.8343でした。去年の12月にはMAX15.8を達成しました。

ベスト枠詳細↓

下限から15.7を追い出したりして、ゆっくりながら(この一年で700クレやっていました)まあまあ成長できたかなあとは思います。

11月にリングフィットアドベンチャーをやり始めてからは特に成長した気がします。筋肉がついて多少のことでは腕がへこたれなくなったり、指先に力が入るようになってそれなりに正確にノーツを押せるようになったことが原因かと思います。
正直初めて一週間くらいで神威が7200出たのはびっくりしたし、この曲は腕にどれだけ力を入れ続けられるかの（瞬発力よりは）持久力をかなり問うてくる曲だと思います。

しかし未だに京急はSSSが取れません。どうして…………………………………………………………………………………………………………………………

次回作のチュウニズムパラダイスも楽しみです。

Pythonの深さ優先探索で失敗した話

ハミルトン閉路が存在するか判定する問題。入力は、
n m
x_1 y_1
x_2 y_2
... ...
x_m y_m
で与えられる。（nは頂点数、mは辺の数。x_i,y_iは頂点x_iとy_iを結ぶ辺が存在することを表す）

#合ってるコード(しかしこれもn=15くらいだと落ちるね......)
n,m = map(int,input().split())
edge = []
for i in range(n):
    T = [0]*n
    edge.append(T)
for i in range(m):
    x,y = map(int,input().split())
    edge[x][y] = 1
    edge[y][x] = 1

def dfs(cur, checked, rest): #curは現在いる点、checkedは訪れた点、restはこれから訪れる点
    if len(rest) == 0:
        if edge[cur][0] == 1: #全点探索が終了したら、現在いる点と点0の間に辺があるかどうかを判定
            print('Yes')
            exit()
    else:
        for i in range(n):
            if edge[cur][i] == 1:
                if (i in rest) and (i not in checked):
                    L = []
                    for j in range(len(rest)):
                        if rest[j] != i:
                            L.append(rest[j])
                    temp = [i]
                    for j in range(len(checked)):
                        temp.append(checked[j]) #ここcopyに注意
                    dfs(i, temp, L)

P = [i for i in range(1, n)] #これから訪れる頂点のリスト
dfs(0, [], P) #点0からスタート
print('No')

間違えた理由はいくつかあって、まず
・dfsを同じ深さのfor文でやると、前の処理がそのまま後ろのfor文に引き継がれる（同時並行で進むわけではない）
・pythonの　= は参照渡し（なので値だけコピーしたいならdeepcopyを使わないといけないけど、deepcopyはバカ遅い）

#間違っているコード
n,m = map(int,input().split())
edge = []
for i in range(m):
    s,e = map(int,input().split())
    edge.append([s,e])

def dfs(cur, checked, rest):
    if len(rest) == 1:
        flag = False
        for i in range(len(edge)):
            if edge[i][0] == 0:
                if edge[i][1] == rest[0]:
                    flag = True
                    break
            elif edge[i][1] == 0:
                if edge[i][0] == rest[0]:
                    flag = True
                    break
        if flag:
            return True
        else:
            return False
    else:
        flag = False
        for i in range(len(edge)):
            temp = checked
            if edge[i][0] == cur:
                if edge[i][1] in rest:
                    if edge[i][1] not in checked:
                        flag = True
                        L = []
                        for j in range(len(rest)):
                            if rest[j] != edge[i][1]:
                                L.append(rest[j])
                        temp.append(edge[i][1])
                        return dfs(edge[i][1], temp, L)
            elif edge[i][1] == cur:
                if edge[i][0] in rest:
                    if edge[i][0] not in checked:
                        flag = True
                        L = []
                        for j in range(len(rest)):
                            if rest[j] != edge[i][0]:
                                L.append(rest[j])
                        temp.append(edge[i][0])
                        return dfs(edge[i][0], temp, L)
        if not flag:
            return False

P = [i for i in range(1, n)]
if dfs(0, [], P):
    print('Yes')
else:
    print('No')

復習 4/18,4/19

O(n)で前計算することで、各nCrをO(1)で求められるようにする。

mod = 10**9+7
MAX = 10**5+1 #nは10**5までを想定
fact = [1]*(MAX+1)
for i in range(1, MAX+1):
    fact[i] = (fact[i-1]*i)%mod
inv = [1]*(MAX+1)
for i in range(2, MAX+1):
    inv[i] = inv[mod%i]*(mod-mod//i)%mod
fact_inv = [1] * (MAX + 1)
for i in range(1, MAX + 1):
    fact_inv[i] = fact_inv[i-1]*inv[i]%mod
def comb(n, r):
    if n < r:
        return 0
    return fact[n]*fact_inv[n-r]*fact_inv[r] % mod

atcoder.jp
例えば(10**5)**(10**5)を10**9+7で割りたい、みたいな気持ちになった時に、for文で10**5を10**5回回してるとどエライ事になってしまう。a**bをmで割った余りは、pow(a,b,m)で高速に求められる。

atcoder.jp
ナップサックはi番目のものまで見たときに使う、使わないのふた通りの場合分けをちゃんと行うこと。サボるとどっかでミスる。

復習 4/9,4/10,4/11

atcoder.jp

1からkまでのiに対して、
・「i回目に働くのは一番早くて何日目？」
・「i回目に働くのは一番遅くて何日目？」
というのを格納した配列A,Bを考える。いずれも、oxの列を前から、後ろから見ていくことで可能。

結論から言うと、A,Bについて、A[i] == B[k-i-1]となる日付が「働くべき日」に該当する。

例えば、ooxoxoxoという配列で、「必ず1日以上開けて働かなくてはいけない」という制約をつけたらどうだろうか。
働く日数が二日であれば、上の配列はそれぞれ、
[0,3]
[5,7]
となることだろう。1回目に働くのは、遅くとも5日目に働けばいい。そう考えると、0,1,3日目に働く必要はない。同様に、0日目に働いてもいい。そうすれば、5日目を待たずとも二回仕事を終えることもできる。
以上より、「必ず働く日」というのは存在しない。

働く日数が三日であれば？　配列はそれぞれ、
[0,3,5]
[7,5,3]
となる。この場合も、実は働くべき日は存在しない。2回目に働く日は3,5日目のいずれかから選ぶことができるし、選んだ日付によって、例えば2回目に働く日を3日目にすれば、1回目、3回目に働く日はそれぞれ0と(5,7)日目になるし、5日目を選べば、1回目、3回目に働く日はそれぞれ(0,1,3)と7日目になるからだ。

最後に、働く日が四日であれば、配列は
[0,3,5,7]
[7,5,3,1]
になる。この時、最初に働く日付のみが問題になり、後の3,5,7日目については必ず働かなくてはならない。（A[i] == B[k-i-1]なので）
ということで、この場合は3,5,7日目となる。

atcoder.jp

累積GCDまでは思いついたが......という感じ。前から累積GCD取って、各クエリごとに「初めてGCDが1になるところはどこか？」を二分探索すればO(QlogN)で求まる。GCDが1にならないなら配列の最後とのGCDを求めてあげればいい。

atcoder.jp

部分列の和を求めるのはわかる。bitがk個以上立っている桁を大きい方から取ればいいのもわかる。しかし大きなbitがk個以上立っているものをまたかき集めて、その中から次の桁のbitが立っているものを選んで......とやっていると日が暮れるので、視点を「n(n+1)/2個部分和」ではなく、「k個選んできた後の論理積の最大値」に移す。これをxとすれば、二進法で表した時にたかだか40通りなので、各bitについて立てるか立てないかを、bitの大きい方から検討していけば良い。

具体的に言えば、ans = 0として、

ans = 0
for i in range(40, -1, -1):
    temp = ans+2**i
    cur = 0
    for j in range(len(list_sum)):
         if temp&list_sum[j] == temp:
                cur += 1
    if cur >= k:
         ans += 2**i

（擬似的なコードなので粗はあるけどこんな感じ）
上のような実装をしてあげればいい。ansについては過去の結果を持ち越すことになるので、「上からbitがk個以上立っている集合を選んできて、その中でまたk個以上立っているような下のbitを選んでくる」のようなことができていることになる。

めっちゃ賢い......

atcoder.jp

「ペア」なので、必ず二つの要素の組で考える。
大きい方から貪欲に、「ペア」を作れる相手を取ることを考える。（降順で固定する）

大小関係をつけることでわかることがある。例えば、今見ている要素pに対して、相手となる要素q（p>qとする）を取ってきた時、p+q=2^kとなるような2^kは、確実に2^(k-1) <= p < 2^kを満たしている。

ペアの和が2^kよりも大きい2のべき乗になることはない。例えばp<2^kとして、q = 2^(k+1)-pとすれば、p>qよりp > 2^(k+1)-pとなるので2p > 2^(k+1)となり、p>2^kから矛盾が生じる。よって、p+qでできる二のべき乗は、pより大きくて、そのなかで最も小さいような2^kに限られる（ここに気付けるかが肝心）

ここまでくれば大体OKだが、相手となる要素の個数を管理するのにpythonではCounterという便利なデータ構造がある。
例えば

from collections import Counter
L = [3, 11, 14, 5, 13, 3]
C = Counter(L)
#Counter({3: 2, 5: 1, 11: 1, 13: 1, 14: 1})
#C[3] = 2
#C[14] = 1

となる。これを使うことで、delete()などを使わなくても要素数を減らす操作が簡単にできる。

復習 4/2,4/3

atcoder.jp

必勝法ゲー。dpで遷移を見る。「j枚目で回ってきたときに勝てるか？」をdp[j]で管理する。
取れる枚数がn種類（a_1...a_n）あったとき、dp[j-a_i]が全て「win」であれば、必ず相手に「勝てる」状態で回してしまうことになるため、dp[j] = lose
逆にdp[j-a_i]がLoseになるものが一つでもあれば、相手に「負け」の状況を押し付けることができるのでdp[j] = winとなる。

atcoder.jp

BITを真面目に使った初めての問題。文字を入れ替えたら、BITの情報だけでなく元の文字列の情報も更新するのをお忘れなく

onlinejudge.u-aizu.ac.jp

巡回セールスマン問題。これ始点を0に固定しているけど、どの頂点から出発したとしても、必ず0は通るわけで、そのあとの道のりは全く同じになるので、別に頂点0にスタートを固定しても問題はなさそう。
すなわち、頂点i~頂点0(経路A)→頂点0~頂点i（経路B)は、B→Aとしても最小コストが変わらない。

v,e = map(int,input().split()) #v:頂点, e:辺
graph = [[] for i in range(v)]
cost = [[float('inf')]*v for i in range(v)]
for i in range(e):
    x,y,z = map(int,input().split())
    cost[x][y] = z
dp = [[float('inf')]*v for i in range(1<<v)]
#(1<<v)-1 == 2**v-1
dp[(1<<v)-1][0] = 0 #全ての頂点を訪れて帰ってきた時（ここがゴール）
for i in range(2**v-2, -1, -1): #まだ見ていない頂点集合に対して
    for j in range(v): #現在いる頂点から
        for k in range(v): #次に行く頂点について
            if i>>k & 1 != 1: #まだ訪れていないならば
                dp[i][j] = min(dp[i][j], dp[i|1<<k][k]+cost[j][k])
            #dp[i|1<<k]は「kを訪れた状態」を指す。
            #視点を変える。「今kにいる状態からゴールに至るのに必要なコスト」+「j→kに必要なコスト」は、
            #「今jにいる状態からゴールに至るのに必要なコスト」になる（遡る）
            #これを「今0にいる状態からゴールに至るのに必要なコスト」まで遡って計算する。
if dp[0][0] != float('inf'):
    print(dp[0][0]) #まだどこも訪れていない状態から、ゴールである0を目指して進む
else:
    print(-1)

シフト演算子が結構便利であることに気づいた。

復習 3/31,4/1

atcoder.jp

まずは美味しい順にソートして上からK個取る。そこから、残りのN-K個のうちでどれかと交換することで満足度が上がるかどうかを見ていくわけだが、この時、すでに取っているネタの種類がi種類であれば、そこから種類を減らすことによって満足度は決して上がらない。
何故ならば種類は多いほど満足度が上がるし、そもそも最初にK個選んだ時点で美味しい順に取っているので、i未満の種類を選ぶことによって純粋な「美味しさの和」を上昇させることが不可能なためである。

したがって、ここから
１、種類を減らさずに（★逆に言えば、現時点で食べようと思っている寿司の中にないネタを選んで）
２、交換することで満足度が上昇するか
についてを、残りのN-K個の寿司について考える。（N-K個も美味しい順にソートしておく）

交換するのは、現時点で食べようと思っている寿司のうち、同じ種類のものが二つ以上あるものに限る。なぜなら、今確保している寿司よりも、残りのN-K個の寿司の方が美味しさが小さいため、純粋な一種類・一個の寿司のトレードで満足度を向上させられない（種類ボーナスは増えないし、美味しさが減るだけ）からである。

これを、現状2個以上残っている寿司の美味しさをheapqで持っておき、新たな寿司のネタと交換することで、美味しさを増やせるかどうかを見るだけ。種類が多くなればなるほど満足度が増える訳ではないことに注意。

atcoder.jp

閉路検出。BFSするだけだけどもっとマシなコード（実装法）が知りたい。

n,m = map(int,input().split())
graph = [[] for i in range(n)]
for i in range(m):
    u,v = map(int,input().split())
    graph[u-1].append(v-1)
    graph[v-1].append(u-1)
visited = [0]*n
ans = 0
start = 0
while sum(visited) != n:
    while visited[start] == 1:
        start += 1
    stack = [start]
    flag = True
    while len(stack) != 0:
        t = stack.pop()
        if visited[t] == 0:
            visited[t] = 1
            for j in range(len(graph[t])):
                if visited[graph[t][j]] == 0:
                    if graph[t][j] not in stack:
                        stack.append(graph[t][j])
                    else:
                        flag = False
    if flag:
        ans += 1
print(ans)

atcoder.jp

完全グラフから、nがoddなら[1,n-1]...を、nがevenなら[1,n],[2,n-1]...を除けばいい

は？？？？？

atcoder.jp

縦方向と横方向を一緒くたに考えようとすると混乱するので分解する。

とにかく「ゲーム終了時に盤面上に残っているには、最初にどこに駒があればいいのか？」を考えるため、操作を逆順に遡っていく。

先攻は「範囲を狭めようとする」動きをするのであんまり考えなくていいが、後手が結構ややこしい。
例えば、縦方向に見ていて先手を見終わって範囲が[2,3]だった時に（範囲は1~hとする）、後手が"D"を持ってきたら、後手がDを出して[2,3]の範囲に居られるようにするためには、後手の行動前に駒が[1,2,3]のどこかにいなくちゃいけないな〜みたいに、「後手が行動する前に駒はどこにあるべきか？」を考える。

セグメント木、BIT（反転数）

・セグメント木
書きようによっては任意の区間のGCDを求めたりもできるっぽいけど、とりあえずは任意の区間の最小値を求めることにする。

n = int(input()) #配列の要素数をnと置く。
L = list(map(int,input().split())) #配列
t = 1
while t <= n:
    t *= 2
segtree = [float('inf')]*(t-1) #tはn以上で最小の2のべき乗の数

def init(LIST):
    for i in range(n):
        segtree[i+n-1] = LIST[i] #配列のi番目をセグ木のi+n-1番目（葉）に格納
    for i in range(n-2, -1, -1):
        segtree[i] = min(segtree[2*i+1], segtree[2*i+2])

def update(k, a): #k番目（0-indexed）の値をaに変更
    k += n-1
    segtree[k] = a
    while k > 0:
        k = (k-1)//2
        segtree[k] = min(segtree[2*k+1], segtree[2*k+2])

def query(a, b, k, l, r): #[L[a],L[b])の範囲の最小値を求める。kは今見ている節点の番号、l,rはkの対応している範囲を表す。
#L[a]~L[b]の最小値を求めたければ、query(a,b+1,0,0,n)
    if r <= a or b <= l: #求める場所が範囲外
        return float('inf')
    elif a <= l and r <= b:
        return segtree[k]
    else:
        u = query(a, b, 2*k+1, l, (l+r)//2)
        v = query(a, b, 2*k+2, (l+r)//2, r)
        return min(u, v)
        
init(L)
print(segtree)
while True:
    i,p,q = map(int,input().split()) #i==1でL[p]~L[q]のminを求める。i==2でL[p]をqに変更
    if i == 1:
        print(query(p, q+1, 0, 0, n))
    elif i == 2:
        update(p, q)
        print(segtree)
    else:
        break

実行例

>>8
>>5 3 7 9 6 4 1 2
[1, 3, 1, 3, 7, 4, 1, 5, 3, 7, 9, 6, 4, 1, 2]
>>2 0 2 #L[0]を5から2に変更
[1, 2, 1, 2, 7, 4, 1, 2, 3, 7, 9, 6, 4, 1, 2]
>>1 0 0 #L[0]の値
2
>>1 0 3 #L[0]~L[3]の最小値
2
>>1 0 7 #L[0]~L[7]の最小値
1
>> 1 4 3 #範囲が前後する
inf

・BIT
任意の区間の和を求めることができる嬉しい配列。

n = int(input()) #配列の要素数をnと置く。
L = list(map(int,input().split())) #配列
BIT = [0]*(n+1) #1-indexed
def sum_1_to_i(i): #L[1]~L[i]の和を求める
    ans = 0
    while i > 0:
        ans += BIT[i]
        i -= i & -i #ビットが立っている最下位の桁を0に
    return ans

def update(i, x): #L[i]にxを加算する
    while i <= n:
        BIT[i] += x
        i += i & -i
    return

for i in range(n):
    update(i+1, L[i])
print(BIT)

while True:
    i,p,q = map(int,input().split())
    if i == 1:
        print(sum_1_to_i(q)-sum_1_to_i(p))
    else:
        break

実行例

6 
1 2 3 4 5 6
[0, 1, 3, 3, 10, 5, 11]
>>1 3 6 #4+5+6
15
>>1 2 6 #3+4+5+6
18
>>1 0 3 #1+2+3
6
>>1 0 6
21

・1~nを適当に並べた配列における反転数（バブルソートの回数）を求めるコード
※反転数＝バブルソートの回数なのは、①一回の入れ替えで反転数は-1、②昇順に並んでる時の反転数は0、の二つから従う。

n = int(input()) #配列の要素数をnと置く。
L = list(map(int,input().split())) #配列
BIT = [0]*(n+1) #1-indexed
def sum_1_to_i(i): #L[1]~L[i]の和を求める
    ans = 0
    while i > 0:
        ans += BIT[i]
        i -= i & -i #ビットが立っている最下位の桁を0に
    return ans

def update(i, x): #L[i]にxを加算する
    while i <= n:
        BIT[i] += x
        i += i & -i
    return

times_of_swap = 0

for i in range(n):
    times_of_swap += i-sum_1_to_i(L[i])
    update(L[i], 1)
print(times_of_swap)

参考：
転倒数 - 個人的な競プロメモ

復習 3/30

atcoder.jp

逆元使ってn_C_k（を10**9+7で割った余り）を高速で求める、それはそうみたいな問題なんだけど、流石にテンプレをペタって貼り付けてn=10**5,kを1~10**5まで計算するのはしんどい（factorialの都合上）

n_C_k-1からn_C_nまでを一気に求める問題であれば、以下のような実装でまあなんとかなる。（色々杜撰なのは多めにみてね）
n = 10, k = 3なら、2C0, 3C1,...,9C7まで求めることになる

import math
mod = 10**9+7
n,k = map(int,input().split()) #n_C_kのn,k
a = math.factorial(k-1)%mod
b = math.factorial(k-1)%mod
c = 1
fact = [0]*(n-k+1) <s>#fact[j]は、n_C_(j+k-1)を表す</s>
for i in range(k-1, n):
    if i == k-1:
        fact[0] = (a*pow(b*c, mod-2, mod))%mod
    else:
        a = a*i%mod #前の結果を再利用
        c = c*(i-k+1)%mod #前の結果を再利用
        fact[i-k+1] = (a*pow(b*c, mod-2, mod))%mod

atcoder.jp

i番目の鍵を使うか？でDPを行う。また、dp[i][j]について、iは「i番目までの鍵を見た（使った、使わないは無視）」、jは0から2**n-1までの値を取り、「二進数に直した時にビットが立っているところは、宝箱が空いている」とみなす。

例えば宝箱が3つあり、dp[3][6]であれば、「3番目の鍵まで見て、6→110、つまり箱1,2が空いている状態において、最小のコスト」が入るようにする。

dp[i][j]の遷移についてだが、まずi番目の鍵を使わないのであれば、開く箱はi-1番目の鍵を見た時と変化がないので、dp[i][j] = dp[i-1][j]となる。
i番目の鍵を使うのであれば、

dp[i][j|key[i][1]] = min(dp[i][j|key[i][1]],dp[i][j]+key[i][0]) #j|key[i][1]はor演算子を使っている。dp[i][j]までで開いている箱に、新たに鍵iを使った時に開く箱の状態に遷移した時、その鍵を使った方が最適かどうかを判断している。

という式で遷移が書ける。
最後にdp[m-1][2**n-1]を出力してあげればいい。（全部開けられないかの判断もここでする）
計算量は、鍵1~mを開けるか否かについてと、それについての0~2**n-1通りの箱の開き方があるのでO(m*(2**n))。

atcoder.jp

これ1000人も通してたってマ？

いもす法で前から見ていくのだが、区間全部の累積和を取るのではなく、「爆発の及ぶ範囲」の端と橋をプラス、マイナスしておいて、今見ているところの累積和s[i]がモンスターの体力h[i]以上であれば爆発せずに次へ、小さかったら足りない分だけ爆発させて右端（爆発の及ばないところ）にマイナスし、s[i+1]にs[i]で与えた分だけ増やす、という方式を繰り返す。

例で言えば、例えば爆発の及ぶ距離が左右に2、爆発のダメージを2として、
[1,2,5,9,11]
という位置にいるモンスターが
[10,12,8,14,9]
という体力を持っていたとしよう。

s = [0,0,0,0,0,0]（一つ多く取っておく。s[i]にi番目のモンスターに与える累積ダメージが後々入ることになる）
まず、最初に1にいるモンスターを左端と見て、ここを爆発させると位置2,5のモンスターも巻き添えを食らう。位置1にいるモンスターを倒すには10のダメージ（爆発5回）が必要で、これを表した状態は、
s = [10,0,0,-10,0,0]
となる。

次に進む前にs[1] += s[0] をするので、
s = [10,10,0,-10,0,0]
となる。

次に、距離2にいるモンスターに着目すると、現在与えられているダメージはs[1]=10で、倒しきるのにあとダメージが2（爆発が1）必要である。
ここを左端にして爆発させると、巻き添えを食らうモンスターは位置5のみ。（位置5はもう倒してるけどそれは放っておく）
というわけで、一回爆発させた状態を表現した配列sは、
s = [10,12,0,-12,0,0]
となる。

次に進む前にs[2] += s[1] をするので、
s = [10,12,12,-12,0,0]
となる。

次は距離5にいるモンスターだが、s[2] > h[2] = 8なのでもう爆発させる必要がない。
というわけで次に進むので、s[3] += s[2]をして
s = [10,12,12,0,0,0]
となる。（ここで、s[3]の累積ダメージが0になっていることに着目したい。s[3]を見るまでs[3]に入っていた値は累積ダメージを表現していなかったが、前から累積和をとることによって、s[3]を見る時にはうまく帳尻があう（正確なダメージが入る）事になる）

次に距離9にいるモンスターに注目する。現状、累積ダメージは0なので、7回の爆発（ダメージ14）が必要である。この爆発で、距離11にいるモンスターも巻き添えを食らうので、配列sは
s = [10,12,12,14,0,-14]
となる（配列の要素を一つ余分に取っておいたのがここでうまく作用する）

次に進むので、s[4] += s[3]をして、
s = [10,12,12,14,14,-14]
となる。

最後にs[4]だが、s[4] > h[4] = 9なのでもう爆発の必要はない。よってs[5] += s[4]をして、
s = [10,12,12,14,14,0]
となり、これで全部倒し切って終わり。O(N)で十分間に合う（ぶっちゃけ計算量的には前処理のソートの方が支配的）

復習 3/26, 3/27

atcoder.jp

桁DP的な発想　解説読んでパッと理解できなかった

atcoder.jp

これも桁DP的発想

atcoder.jp

提出した後で「2,8とかの組み合わせの時無理じゃね？」とか気付く。ちゃんと考察をしましょう。

atcoder.jp

グラフの用語を知った。
・直径：一番遠い点間の距離
・二部グラフ：二つのグループに分けられるグラフ。グループAはグループBの頂点としか繋がっておらず、逆も然り。例えば三角形に頂点が並んでいるグラフは二部グラフではないが、四角形に並んでいたら二部グラフ。二部グラフの時、隣接する頂点のグループ番号を偶数、奇数、偶数、奇数……と交互にできる。

atcoder.jp

とにかく桁数がデカけりゃデカいほど強いので、それを目標にしてまずはDPで「マッチ棒ビッタリ使った時に最大何桁作れるか？」を求める。そしてそれが求まったら、dpの最後から遡ってどういう数字を各桁に割り当てればいいかを求める。賢い。

atcoder.jp

結局は高校数学。1<=i<=kのそれぞれのiに対して、(n-k+1_C_i)*(k-1_C_i-1)を求めてあげればいいだけの話。考え方は「最初に赤いボールn-k個を並べて、①その間のi個のどこにボールを入れるか、②その場所に何個のボールを入れるか、の二つをかけたもの」

逆元の求めかたを、例外処理（例えば4C6なんてのは存在しない）も入れて書き直した。

import math
mod = 10**9+7
def comb(p,q):
    if p >= q:
        a = math.factorial(p)%mod
        b = math.factorial(q)%mod
        c = math.factorial(p-q)%mod
        return ((a*pow(b*c, mod-2, mod))%mod)
    else:
        return 0

どうでもいいけどn=10**3くらいだったらpythonの方が早そう

atcoder.jp

二分探索と、「二つの配列の各要素を掛け合わせた時の最大値をできるだけ小さくするにはどう掛けあわせるのが最適？」っていう問題をちゃんと考える。
二分探索で値を見つけるコードを覚えとこう。

n,k = map(int,input().split())
A = list(map(int,input().split()))
F = list(map(int,input().split()))
A.sort()
F.sort()
F.reverse()
t = sum(A)
ok = 10**12
ng = -1
if t <= k:
    print(0)
else:
    while abs(ok-ng) > 1:
        cur = 0
        mid = (ok+ng)//2
        for i in range(n):
            temp = mid/F[i]
            if int(temp) == temp:
                cur += max(0, int(A[i]-temp))
            else:
                if A[i]-temp > 0:
                    cur += int(A[i]-temp)+1
        if cur > k:
            ng = mid
        else:
            ok = mid
    print(ok)

scrapbox.io

（こちらのサイトを参考にさせていただきました。ありがとうございました。）

復習 3/21

atcoder.jp

総和が不変であり、その約数がgcdの候補であることは気づけた。そしてその後に分配するフェーズで余りを横に並べて右側はプラスされる側、左側はマイナスされる側と分けてそれぞれをチェックするところまでは発想できた。
（例）
約数＝5で割った余りが1 1 1 1 2 2 3 4
1 1 1 1 2 2 3 / 4 →4はあと1プラスすればmod5=0、左側は全部4に移すので手数が11かかる
1 1 1 1 2 2 / 3 4 →3,4はそれぞれ2,1プラス（合計3）すればmod5 = 0、左は全部移して手数8、よって合計で手数8
1 1 1 1 2 / 2 3 4 →2,3,4 はそれぞれ3,2,1プラス（合計6)すればmod5 = 0、左は全部2,3,4に移して手数6、よって合計で6
1 1 1 1 / 2 2 3 4 →2,2,3,4は手数9、左を移すのは手数4、実際は左を全部2,4に移してmod5=0にして、あとは2を3に移せばいいので手数は6（だが便宜上9にしておく）
みたいなのを最後までやっていき、手数最小になるものがk以下になるものの中で最も大きい約数を出力

答え見てACしちゃったけど割と嘘書いてそうで心配

復習 3/19,3/20

atcoder.jp

数字が「ある」ところを探すんじゃなくて、「ない」ところを探すという発想の転換。難しい。

atcoder.jp

発想の問題じゃなくて、大きな数字を扱うときは注意しましょうねという話。基本的にpythonは大きな数字はメモリの許す限り扱えるけど、例えば

10**100-10
#9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999990

10**100-9
#9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999991

(10**100-9)//2
#4999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999995(これは誤り)

みたいになる。math.floor()とかもそうだけど、大きな数字は割り算（切り上げ切り捨て）の操作に弱いので要注意。

atcoder.jp

0点の人間を除いて、ソートして溢れなかったらK番目にいる人の点数+1、溢れたら0だってさ　なんじゃこりゃ

復習 3/16,3/17

atcoder.jp

s = 10**100とかいう良く分からん表現に振り回された感がすごい

やることとしては、いっぱいつなげる方(s)に対し、sのi番目(iは0~len(s)-1、つまりsの各文字)の文字に対して、そこから数えてa,b,c....が次に最短でいつ出てくるかを数える（これをやるときは、sを二つ繋げた文字で考えると良い）。これを前処理として表にしておく。

そして、tの前から見ていって、今見ている文字から次の文字まで何文字あるかな？ってのを、さっき作った表を参考にして調べていく。

言われればははぁんってなるけど思いつかへん......

atcoder.jp

作れない数列の条件（最初が0でない、増加するときに+1でない）はわかったんだけど、数が数えられなかった。

単調増加なら+1、そうでないなら+(要素の値)になる。新規で作るのに要素の値だけの手数が必要になるので、ってことだけどこれ気づかね〜〜〜〜
それっぽいことを考えたけど実装できませんでした。答えは案外シンプルなことが多い。

atcoder.jp

自力ACできたけど、結構ちゃんと条件を押さえないといけなくて教育的だなって思ったので復習

数字iを二進数に直すには、自身より小さい2の累乗の数と&（ビット演算）を取るのが早い(e.g. 24と27は二進数に直すと11000と11011なので、11000&11011は両方のbitが立っている桁のみ1になることから24&27=11000&11011=11000=24となる)
あとNが小さいのでO(2**N)が使える

あとは証言を全部舐めてって矛盾が生じた時点でアウトの処理をすればいいけど、矛盾が出るのは、
①証言者が正直（bitが立っている）かつ、言及先が本当は正直者(bitが立っている）なのに「不親切」と言及している
②証言者が正直（bitが立っている）かつ、言及先が本当は不親切(bitが0）なのに「正直者」と言及している
の2パターンしか存在しないので、この二つを確認すれば良い。

復習 3/15

クッソサボってた　しょうがないね

atcoder.jp

s = 'AAA'
s = 'B' + s  #s = 'BAAA'

上の例みたいに、文字列の先頭に新たな文字をくっつけるのは、末尾にくっつけるよりもかなり時間がかかるので注意すべし

atcoder.jp

サイズ付きUF木で一撃　こういうのが普通にできるようにしたい

atcoder.jp

こういう辞書順最小みたいなのは、前回作った奴を再利用するタイプが使える

atcoder.jp

1文字と2文字を扱おうとするからごちゃごちゃになる　2文字を1文字として扱うべし

桁DP

桁DPは、例えば「0以上N以下の数字で、ある条件を満たす数字がいくつあるか」などを数えるのに便利な手法である。

発想が単純なものと、複雑なものの2パターンある。

＜単純な方＞
例えばこの問題↓
atcoder.jp

?はワイルドカード（0~9のいずれでもいい）の時、?5?という形をしている3桁の数字で、13で割って5余るような数字はいくつ存在するかを数える。

上から順に数字を見ていく。まず、「n桁目を見たところまでで、13で割って5余る数字は何通りか？」を管理するために、「n桁目を見たところまでに13で割ってi余る数字」をdp[i]とする配列dpを考える。

例えば?5?であれば、一番左（最初）の桁が?なので、dp = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0]となる。（?には0~9が入るため、ここまでを13で割った結果がdpになる）
次に、真ん中の桁が5になるので、?5を13で割った余りは、dp = [1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1]となる。(例えば、dp[2]について、25を13で割った余りは12になるので、もともとdp[2]にあった1はdp[12]に移る）
最後に、一番右の桁が?なので、dp = [8, 8, 7, 8, 8, 8, 7, 8, 8, 8, 7, 7, 8]となる。dp[5]は、すべての0~12のiについて、(10*i+j) % 13 == 5となるようなj（つまりワイルドカードの?）を試し、その場合の数を加算してあげればいい。

その他の例
atcoder.jp

＜複雑な方＞

例えば「N以下で4の入った数字はいくつありますか？」という問いかけで、N=50であれば、十の位を1~9まで全部見ても、十の位で弾けるから簡単だが、N=1234とかだった場合に、千の位が1だった時に、単純にdpを作ろうと思っても「1100」と「1200」で扱いが変わってきたりする。（前者は十の位がなんでもいいけど、後者だと十の位の動きに制限が出る）

そういうのを管理するために、単純なdpではなく、
dp[今見ている桁][Nよりも明らかに小さいか、同じか][すでに4が登場しているか]
という配列で管理するのが良い。これを用いて遷移を場合分けしていけばいいんだけど、かなり面倒。

atcoder.jp

abc007.contest.atcoder.jp

atcoder.jp