AtCoder Beginner Contest 155

結果

順位   795th / 6812
パフォーマンス   1489
レーティング  1779 → 1753(-26)

　D問題までの4完でレート減。しかしレート下がってもそんなに悲しくならないくらい今は競技プログラミングへのモチベーションが落ちている。コンテストに出ることは継続しているけれど振り返りを一切しないようになっていて、流石にそれではまずそうなのでここらで再開。

A - Poor

　長さ3のstd::vectorに受け取ってソートして上手くできるのかと思って書きかけたが、なんか結局面倒なことになりそうだったので方針転換して条件をベタ書きした。2分以上かかる。

　提出

B - Papers, Please

　問題文が理解できず頭の悪さを感じた。"APPROVED"、"DENIED"をコピペせず手打ちするという勇者プレイ(普通に通った)。

　提出

C - Poll

　std::mapで出現回数を数えてから最大のものだけstd::setに詰め直す。range-based forを使うとき、CLionが指摘に従って律儀にconst auto&にするタイプの人間。

　提出

D - Pairs

　「番目に来る数がである⇔積が以下になるペアが個以上になるような最小の」が正しいのに、最初の方はずっと「番目に来る数がである⇔積が未満になるペアが個未満になるような最大の」をと勘違いしていた。これだと積として存在しないを答えにしようとするのでWAになる。

　まぁそれは些細な話として、この問題は実装をどうするかが要点だったんだろう。自分は最初に「std::upper_boundを使おう！」と心に決めて実装を始めた。

を見ながら比較関数をラムダで書いて与える形式std::upper_bound(begin, end, value, comp)が使えるはずだと確認したところまでは良かったが、ここから罠が多い。まずこのページの「trueとなるすべての要素が、その式がfalseとなるすべての要素よりも前になければなりません」は逆では？ と思ったが、これは!comp(value, element)についての記述なので逆が正しい。ここに気づくのにかなり時間がかかった。またvalueはcompのどっち側の引数に入るかも、上の式を冷静に見れば左側だとわかるんだけど混乱していたので何回も間違えた。混乱していた理由としてはstd::lower_boundだと引数が入る順番が逆になる。

これ本当に難しくて、比較関数を自前で実装するならstd::upper_boundとstd::lower_boundはどっちでも良いんだけど、問題で正と負の場合で2回実装しなければならなくて、それで片方は等号含み、片方は含まないから適切な方を使わなければ？ とか思うと適切な方ってどっちだとみたいな感じになり脳が爆発する。

　時間はかかってパフォーマンスは崩壊したけど、なんとか最終的にはそこそこ綺麗には書けた気がするので満足感はある。最近はコンテスト中もわりと綺麗なコードを書きたいという気持ちが強くなってきた。using ll = int64_tすら外しているのもその一環で、タイピング速度はやや落ちている気はするので損はあるんだけど、気持ちの問題。

　提出

E - Payment

　D問題でさんざん混乱した頭ではこれを30分で処理することなんてできない。桁ごとに見ていって繰り下がりを考慮しながらどうにかこうにかするんだろうということはわかるが、それを適切に実装するのは一日明けて今日実装していても大変だった。桁DPだという気持ちを持っていた方が楽だったのかな。まぁ難しいです。

　提出

　F問題は解説PDFを読んでもはぁという感じだったのでまた後日。

ここ2ヶ月の進捗

　論文を書いているのもあってある程度情報を隠しながらやっていかないといけないかなと思っていた部分もあったのだけど、やはり性に合わない感じがしてきたので書きたいように書こうという方針で。正直なところ論文も公開しながら書きたいくらい……。

　まずは前回からの変更点を(オセロへの対応を追加した以外のものについて)振り返ってみる。

対戦相手の変更

　今まで基本的に技巧2をレート測定の対戦相手に使っていたが、不具合が出てきたので替えることにした。不具合というのは技巧2が探索中にセグメンテーション違反で落ちることで、今までは上手くいっていたのだが新規に技巧2のリポジトリからクローンしてコンパイルすると失敗してしまう(Ubuntu18.04/g++7.4.0)。いくらかコミットを戻ってコンパイルしてみたりもしたが上手くいかなかった。今まで正常に動いていたバイナリは今も動くのだが、どうやってコンパイルしたものか覚えておらず、再現性が確保できない。

