個の石を置くことができる。ここで次の操作を何回か行う。以下番目のマスに石を1つづつ追加する。操作回数ができるだけ多くなるような戦略で行って、最終的にマス目に残った石の数がスコアとなる。ありうる初期状態すべてのスコアの総和をとるといくつになるか。解法(公式Editorialに補足する形式となっています)操作1回によって石の数は1つづつ減るので、(初期状態の石の個数)-(スコア)=(操作回数)となる。操作回数を多くするための最適な戦略は操作可能なマス目の中で最もindexの小さいマス目を選ぶことである(Editorial参照)。全ての初期状態の操作回数の和を求めることができれば、引き算でスコアの総和を求めることができる。ついて後ろからDPを行う。番目の操作回数をそのまま持ち越す。回操作を行うことができる。番目のマス目で操作を即座に行うことができるからである。見えるが、操作の理論的な回数の上限を考えるともっと高速化することができる。この高速化をすると十分間に合う。MancalaDPは想定された計算量で計算可能な状態を定義するところがそもそも難しい。この問題だと前から操作を行う最適な戦略で後ろからDPするので、再帰的な考えに慣れておく必要がありそう。グラフいじり(+参加後記)AtCoder問題ddcc2017-final.contest.atcoder.jp解法コンテスト中の自分の思考を再現してみたので、無駄な(最終的な解法を導くのに有効でない)考察も含まれている可能性がある。考察の正当性の証明はここでは省略する。問題文には1つの辺の長さのみ変更できると書いてあるので、まずは長さを変更する辺を固定して考える。下のグラフの場合で有向辺1→2を選んだ場合、長さを2から-1にすれば全てのサイクルの長さを0にできる(出力はYesになる)。このケースでよく観察すると、2→1の長さは1であり、つまり辺1→2の長さの符号を逆にしたものである辺1→2がないものとみなした場合、残った辺で作られるサイクルは全て長さが0であることがわかる。ここから膨らませると、全てのサイクルの長さを0にするには、2→1に至るあらゆる経路において、長さは1でなくてはならないこともわかる。2→1への経路は一般には1つとか限らず、たくさんある場合もあり、それらが1→2の長さと足して常に0になるはずだからである。与えられるグラフは強連結なので、辺1→2を無視した場合でも、点2を始点とすればそれ以外の全ての辺を訪れることができることがわかる。この考察から、辺1→2を無視した場合にサイクルでなくなるものとサイクルが維持されるものを区別する必要はなく、点2から全ての辺を訪れるようにDFSを行い、点2から全ての点への長さを計算して、2→1の長さの符号を入れ替えたものが1→2の長さとなることがわかる。注意として、全ての点への長さをDFSで計算する際に、点2から全ての点への長さは一意でなければいけない(*)。下のような例は2→1の長さが一意に定まらないのでだめ。これを全ての辺に対してチェックし、1つでも(*)が満たされている辺があれば答えはYesとなる。なり、TLEしてしまう。回)も行なっていることに注目する。上の図だと始点2でDFSを行うのは辺1→2を選ぶ以外に辺4→2を選ぶ場合がある。何とかして無駄を省くことができないか考えると、例えば始点2のDFSの場合、辺1→2と辺4→2両方を無視しても、その他全ての辺を訪れることが可能であることに気づく。TLE解法と同じようにDFSを行うと、2→1の長さと2→4の長さがわかる。それぞれにおいて無視していた辺1→2との和、辺4→2との和をとり、0であるかどうかチェックする。ここでは高々1つまでの点で和が0以外であれば、Yesとなる(0でない場合はそれに対応する辺の長さを変えれば良く、1箇所までしか変えられない)。学生でもないのに新卒採用の一貫として開催されるコンテストの本戦に参加する権利が与えられてしまい、DISCOさんの懐の厚さを感じました。Bを解いた後、終了8分前にCを通し、何とか3完することができました。800点台の問題はAtCoderのレーティングが導入されてからずっと鬼門に感じていて、レーティングが伸び悩む原因になっていますね...。ある程度の精進で何とかなるかもしれない希望もありつつ、実際には精進できていないという現実があります。将棋AIの特別対談のセッションは将棋AIを自分が手がけることはないだろうな...と思いながら聞いていたのですが、興味深く聞かせていただきました。将棋AIを育てていくのにも、例えばインフラ整えたりするところでサーバ貸し出しの交渉など社会性が必要となることもあったのこと。社会性を身につけなければ。オフィス見学は技術の紹介より福利厚生の紹介の方が多く、(競技プログラマーがどういう生き物か)わかってらっしゃるという印象でした。個人的にはウェーハ加工で実際に動作させるソースコードのサンプルが見たかったです。懇親会は普段Twitterや順位表でしか見ない方とお話できたので、満足しています(近場の人とはまた会いたい)。一度会ったことがあるのに挨拶できなかった方すみませんでした。積極的に話に入るべきでした。純粋な競プロ以外のアウトプットもしていきたいところではあります(最近競プロのアウトプットでさえ危ういですが)。PuzzleAtCoder問題agc012.contest.atcoder.jp概要aaはaを2回、bubobuboはbuboを2回繰り返している。このように長さ1以上の文字列を2回繰り返しているものは良い文字列と定義する。