try-catch DFS を布教したいだけ（twitter を眺めていたら見つけたのでパクっただけなんですが…） 問題 atcoder.jp 頂点 辺の単純無向グラフが与えられる。各頂点の次数は 以下である。 頂点 からの単純パスの個数を とした時、 を求めよ。 制約 解法 基本的…
やっていること自体は公式解説と同じなのですが、状態の持ち方が割と素直かも？と思ったので 問題 atcoder.jp 次正方行列であって、以下を共に満たすものの個数を で割った余りで求めよ。 ・すべての について、 行目の総和が に一致 ・すべての について、 …
問題 atcoder.jp 人の新入生がいて、それぞれの名前が英小文字で与えられる。学籍番号は英小文字の順序に従って辞書順で並べたときの順番で 1-indexed に振られる。 英小文字の順序をランダムに定義したとき、学籍番号の期待値は？ 解法 例えば という文字列…
厳密性には欠ける可能性あり 数式はあまり使わないように（めんどくさいし、僕も分からなくなってしまうので） 公式解説にかなり丸投げをしますし、そもそもあまり人に読ませることを想定していないので、ご了承・・・ F 問題文を読むと、いかにも ACL を使…
ざっと見て自分と同じ解法の人がいなかったので 問題 atcoder.jp 解法 制約が小さいのでbitDPみたいなのが考えられそう．2×1の畳の敷き方が決まれば全体の敷き方も一意に決まるので，以下は2×1の畳を敷いた状態を考える． dp[bit][j]:2×1の畳をちょうどj枚敷…
問題 atcoder.jp 解法 いわゆる「桁DP」と呼ばれるやつ まあ桁DPがよく分からなくてもとりあえず動的計画法っぽいことを認識できれば良し（種類数を管理しながら・・・とかを考えるとDPでやりたいお気持ちになってくる） dp=(上からi桁目まで見た時にn未満に…
フローを理解するためのいい問題だった atcoder.jp 解法 こういうある状況と２種類の操作が与えられるので，どっちかに振り分けて最適にする感じの奴はmaxflowにだいたい帰着できる（多分） 詳しくはこれに色々書いた cprgrma2.hatenablog.com この問題にお…
色々読んで適当に掴んだ雰囲気をなぐり書きしていくので表現の厳密さ，丁寧さには欠けると思います 読み込んだのをそのまま吐き出す感じだったりするのであらゆる記事の丸パクリっぽくなるかもしれないし，独自の解釈が混ざっているので信憑性に欠ける部分も…
atcoder.jp 解法 最小回数で到達できないといけないので，１回あたりでできるだけ先に進む必要がある． また，辞書順で最小ということは，最初の方はなるべく小さい歩数でいきたい． ということを考えると， 最初の方は控えめ→あとの方でなるべく大きく進む …
ARMERIAさんのブログが非常にわかりやすかった 問題 atcoder.jp 解法 '(':+1 ')':-1 と対応させると，適当に文字列を構成した時に累積和Sが以下を満たすようなパターンは存在するか？という問題に言い換えられる． 1.任意のindexに対してS[index]>=0 2.最終…
色々実験して性質を観察するの大事・・・ 問題 atcoder.jp 解法 とりあえず頂点数が小さい範囲でどのような向き付けができるかを見てみる． すると任意の２頂点u,vに対して u→vの向きづけがあるならば，c[u]>=c[v] が成り立っていることがわかる． あとは，…
問題 atcoder.jp 解法 問題のタイトル通りナップザック問題を考える． dp[i][j]:i番目までの要素までを用いた部分集合Sを考えたとき，総和がjになるようなSの部分集合の数 とすると，dp[n][s]が答えとなる． すると，遷移としては以下が考えられる． （要素a…
ABCD4完1ペナ42:17・・・Eは解けるべきだしペナの出し方も下手だったしCも正直間に合うだろうな〜って思ったのに躊躇って出さなかったのでさっさと投げるべきだったしで色々下手でした A if(s[0]==s[1] and s[1]==s[2]) でもいいが， std::sort(s.begin(),s.…
蛇足をしてめっちゃ遠回りした・・・ 問題 atcoder.jp 解法 まあ雰囲気がDPなのでDP 最大サイズがLぴったりになる個数を考えたいところだが，連結成分が複数あるときにめちゃめちゃ面倒なことになる(例えば連結成分のサイズの集合を考えた時に{L}とか{L,L,L,…
よくよく考えれば，それはそう・・・ 問題 atcoder.jp 解法 なんか難しく書いてある（解説も）けど，結局は普段の買い物を考えてみるといい（例えば普通10円玉を使って支払う時に，10円玉のお釣りが出るような払い方はしない） そうすると，下の桁から端数の…
メモ化再帰めっちゃ遅くてビビった 問題 atcoder.jp 解法 要するに繋がってる同士でグループわけができればいい 1つにならない場合は適当にグループ分けして，その分けたグループ内でもできる限り少ないグループ分けになればよさそう→そういうDPを考える（こ…
むずかった・・・ 解説AC 問題 atcoder.jp 上を見よう 解法 A:→↓でいけるやつ B:↓→でいけるやつとして A∨Bが求まればいいので A∨B=A+B-(A∧B)で求めればいい． AとBはそれぞれ各列or各行において最小となる成分を事前に計算しておけば良し（ここまではできた…
某動画を見て以来（初めて見たとき茶コーダーとか）どういうことなんだろうって思ってたやつ 忘れないように 何がしたいの i
atcoder.jp 考えたこと まあそりゃDPなんだけど 閉路がないってことは何も生えてこない頂点が存在するはず→これを基準にDPを組み立てていくと良さそう この位置にあったので身構えてたけど，思いの外シンプルだった atcoder.jp
atcoder.jp 考えたこと 貪欲っぽいけど嘘が怖いなぁ とりあえず貪欲が見えたらDP疑ってみる→HPをいくら削ったとか，どの刀を投げたかとかみたいなのを状態で持とうとしたりしたけど，まあ制約的に無理（当たり前） どうやったら状態数減らせるか→普通に考え…