　仕方ないので対戦相手をやねうら王/Kristallweizenに変更した。今度はちゃんと手順を忘れないようにダウンロードスクリプトを書いた。本当はgit submoduleで管理した方が良いのかもしれないが、ちょっと使い方がよくわからなかったので妥協中。あとはGPLソフトをsubmoduleとして取り込むとMiacis自体もライセンスをGPLにしなければならないかもしれないと思ったのもある。レート測定で用いるのはセーフな気がしているが、ちゃんと規約を確認しているわけではない。

　Ubuntuで利用可能な最強ソフトがなんなのかわかっていないが、論文で引用する可能性があることも考えるとWCSC優勝・準優勝などの箔が付いているソフトを使っている方が良いかなと思ったのでやねうら王/Kristallweizenにしている。探索エンジン側のdolphineなるものはUbuntuで使えるのだろうか……？ そのあたりの事情に疎い将棋ソフト開発者である。

ネットワークの巨大化

　とりあえず手っ取り早く強くする手法としてネットワークを巨大化した。残差ブロック中におけるチャンネル数を64→128に変更して、それに伴って棋譜生成および対局時の推論計算を半精度浮動小数点演算で行うことにした。

　以前fp16を検証したとき

は学習もfp16でやろうとしていたので上手くいかず諦めていたが、対局時のみfp16にすれば性能低下はなかった。これにより生成速度は1.7倍ほど(正確な数字は取っていないがだいたいこれくらい)になったのでこれも多少性能向上に繋がったと思われる。

対局結果

　というわけで128chで学習したものをやねうら王/Kristallweizenと対局させた。やねうら王/Kristallweizenは強いので1Threadかつ一手0.1秒にして、それに対してMiacisは一手0.5秒でようやく互角くらいになる。2Mステップまで学習させていった結果が次のような感じ(縦軸はやねうら王/Kristallweizenに対する相対Eloレート)。

　今までの64chだとまさに丁度互角くらいだったので、128chにしてレートが+80くらいは伸びたと思われる。学習率の制御とかをちゃんとすればもう少し伸びそうな気はしているが、だいたいこれの学習に2080ti×2枚のマシンで2週間かかるのでそうそうたくさん試せるわけではない。

　このくらいの秒数だと技巧2の方が強いらしい？ みたいな話もある

depth12くらいだと0.1秒オーダーかな。試すと分かりますがこのレンジだと技巧２が未だに最強ですよ。 #昨年のゲーム情報学研究会でもざっと話した

— 48 (@bleu48) 2020年1月22日

ので、できれば技巧2も使えるようにしたいのだが、セグメンテーション違反になる原因を探ってみた感じだと合法手生成でコケている感じでよくわからなかった。Ubuntu18.04/g++7.4.0で上手くできる方法を知っている方がいれば教えていただければ……。

近況

1行まとめ

　去年のWCSCで使った手法(AlphaZero+分布型強化学習)についての論文を出そうと奮闘していたのですがちょっと挫折しかかっているという感じです。

長い

　現在はジャーナルに投稿してレビューが返ってきた段階です。レビューの指摘に従って改稿作業や追加実験を行っていたのですが、追加実験で論文の主張と合わない結果が出てき始めていて頭を抱えています。

　もう少し詳しく言うと、論文ではゲームドメインによらず性能が上げられる手法であるとアピールするために将棋だけでなくオセロでも実験を行っていまして、そっちでの提案手法の効果が今一つといった感じなんですね。

　1回目投稿版では超小規模ネットワークでの結果を使っていたのですが、比較対象が弱いと指摘されたのもあってMaicisにオセロ対応を追加する形で完全に実装し直して実験しました。提案手法フルではやや性能が上がっているんですが、切除実験をしてみると一番主張したいところがほぼ効果なく、一番どうでもいいところが一番効果があるという感じで……。

　将棋の方で切除実験をやればもっと顕著な差が出そうな感じはあるんですが、将棋では1回の学習・評価に2,3週間かかるので実験をたくさんやるのはしんどいんですよね。やっぱり計算資源がそんなにあるわけじゃないのに本将棋で実験しているのが良くないなぁと改めて反省しています。

　再投稿の締め切りが迫ったプレッシャーもあってかここ数日心身の調子が悪くなっていて、ちょっと再投稿は無理そうかなという見通しになっています。まぁ再投稿締め切りに間に合わなかった場合でも新規投稿として扱われるだけなので、そんなにデメリットがあるわけでもないのかなとは思うわけですが。実験結果をちゃんと解釈すると論旨がやや変わりそうな気配もあるので新規投稿の方がむしろ相応しいのかもしれないとも思いつつ。

