ABC349 A~E解説
A問題(2:32)
問題文を読んでみたがよくわからなかった -> サンプルケースを見てみると、0 - SUM(A) で良さそうだな。AC
B問題(5:13)
mapで文字数を管理するといい。文字の登場回数などを聞かれたら基本mapとかで管理するべき。最初に map[文字]=登場回数 みたいに記録しておいて、最終的に登場回数ごとの文字の個数をmapで管理すればいいだけ。
C問題(17:06)
最初は連続する部分文字列かと誤読してしまってタイムロス。
連続しない部分文字列 -> DPでTの何文字目までがあるか判断できるよね
DP[i][j] = i番目までの文字列を見てTのj文字目までを完成させられるかでDPをした。あとは、(DP[N][2] & T.back(X)) || DP[N][3] を判定するだけでいい。（もっと簡単な解法あっただろ）
D問題(62:49 - 1ペナ)
最初ノートに書いていたりすると、(2^i*j, 2^i*j + 2^i)となっていることがわかる。よって、現在のLが2^i*jの場合は最大で2^iの区間分を良い数列としてカバーできる。Lは2^iの倍数ではないと表現できない。一般化すると、現在のLが2^iの倍数である、最大のiの分だけ動けるということがわかる。あとはそれを実装するだけ。(こうやって書いてみると簡単そうだな)
E問題(93:48 - 3ペナ)
まず、ゲームの進み方の通り数はざっと見積もって 9!=10^5 ほどしかないことがわかる。よって、dfsなどで全部の盤面を探索できることがわかる。
ここで常識的な知識が役に立ってくる、「丸バツゲームは」両方が最適な行動をした場合、必ず引き分けになるということだ。今回の問題の場合、両方とも最適な行動をするため、結局は得点のみの差で勝敗が決まるということがわかる。公式の解説では勝敗のみで遷移をしているが、そっちの方が楽そうだった。あとは自分と相手の得点差をお互い最小化しつつ遷移させて、最終的に0 < res だったら Takahashi それ以外だったら Aoki。
この記事が気に入ったらサポートをしてみませんか？