AtCoder Beginner Contest 206 反省
4連続で温まっていたが今回は冷えた。単独writer回なので仕方ない（？）
典型90を今週は30問近く解いてコンテスト練習をしなかったのだが、実装のミスは少なかったが直観が鈍っていたような感じだった
結果を鑑みて
1500(1) 64:47
405位となった。Dで手こずり、Eで手こずり、Fは解けなかった。
来週月曜まではやや忙しいことがあってまたスランプの入り口に立っているのではないかと危惧している
A - Maxi-Buying
100倍しておけばmath.floor()を使わないでも解ける。
解けるがこわいのでちゃんと境界値は試した。
B - Savings
パッと見て思いついたのが二分探索だったので二分探索した。
コードを書いている途中で全探索が可能なことに気付いた。大してかかる時間は変わらないのでOK
C - Swappable
同じ数をまとめておく余事象的数え上げで良い。
解いて出したあたりで順位表を見た。100位を切っており、良いスピードだった。ここまでは......
D - KAIBUNsyo
貪慾法かなと思っていた。dpするには制約がきつすぎる。
端から順に見ていって数字を入れ替えるなら常に２択だし、選び方によっては手数がかかりすぎたりする。寄与を考えるとか後から保証するやつは難しそう。
困りまくって端から貪欲書こうとして、数字の書き換えの管理をUnionFindでやるとうまくいくことに気付き、UnionFind使うんだったらひょっとしたら連結成分分解がキーで、貪欲は関係なくUnionFindだけで解けるのではないかと直感した。
結局、何も証明していないがUFを投げたら通った。メタ読みに救われた。
ここで時間をかけまくって700位くらいになった たまげた......
E - Divide Both
題意を理解しようとしてみると、互いに素でないx, yのペア(x, y)であってどちらももう一方の約数ではないものを数え上げよという問題であることがわかる。ここまではすぐわかったが、そこから難航した。
余事象を用いて問題を切り分けると、計算量は以下のようになることが予想できた。
全体ペア集合のサイズ計算 O(1)
一方がもう一方の約数であるような(x, y)の個数 O*1
互いに素なペアの個数 O(?)
互いに素なペアの個数を求められればよくて、これはいかにも典型問題っぽいので number of coprime pairs みたいな文言でぐぐるとhttps://codeforces.com/blog/entry/65229…がみつかった。
メビウス関数で区間coprime pairsを計算するのは初めてだったのでバグらせたが、なんとか通すことができた。
この時点で350位くらいだった。
F - Interval Game 2
制約はヒントだったのだが、制約から連想したのは掃き出し法だった。そこから、区間というアイデアを捨ててグラフにする方向で進んだ結果、解くことはできなかった。grundy数を絡めれば Green Hackenbush に似た感じになることに気付いてどうにかならんかと考えていた（木ではないのでより難しいバージョンになる）
ワーシャルフロイド嘘解法を書いて出したが、当然WA
そのままコンテストは終わった。
総括
検索ムーブは結構よくなってきている。しかし今回は直観がうまく働かなかった。素因数・約数系の包除が苦手気味なのが今回のコンテストに響いた部分もあった。
典型90やるのもいいがコンディションの確認・向上のためにもコンテスト練習はしたほうがよさそう。
*1:R-L)log(R-L
AtCoder Beginner Contest 205 反省
今回はコンテスト前まで体調が終わっていて、ウォームアップの問題を解いていなかった。前回の分は書いていないが、黄パフォだった。内容について軽く触れると、ABCDFの5完で、順位表から得た情報でDとFを通して何とか冷えずに済んだ感じだった。ほぼまぐれ。
結果を鑑みて
1600(1) 85:54
239位となった。EとFは何となく解けるオーラがあったので両方同時に考えていた結果、Fだけ通してしかも時間がかかったという結果になった。とはいえ立ち回りはマシになってきていると思う。
A - kcal
writerにサーバルがいるので誤差問題かと勘繰ってしまった。関係なかった。
B - Permutation Check
len(set(a))を見るだけで良いことがすぐにわかるが、2重ループを許す制約なので少し不安になった。通りはした。
この時点で順位表を見た。100~200位くらいだったと思う。
C - POW
どちらもC乗なのでAとBだけ見ればいいだろと思ったが、よく見るとA, Bが負の数も許容されている。Cが奇数かどうかで場合分けをした。一応、A=0のときとかがコーナーになっていないだろうかとチェックしていた。まあ指数関数なので問題ない。
この時点でも100~200位くらいだったと思う。いいペースで解けていた。
D - Kth Excluded
答えの二分探索を考えてあげると、その値が何番目になるのかはさらに二分探索でわかる。最近解いたARCの問題で、ある数についてのある計算値から数が昇順何番目になるかが推測できるという問題があった。これを思い出したおかげで解法がわかった。
出してからジャッジの進みがやけに遅いことに気付いたが、TL3secだったので通った。このとき、実行時間制限が3secだったことを把握していなかった。今回は通ったが、場合によっては定数倍高速化が必要になった可能性もあるので気をつけよう。
この時点で50位くらいだった。安心して次に進めた。
E - White and Black Balls
インラインDPっぽいなあと思いつつも遷移がよくわからず、よく考えないままFを見に行ったらめちゃくちゃ二部マッチングっぽいので投げてみたが何だか通らず、EとFは同時進行で考えていた。
残り30分くらいになってやっとカタラン数との明確な関係性に気付けたが、対称位置のアイデアを思いつかず、解けなかった。単純な幾何で対称位置をとるのはよくやる操作だが数え上げでやることになるとは......
F - Grid and Tokens
見てすぐ最大二部マッチングだと思ってmaxflowを投げたが通らず、残り20分までうんうん唸りながらEとFを同時進行していた。
通らなかった理由は行へのコマの割り当てと列へのコマの割り当てを別々にやっていたから。この場合、行への割り当てで用いなかったはずのコマを列に割り当てたりすることができてしまう。解決案としてこの2回のフローを重ねていっぺんにやる構造を考えていた。最終的に残り20分くらいで行とコマと列のサンドイッチみたいにすればいいことに気付けた。サンプルのおかげでコマの頂点は倍にしなければならないことにも気付けた。（このくらいは自分で気付こう！）
総括
Dまで解いてE捨ててFに行ったムーブは悪くなかったが、通らなかった時にどちらも捨てきれずにどっちつかずな進行をしたのはよくなかった。今回はEもFも解けそうな問題に見えたことがこのどっちつかずムーブの原因でもあるが、効率の良くないムーブなので考えものである。精神が安定しているときはこのムーブを取っても良いが、今回の後半のようにやや焦りを感じながら2つ以上の問題を考えるのは若干無駄なので自分の状態に応じてさっさと切るかどうするか決めたほうが良いのかもしれない。
AtCoder Beginner Contest 203 反省
今のところそこまで調子は悪くない。忙しくなる前に黄色に戻れるといいが。今回は開始1時間前から緑水青の3問を解いていた。開始5分程度での体感時間は実際の2倍程度だった。良い時は5倍くらいになることはあるが、比較的良い集中ができていたと思う。
結果を鑑みて
2100(1) 84:46
93位となった。遅めの全完という感じだが、パフォーマンス2400だった。全体的に考察よりも実装が足を引っ張った印象だった。
A - Chinchirorin
if文で列挙した。xorでできると言われてびっくりした。確かにそうだ。
B - AtCoder Condominium
全列挙して実際にintとみなして総和を取る方法と数学をする方法がある。いつもであれば全列挙を選ぶが、今回は数学する方を真っ先に選んだためO(1)で解くことになった。この問題にはコーナーケースらしいものは感じられなかったので、サンプルを合わせるとすぐに提出することができた。
C - Friends and Travel costs
流し読みすると最短経路問題かなあという気分になるが、よくみるとシミュレーションするだけっぽいので普通に組んで提出。実装の問題だが、わずかにミスしやすいポイントを作ってしまった。提出前に気付いたので良かったが、できるだけ場合分けの多い実装は避けるよう日頃から心がけるべきだろう。
この辺りで順位表を見ると、200位未満であった。悪くないスピードなので焦らず進むことができた。
D - Pond
難儀した。3分くらい考え、トイレに行ったら解法がわかった。解法を二分探索と決め打たないとなかなか気付けない問題だった。Median of Medians を解いていれば典型と言えるかもしれないが、その上で二次元累積和を要求するのは400点にしては難しすぎではないかと思う。
判定関数で「何を判定させれば良いか」正確には不等号の向きなどで詰まって時間を使った。サンプルがいくらやっても合わず、焦って順位表を確認したりもした。この行動は結果的には良かった（みんなも事故っていたので安心できた）が、基本的には焦燥を加速させるだけなので好ましくない。
実のところサンプルの合わない本当の原因は二次元累積和の添字ミスだった。累積和配列になぜか単調性がないことに気付いて直すことができたが、この問題には30分近く費やしてしまった。
二次元累積和はスニペットにして良いかもしれない。
E - White Pawn
ソートしてごちゃごちゃやるとかデータ構造とか色々解法のとっかかりはあったが、最初にインラインdpの方針を取ることにした。これはおそらく、問題を見てすぐにたどり着ける点は多くてM+1程度しかないということに気付けたため。
Counterでdpを書き、dpの更新はキューにためておいて一括更新する形をとった。詰まったのは、Xが縦、Yが横だったこと。チェスのマスの読み方は(縦, 横)なのかもしれないが、それなら(Y, X)にしてほしい。これのせいで2~5分は溶けている。条件はよく確認しよう。
そんなこんなで20分ほどかけてAC。順位は100位ちょっとだったので余裕を持って先に進むことができた。
F - Weed
まず、解けそうなオーラを感じ取った。時々、コンテスト中に問題文から解けそうな雰囲気を感じとることがある。そういう時、大概解ける。とはいえ今回解けたのはたまたま気付きが連鎖しただけだったが。
まず、ソートして高い草から除いておくべきではないかという気になった。よく考えると低い草を除くのも寄与が大きい場合がありそうだった。状況に応じて真ん中も...... と考えると、貪欲の線は薄い。
二分探索で高橋くんの操作回数をまず決定することを考えた。「後から保障する」アイデアでうまくいく気がした。判定関数を考えていると、二分探索する必要性がわからなくなった。
次にdpを考えた。一次元で済まそうとしたが無理だったのでN*Kのdpを書いていた時、そういえば高橋くんの操作回数は少なく済みそうだということに気付いた。思い出しただけかもしれないが。そこで思い切って 持つ状態と、求めたい値の立場を逆転 させて解くことができた。
dpの遷移を決める際の二分探索パートで上界の設定をミスってて1ペナした。すぐ気付いて再提出した。大して順位は変わっていない。
総括
冷静に問題を解くことができていたと思う。ただ、今回は偶然に愛された部分が多く、立ち回り、実装上の注意など課題が残る。
とりあえずまあ1900には戻れたようでよかった。
エイシングプログラミングコンテスト2021（AtCoder Beginner Contest 202） 反省
久しぶりにまた書いている。ゴールデンウィークから先週末くらいまでひどいスランプに陥っていて半月で150近くレートを溶かしてしまった。
結果を鑑みて
1500 43:21
Eで時間をかけすぎてしまったようだ。とはいえ2100ほどのパフォーマンスなのでレートは上がる。スランプは脱せていると良いが。
A - Three Dice
21から引けば良い。やるだけ。
B - 180°
反転するとどう見えるのか書いてあるので、その通りにやる。うっかり変換のし忘れがないかちょっとヒヤヒヤしていた。
C - Made Up
読んでもよくわからない感じだったが、C_jに注目してみるとテーブルにまとめてしまえばいいような気がした。この解法で正解なのだが、いかんせん問題文がよくわからなくて雰囲気で実装した。サンプルは合っていたので出した。
ここで順位表を見る。300位くらいなのでそこまで早いわけではなかったが置いてけぼりにされているわけでもないので特に心持ちの変化はなかった。ただ、自分としては結構すいすいといたつもりではあった。
D - aab aba baa
まず階乗進数に思いを馳せたが、文字は2種類なのでもう少し簡単だろうと思った。
AもBも小さいので全列挙できるかな？と思ったけど60C30を考えて真顔に。
組み合わせが計算できるなら、その値を参考に貪欲に構築できるなと思った。試しに60!までテーブルに保持したが時間はかからなかったのでこの方針で解き始めた。辞書順K番目の文字列を出力する問題でバグらせなかったことはないので、落ちたらやだなあと思いながら出したら通ってびっくりした。
E - Count Descendants
最初すぐには解法が浮かばなかった。木DPで集計してクエリに答えるタイプだろうと推測した。集計できる感じではないので、ダブリングでも使うのかなと思って考えていたがこれもよくわからなかった。
部分木クエリに読み替えて深さの小さい頂点から木に出現させていく（？）手法を取ればクエリソートしてオイラーツアーを区間木に載せることでとりあえず解けそうなことには気付いた。実装が重いので想定解ではないだろうと思ってこの実装に踏み切るのに逡巡したが、仕方ないのでこの方針をとった。
40分あたりでACしたが、この時点で2150くらいの推定パフォーマンスだったので方針を間違えて時間をかけすぎてしまったのだと解釈した。実は今回の実装は想定解通りで、単に自分が悩みすぎていただけだったのだ......
F - Integer Convex Hull
普通に諦めていたが、一応解こうとしてみた。
3点選んでその内部に入る点を見つけるのはO(N^4)で可能。三角形の面積の関係を使った。
辺を共有する三角形同士を連結することで凸包を作る方針で行った。辺を共有する三角形同士を無向グラフ上で連結させると、グラフは木になるように思えた。
そういうわけで木DPしていたが、値の伝播が難しく、「無理だなあ」と思っていたらコンテストが終わった。
総括
Dくらいまでいいペースで解けていた。ライブラリをちゃんと整備して木→オイラーツアー列をパッとできるようにしておけばもう少し速く自信を持ってEを解けたのではないかと思う。全体的にあまり焦りは感じなかった。
スランプは概ね抜けたのではと思ってはいるが懸念もある。Eを解いている時に頭にもやがかかるような感覚に陥った。今回は大して支障はなかったが、俯瞰することを見失って大冷えするときは大抵こういう感覚を味わうので（ここ２〜３週間はずっとこうだった）まだ油断はできない。
ZONe プログラミングコンテスト ネタバレ 答え
これの答えを書いていきます！よろしくおねがいします！
1問目
rot13をやれと書いてありますね！
"ZONe"という文字列の個数を数えればいいので、pythonであればcount関数が使えそうです！
print(input().count("ZONe"))
というコードで正解できます！
2問目
算数をやれと書いてありますね！
UFOに電波が届かないとき、電波が一個の障害物に当たっていることになります。逆も成り立ちますね！
距離d、高さhの障害物に電波が当たらないようにするためには、少なくとも
H-D(H-h)/(D-d)
以上の高さから電波を発する必要がありますね！
N,D,H=map(int,input().split());res=0
for _ in range(N):d,h=map(int,input().split());res=max(res,H-D*(H-h)/(D-d))
print(res)
というコードで正解できます！
3問目
やれと書いてありますね！
「答えをxにできるか？」という判定問題を考えるのが定石ですね！
2人を既に選んだ時点で、(パワー, スピード, 根性)など、特定の複数のパラメータがチームに足りないとき、足りない部分のパラメータの最小値が最大の人を選ぶのが最適ですね！
ところで、3人目に限らず、ある特定のいくつかのパラメータに絞ってみた時に最適な人をチームに入れるのが正しそうですよね！
そこで、5つのパラメータの任意の組み合わせ31通りについて、各パターンでパラメータの最小値が最大の人を先に選んでおくと、チームはこの31人から3人を選ぶのが良さそうですね！
from itertools import combinations as np
N=int(input())
a=[tuple(map(int,input().split())) for _ in range(N)]
aa=[]
res=0
def plt(x,pd):
res=10**9
for i in range(5):
if i in pd:res=min(res,x[i])
return res
for c in range(1,6):
for pd in np([i for i in range(5)], c):aa.append(max(a,key=lambda x:plt(x,pd)))
for pd in np(aa,3):res=max(res,min([max(pd[0][i],pd[1][i],pd[2][i]) for i in range(5)]))
print(res)
このコードで正解できます！
さいごに
全部解くことができました！いかがでしたか？
ZONeの進化には今後も目が離せませんね！
ZONeエナジー プログラミングコンテスト “HELLO SPACE” 反省
久しぶりにまた情けない冷え方をした。ZONe飲んでからコンテスト出たんだしちょっとくらい色つけてくれてもいいんじゃないの〜？
結果を鑑みて
1000 35:52
853位となった。ABC級で水パフォを出したのはかなり久しぶり。学業やバイトを気にしなくてはいけなくなる時期は決まってとんでもないパフォーマンスを出してしまう傾向にある。それに加えて精進不足から来る視野の狭さ、定数倍感覚のズレによってえらい目に遭ってしまった。
A - UFO Invasion
直前に似たような問題をtwitterに投げていたので少しドキッとした。
B - Sign of Friendship
初見では角度が問題の本質だと思った。arctanや二分探索（今回は誤差はあまり気にしなくていいので）が思い浮かんだ。
「これ二分探索必要だったのか」と実装中に思いもしたが、普通に実装して通せた。
このときの順位は普通だったと思う。
C - MAD TEAM
Dを先に解いている。
最小値の最大化ということで二分探索が結びつくわけだが、これは最大値の最小値の最大化なのでなかなか一筋縄ではない。
制約的に考えると２乗対数時間だが、この場合定数倍が重いと破滅の可能性があり、定数倍は軽めに作る必要に迫られた。
答えを二分探索しながら二乗で2人選出して、残りの1人を選ぶ時、 足りない部分のパラメータを充足してくれるような人間を求めることになるが、これをO(1)時間で行わねばならない。
充足する必要のあるパラメータの組み合わせ2^5 - 1に対して、充足しなくてはならないパラメータの最小値が最大のものを先に選出しておけば良い。この前計算で解くことが可能になった。
ところで、この場合二分探索が必要なく、この31人の中から3人選べば十分だということに気付けたので十分実行時間に余裕を持って制することができた。
順位はこの時点で悪くはないものだったと思う。Eを速い時間で通せれば橙パフォに大きく近づくので本腰入れてEに取りかかった。
D - Message from Aliens
reverseしているかどうかを持ってクエリを処理していくような問題は最近何度か見ている。
いつも通りやるだけだが、先頭追加があるのでdequeで実装した。
結構手間取った気がしていたが、この時点で200位切っており好順位につけていた。
E - Sneaking
読んですぐ頂点倍加してのdijkstraであることには気付けた。頂点数が10^5を超えた時に自分のdijkstraは定数倍がでかすぎて通らないことがあったので、陽にグラフを持たない方針で空間計算量を削減して解くことにした。これがすべての始まり、あるいは人生の終わりだった......。
(y, x)→(y - 1, x)方向の移動についての処理が頭の中でぐちゃぐちゃになってしまい、結局7ペナつけた上に本番中に通すことができなかった。なお、陽にグラフを作ってdijkstraしても十分余裕を持ってACできた。
定数倍感覚を改める必要があるのと、微妙な計算量なら最悪ケースを作って試してみることを教訓、ぐちゃぐちゃ実装を作らないことを課題とした。
F - Encounter and Farewell
あまり読めていない。本番中ではおそらく合計5分くらいはこの問題を考えていた。
さて、Eまで一応復習したことだし今からこの問題を考えてみることにする。
-
全域木の問題っぽい。ある頂点xを木に加えることができる場合に後回しにするメリットはない。0からいろいろ繋いでいくことにしてよい。
補グラフが与えられての全域木問題と考えられるか。数列Aの補集合を取るとxor基底がいくらか得られて、これで1~2^N - 1を作る問題に落ちた。なるほど。Eで焦っている時にF見ても解けはしなかっただろうと思うのでまあいいか。
なんかここまで解けた気でいたが、構築パートが難しい。一旦基底に分解すると厄介だ。
基底で新たなベクトルに対してxorを行って新しい基底を作る操作は辺を張るのと同義。のはずなんだけれど
ごちゃついたがなんとかAC。
小さい方から数列Aに含まれない数xを見ていって、まず0からxへの辺を張る。それまでに手に入れた基底でxorを貪欲に取りながら見たことのある数に辿り着いたらbreakする。そこまでの遷移をすべて辺として持つ。ということを繰り返して、最後に持っていた辺を使ってunionfindで全域木にする。という方針だった。
ごちゃついてペナしまくった原因だったのは「それまでに手に入れた基底を使って」という部分だった。本来log(N)個の基底が手に入って、それで以って連結グラフにできるはずなのにグラフの構築と基底の作成を同時に行ったために連結になっていなかったのだ。基底パートを2回回すことで無理やりAC。
総括
Dくらいまでの問題はいつものABCよりやや難しかったが、良いペースで解けていた。少し数学すればいい部分を実装パンチに持っていったところは少し反省。E以降はこの世の終わりのような実装でレートを持っていかれてしまった。定数倍感覚のアップデートが必要なのがわかった。もったいないペナとかしないように気を付けたい。焦って視野が狭くなるのを感じたら一回横になって天井を見ることにしているが、今回は感覚として焦っていると感じなかったのでこれを行わなかったが、20~30分おきに天井見てゴロゴロした方がいいのかもしれない。
AtCoder Beginner Contest 199 反省
実は先週の最強コン、それに続くARCについての記事を書いていない。忙しかったので仕方がない。軽く先週のおさらいをしておくと、「最強コンで黄パフォ黄色昇格→ARCで水パフォで-50くらいして青入り」
結果を鑑みて
1500(1) 66:52
298位となった。普段のABCでこの順位だと冷えかねないが、どうやら今日は参加人数が多かったようだ。今回のセットは典型力と実装力を問う問題が多かった。実生活の心配事を引きずって考察が鈍る傾向があるが、今回はウォームアップと睡眠（昼寝もあわせて13時間寝てる......）の甲斐あって冷えずには済んだ。
A - Square Inequality
どこかで見たような問題文だが、整数値の判定なのでふつうにやればよい。サンプル一通り試しても1分かからなかった。
B - Intersection
これも見てすぐ解法はわかった。
軽実装なので解いてすぐ順位表を見たが、特に危ない順位にはなっていなかった。
C - IPFL
問題文を読んで、これもすぐにわかったがflipが奇数回行われたときと偶数回行われたときで場合わけする必要があることが予期されて、少し実装したくなさがあった。そういうわけで少し実装が楽になる気付きポイントがないか少し考えたが、何も思いつかないので実装し始めた。実装していくと、flip奇数回のときにA, Bの値を書き換えることにしておけばそれ以降の処理は共通なので実装は案外重くならなかった。
最近はシンプルな実装ができるようになっている一方で、泥臭い実装を要することが予期されるとすぐにやる気がなくなることが増えた。よくないなあと思うが、競技との向き合い方自体に問題がある気がしている。
D - RGB Coloring 2
制約を見て、計算量の評価がすぐにできた。雑にやれば状態数が3^Nあるが、連結成分ごとに一頂点決め打てば2^Nに落ちる。
ところが、これを実装に落とすのに難儀してしまった。最初は色を配分した表を持ちながらDFSしていく方針だったが、これは探索中の頂点が連結成分の末端に達した時にうまく他に遷移できないこと、木ではないのでボトムアップな集計ができないこと（木は二点間のパスが1個だけなので二点間の情報伝播に矛盾が生じないが、閉路があると簡単ではない）から正しく実装できずに時間だけが過ぎ去ってしまった。
順位表を見て、DとEが50人ほど解けている状態だったので仕切り直す意味を込めてEを見に行った。このときにDが200人くらいに解かれていたら冷静な判断ができなくなっていたかもしれない。
Eを解いて戻ってくると、すでに150人程度に解かれていた。最初の方針で1回組み切って出して1ペナした。その後、やや実装は重いが連結成分ごとに頂点の色を決め打ちして正しく塗れているかをチェックする方針にシフトした。最初に取った方針と似てはいるが、DFSの集計に関する弱点がこちらの方針にはないので何とかこれを解くことができた。
最近のD問題にしてはかなり実装が難しい問題だったと思う。
E - Permutation
制約を見て、こんなものはbitDPしかないなと思った。実際、数列を端から順に構築していく場合に保持すべき状態数は2^Nずつで抑えることができる。あとは素直に組めばいいのだが、全状態でM個の制約全部を見ているとO(N^2M2^N)などという計算量（この計算量回文じゃん！）になってしまい、破滅の予感がした。そういうわけで枝刈りをして祈りながら提出をした。この枝刈りに少し時間を取られたが、最悪O((Mcomb(N,N/2)+2^N)N^2)くらいにはなっていたため通すことができた。一応、最悪ケースでコードテストもしておいた。
これを解いた後に気分新たにDを見に行った。
F - Graph Smoothing
難しい。これは本番中に解けなかった。なぜこんなに解かれているのか。
最初はDFSで考えていた。パスをうまく管理できればあとは組み合わせ計算でなんとかなるように見えたため。これは難航したので、別のアイデアがないか少し考えた。
次に出たアイデアが隣接行列のようなものを持っての行列累乗で、思いつきだったが問題の条件にフィットしており、大いに興味をそそられた。そこから先、行列の初期値をあわせるためにガチャガチャと値を変えていたのだが、ついにACできなかった。
行列累乗で考える場合は、「どの部分が何を表しているか」「次状態に遷移する際に、どこから寄与が生じていてどのような遷移式になるか」を意識して特に遷移部分を明確にしなくてはならない。今回は雰囲気で値をガチャガチャやっていてこの二点を疎かにしていたのが敗因となったように思う。
ところで、さっきまでこの問題Graph Somethingだと思っていた。
総括
Dで詰まってEに行った時のムーブは良かったが、もう少し早くDを後回しにしても良かった。また、最近は（といっても今回のと直近のcodeforcesだが）解法の正しい道筋が見えずに嘘解法を出してペナると途端に解法と問題の全体像が見えることが多くなってきた。できればWAとかになる前に気付きを得たいのだが、コンテスト中の冷静さが足りていないのだろうか。