　あとはそもそもレビューの指摘でもあったんですが、「トップソフトと差が大きすぎる低レベルなところで手法の有効性を示してもどうなのか」みたいなところは自分としても感じるところであり、もう少しプログラム自体の性能を上げないとなーと思います。しかしここ数カ月は基本的にオセロの方ばかりいじっていたので将棋側の性能は上がっているわけではなく……。

　根本的に論文を書くことが全く好きではないことがわかり始めていてつらいですね。論文書きたくない。プログラムを書きたい。そんな感じですね。

学習の再現性確認

　最近はあまり新しい工夫を実装する時間がなく、とりあえず今の時点での学習に再現性があるかどうかを確認していた。

　現状使えるマシンは、2080tiを2枚搭載しているものが1台、1080を2枚搭載しているものが2台となっている。実装上の都合によりマシン間でのデータのやりとりはできないので、これら3台をそれぞれ独立に学習させることしかできない。個人的にデスクトップマシン1台で学習できることを目標としているので、クラスタ化学習はあまり進んで実装する気になれないという事情もある。

　これら3台でそれぞれ別にランダム初期化したパラメータから学習を初めて同じような結果になるかを確認した。2080tiと1080では速度が大きく違うが、スリープ時間を調整して1ステップあたりに生成する量を揃えることで、1080搭載マシンでも時間はかかるが同じ条件で実験できるようにした。

実験結果

学習時間

　学習にかかった時間は2080tiのマシンが344時間(≒2週間)、1080のマシンが487時間、526時間(≒3週間)となった。2080tiと1080では本来もっと差があってしかるべきだが、そうなっていないのは実装上の問題でGPU利用率が100%になっていないからである。

Validation損失

　floodgate2015年の棋譜からレート2800以上のソフト同士のものだけを抽出し、各局面について指し手と最終結果に対して損失を計算した。

左:Policy損失　右:Value損失

　どれでも損失としては大差なく、再現性がある結果だと言える。

　本題とはずれるが、1.5Mステップ経過時点で学習率を1/10にすることを試したところ、そこで損失が大きく落ちるよく知られた現象が起きた。1.75Mステップ経過時点でも学習率を1/10にしたのだが、そちらの効果はよくわからない。

対局結果

　1手0.25秒で技巧2(深さ10)と500局対局を行った。技巧2(深さ10)はuuunuuun氏のサイトによるとレート2808であり、それに対する相対Eloレートを示す。

　どの学習でもほぼ技巧2(深さ10)と互角という結果になった。やはり再現性はある結果だと言える。

　また性能面でも1.5Mステップにおける学習率の調整は効果があるようだ。

まとめ

　とりあえず1手0.25秒でレート2800は安定的に出せることがわかった。1080マシンでも同じような結果が出ることが確認できたので、これらを使って上手く実験を進めていきたい。

余談

　現状は諸事情により将棋だけでなくオセロでも検証できるように実装を進めている(multi_gameブランチ)。

　できるだけ汎用的になるように実装したのでPositionクラスなどを適切に加えればたいていの二人零和有限確定完全情報ゲームには対応できそうだと期待しているが、どこまで上手くできているかはわからない。いずれは囲碁なども実装してみたい。

MuZeroと脳内盤

　技術的な内容というよりはやや曖昧な、（この言い方は好きではないが）ポエムっぽい文章を書いてみるなど。

　今年の選手権でmerom氏には話した気がするのだけど、プログラム内部に盤面を保持してそれを遷移させて評価関数に入力するという方式は、継ぎ盤を用いて思考しているようなものなのではないかと感じることもある。盤面の遷移則自体も学習できるならそうして欲しいし、その学習が価値判断や指し手の学習に良い効果をもたらす可能性もあるとは思っていた。

　MuZeroの手法は表現ベクトルにおいて遷移を考えるという手法の一つとして見なすことができ、これは個人的な解釈で言えばまさに脳内盤を遷移させているようなものだと感じられる。一方で明示的には「遷移予測した表現ベクトル」と「遷移先の盤面をエンコードした表現ベクトル」が近くなるような損失はないので、価値や方策は似た値を出力するが表現ベクトルとしては違うものになっている可能性は高いと思われる。

　手元の実験(教師あり学習)では、「遷移予測した表現ベクトル」と「遷移先の盤面をエンコードした表現ベクトル」の二乗誤差を損失に含めるなどとしない限り、両者の各要素についての平均二乗誤差が5くらいは残り続けるような結果が得られている。二乗誤差を損失に含めれば二乗誤差は0.005ほどまで落ちるが、これは表現ベクトル全体が単純に小さくなるためでもあることがわかっている。

　個人的にはやはり「遷移予測した表現ベクトル」と「遷移先をエンコードした表現ベクトル」はできるだけ一致する方が良いのではないかと思われる。ルール的に同じ盤面であることが理屈としてわかっていることが担保できれば嬉しい。そのためには連続的な表現ベクトルではなくて、離散化などの処理が必要なのかもしれないとも考えたりはするが、試したみたことはない。

　また自分は盤面の再構成誤差を損失に含めるブランチも作ってみていて、少なくとも盤面を直接エンコードした表現ベクトルから盤面を再構成することはかなりの精度（99%以上)で可能であることがわかっている。しかし遷移予測した表現ベクトルからの再構成では確か70%程度まで落ちてしまい、特に持ち駒の数を誤解するケースが多かったと記憶している。盤面の認識は怪しいのに価値判断はそれなりに可能というはやや妙だなという印象を受けた。はっきりとしたデータがどこにあるかわからなくなっているので曖昧な話ではあるが……。

　遷移則を学習することが性能向上に結びつくかは微妙なところではあるけれど、学習の高速化に少しでも寄与する可能性はあるのではないかと期待している面もある。MuZeroではあまりそのような傾向は見られていないようだが、なにかうまいやり方があればなぁとは思うところ。

三井住友信託銀行プログラミングコンテスト2019

結果

順位    323rd / 3912
パフォーマンス  1901
レーティング    1835 → 1842(+7)

　全完早解きセットだったので3WAを出すようではそれほど良い順位にならない。

A - November 30

　で判定。出力のYes/Noが1/0だと判定をそのまま出せば良いので楽なんだな。

　提出

B - Tax Rate

　†全探索†

　提出

C - 100 to 105

　なんかちょっと手を止めて考えたら最小での個数が100で割った値で、個数×105までは自由に選べそうなのでそんな感じのを（無証明で）書いた。実際に方針として選ぶかどうかは別の問題として、DPがさっぱり思い浮かばないの自分でも呆れるな。

　提出

D - Lucky PIN

　各場所について、自分より左に出現している文字の集合と、自分より右に出現している文字の集合をあらかじめ構築しておいて、あとはループして実際に構築して答えの集合に突っ込んでいってサイズを出力。ちょっと計算量重いかなと思ったけど、解説PDFを見るにもっと重い解法でも大丈夫っぽいのでそういうのに救われた。

　提出

E - Colorful Hats 2

　最後答えにをかけるという思考にとらわれ、の時だけ特別扱いをするという意味不明なことをして1WA。美しくない処理を平気で提出してしまうのひどいなぁ。

　提出

F - Interval Running

　とりあえず適切にスワップして、秒後に多く移動している方をとして固定して考えたくなる。そうするとなら交わることがなく、の場合にのみからまででで1回、からでもう1回交わる可能性があって、それは距離の差がある値になるまで続く。よってその限界値を2分探索すればOK、と思ったのだが、最後にちょうど時刻で1回交わる場合に対処できてなくて2WA。

　よく考えればこれは二分探索をする意味がない。普通に割り算で求められることを無駄にやって混乱してWA出して、ということになっている。冷静さがない。

　さらに言えば解説PDFを見ると出会う場所がint64_tを超える場合があるらしく、全然注意してなかった。なんとなく差分っぽい感じで計算したのでそれは回避できていたようだが、運が良かっただけ。

　提出

AtCoder Beginner Contest 146

結果

順位    359th / 5026
パフォーマンス  1799
レーティング    1839 → 1835(-4)

　E問題以外の5完。しかし、うーん、E問題解けないようではひどい。レート下がるのもしょうがない。

　前回ドハマりした反省として、今回は順位表を常に眺めながら参加した。ある問題について何人解けているかという情報は大きく、それである程度の難易度を察することができる。それが問題を解く力を付ける上で良いのかどうかは判断がつかないが、最近はちょっとまたレート最大化に拘りたいという気持ちになってきたのでこうすることに。今回はそれが結構大きく、F問題が簡単であることが読み取れたのでそっちに先に取り組んだおかげで大失敗を免れた。

A - Can't Wait for Holiday

　流石にこれは曜日名をコピペしたが、コピペしても結局何を求めるのかでやや混乱した。strs.end() - find(strs.begin(), strs.end(), S)と書けることが思い浮かんだので満足。

　提出

B - ROT N

　最初は全部小文字かと思ってそう処理するプログラムを書いたら意味不明な文字列が表れて混乱した。なので無駄なキャストが挟まってしまった。不満。

　提出

C - Buy an Integer

　C問題で二分探索を求めるのはやや難しめ？ 桁数を求める部分とかがきれいに書けなくてやや不満。

　提出

D - Coloring Edges on Tree

　解法自体は簡単にわかるけどどうやって実装するかに少し迷う。最終的に辺にインデックス持たせてそこに書き込んでいく感じの実装にして、まぁそんなに悪くなかったかな。

　提出

E - Rem of Sum is Num

　F問題を解いてからこっちに取り組んで、累積和についてとなり、かつとなるこのを数え上げれば良いというところまで気づいたのにそこからどうやればいいのかがわからなくて解き切れなかった。std::mapを自然に使うだけで良いじゃん。なんでこれが思い浮かばないのか。錆びつきすぎている。

　類問がパッと思い浮かばないのも全然練習していないことの証左。とにかく練習が足りない。

　提出

F - Sugoroku

　妙に解いた人が多いので先にこっちに取り組んだ。そういうのもあってどうせ単純な解法なんだろうと決めてかかる。まず適当にダイクストラ法書いて提出してTLE。さすがにそれはわかれよ。適当すぎる。ちょっと考えて後ろから貪欲で良さそうと思ったのでそれを書いて勝ち。これが間に合う理由もまともに考えてなかったけど、戻らないならはなるほど、そうか。

　提出

DISCO presents ディスカバリーチャンネル コードコンテスト2020 予選

結果

順位   1517th / 3050
パフォーマンス   978
レーティング  1904 → 1839(-65)

　A,B,Cの3完遅解きで大失敗。パフォーマンス3桁なんていつぶりだ？ と思ったけど成績表見てみたら2019/03/23のAGC032でもやらかしているので定期的に発生するものなんだろう。

A - DDCC Finals

　場合分けがやや複雑でいつものA問題と様子が違うぞと思ったけどこれはARC相当なんだったっけ。そうか。

　提出

B - Iron Bar Cutting

　減らす方の操作が区間の量に依存するので扱いにくいなと思ったが膨張だけで良さそうなので。

　提出

C - Strawberry Cakes

　ここで4WAかつ通したのが1時間20分経過時点とドハマりした。最初は行ごとに適当に区切っていけばいいだろと考えていたんだけどサンプル3を見て手が止まり、二次元累積和でイチゴの個数が1となるような最大長方形を埋めていく感じかなーという方向に行ってしまったのが間違いだった。せめて二次元累積和でも解けるなら良かったがなんかWAがなくならずどうにもならないと1時間経ったくらいで再度方針転換をすることに。落ち着いて考えればイチゴがない行は上か下の行と全く同じようにすればいいだけのことなんだが、それに一発で気づけないと厳しい。

　提出

D - Digit Sum Replace

　残り20分くらいだったので、願望も込めて「これは各桁の和とか桁の数だけから求まるだろう」と思って解法を考えたが届かず。勘ではあったけどそういう方針で間違ってはなかったのね。9じゃなくて10で割った答えなら提出していたりしたんだが、そんな当てずっぽうではやはりダメ。

　提出

E - Majority of Balls

　今朝朝食を食べながら考えていて、回でできるところまでは到達したけどそこで諦めて解説を見た。そうか、最初に切り替わる部分を見つけるのはでできるから回で大丈夫なのか。それが回数制限を満たしているということにすら気づいていなかったのでインタラクティブ慣れしていないのが明らか。練習が足りない。

　提出

MuZeroを読んだ感想

　自分用にメモを書くなら「自分の研究テーマとほぼ同じ。差分は表現ベクトルの一致具合を損失に入れるかどうかくらい」で終わり。それくらい本当にもろ被りしている。そこまで突飛なアイデアではないので当然と言えば当然でもあるが。

　Miacisのrepresentationブランチを少し（もしかしたら一行）いじれば将棋については再現実装ができそう。少なくともFloodgateの棋譜を使った教師あり学習はできていて、手元でも真のシミュレータを用いた探索よりやや弱いくらいの結果にはなっている。

　このターン学習というのがMuZeroでは3章の冒頭で記述されている学習するステップ数。論文中ではとして実験していたようで、学習時間の兼ね合いとかも考えてまぁそれくらいがちょうど良いかなという感覚も一致する。

　そこまでデータが多くもない教師あり学習でこの程度の性能が出るのだから、強化学習を真剣に回せば真のシミュレータに遜色ないくらい強くなるという結果も不思議ではない。Figure 3(A)で20秒を超えるとたしかに真のシミュレータに負け始めるようだけど、そこまではむしろ真のシミュレータより強いわけで、そんなに上手くいくのかと感嘆するばかり。（本題からは外れるが真のシミュレータを使った場合のグラフも興味深く、思考時間の伸びによるレートの上昇がMiacisより高いように見える。やっぱり今のMiacisの探索部はどこかおかしいのかなぁという気にもなった。）

　遷移部分のアーキテクチャはエンコーダ部分と同じ（4章Resultの2段落目）って残差ブロック16個ということか、それは大きいなぁとは思った。「遷移が小さいネットワークで実現できれば高速化に繋がる」というのが最初このテーマをやろうと思ったきっかけだったので、そこに巨大ネットワークが必要ならあまり高速化という嬉しさはないか。

　実験結果については本当に想定通りという感じで、Atariゲームでも（かなり穏やかではあるが）探索した方が性能が上がるという結果になっているし、すごいなぁという感じ。

　まぁなんというかAlphaZeroの進化方向としては自然なものだと思うし、それを本家の人たちがきっちりやったというのは良いことなのではないか。自分の研究テーマが潰れたのは痛いが、こういうリスクがあると認識しつつ選んだことではあるので。

　この研究を手法として素朴に発展させるなら遷移部分の確率化とかによって不完全情報性とか不確定性へ対処していく方向になるのかなと思うが、やや自分の興味から外れる感じもあるので自分からそれに手を付けることはないかもしれない。結局MuZeroが将棋でSOTAを更新したわけではないし、MuZero Reanalyzeでサンプル効率は上がるらしいが実学習時間はやっぱり大きいままだろうし、少ない計算資源でもなんとかやっていく方向でとりあえずは考えたい。

AtCoder Beginner Contest 145

結果

順位   297th / 5299
パフォーマンス   1889
レーティング  1906 → 1904(-2)

　まぁこんなもんだろうという成績。しかしとうとうmorio__氏にぶち抜かれてしまったので、時間は流れているなぁという感じ。

A - Circle

　素直。

　提出

B - Echo

　普通に番目と番目を比較していった。substr使うのは思い浮かばなかった。

　提出

C - Average Length

　賢くやる方法がありそうだとは思いつつ、制約が愚直にやっていいよと言ってくれているのでそのままやった。next_permutationを使うのが久しぶりで不安になりながらの実装だったけど、基本的にdo{}while();を使うのってここしかないしな。解説PDFの解法2はいやなるほどですね。

　提出

D - Knight

　ちょろっと図を描いてみたらパスカルの三角形が出てくるのでコンビネーションのライブラリを持ってきて終了。

　提出

E - All-you-can-eat

　最初は「一番最後に食べる料理を全探索」という方針で考えていたが、やっぱりここで取られるのがつらいので考え直してみると、美味しさが最大の料理は絶対採用して良いのだなということに気づく。採用する場合、末尾かそうでないかの二通りだが、末尾じゃない場合は先頭に置けば良く、そうするとその最大料理を食べた状態で同じ問題を解くことになるのでこれでほぼ解法が見える。美味しさでソートしておいて、大きい順に末尾or先頭に置いていけば良い。末尾に置く場合は直前までの料理で時間ギリギリになる最大の美味しさをDPで求めておけば良いので。2番目以降を末尾に置く場合もこのDPテーブルが使いまわせるのすごいなぁと思った。綺麗な問題だ。

　解説PDFの解法1（前後で2つDPテーブルを作る）のは思い浮かばなかった。解法2が自分のやつと一緒……ってあれ、所要時間の方でソートするのか？ ん、でも美味しさ最大は絶対採用も間違ってはないよな。ほぼどちらでも大丈夫なのか。ふーん？

　提出

F - Laminate

　の場合の数え方すら全然わかってなくてさっぱりダメでしたね。そこが見えたとしてもDPに帰着して、、高速化すればですか。こういうの全然できないなぁ。

　提出