Quiz https://yukicoder.me/problems/no/1310 AC https://yukicoder.me/submissions/596585 解説 +1, -1が隣り合う箇所（変化点）に注目する N個のマスに切れ目をいくつか入れ、グループごとに+1, -1を割り当てる。変化点の数は切れ目の数 円環なので切れ目…

Quiz https://yukicoder.me/problems/no/1076 解説 editorialのように方程式一発でやるとかっこいい でも今回は基本に立ち返って求めてみると、以下のようになります 「等比数列の和の公式」を使いました

Quiz https://yukicoder.me/problems/no/999 公式解説 https://yukicoder.me/problems/no/999/editorial 私の解説 累積和を使わなかったので書いておく ほむちゃんが左から攻める領域と、右から攻める領域は2つは左右に分割されるので、切れ目を全探索。各切…

Quiz No.771 しおり https://yukicoder.me/problems/no/771 AC https://yukicoder.me/submissions/353958 他の人の解説記事 はまやんはまやんさん https://www.hamayanhamayan.com/entry/2019/01/02/214632 解法 Bit DP 蟻本(v2)で言うと、p173の巡回セール…

Quiz https://yukicoder.me/problems/no/539 AC Code https://yukicoder.me/submissions/353645 感想 やるだけなのだが、意外と骨が折れる 文字列で表された数字の和はたまに作ることがあるので関数化しておきたい 文字列で表された数字の和 string zero_pad…

Quiz https://yukicoder.me/problems/no/267 Submission https://yukicoder.me/submissions/350277 解法 vector<pair<int, int> > Aをソートすると、firstの昇順でソート、firstが同じグループの中ではsecondの昇順でソートされる それを使うことを見越して絵柄(D, C, etc)</pair<int,>…

Quiz https://yukicoder.me/problems/no/71 Submission https://yukicoder.me/submissions/350266 考察 N=5 普通のそろばんと同じ数 1, 4に分けると0〜9までの10種類を表現できる 一方、サンプルケースでは2, 3に分けることで11種類を表現できる 等分すると…

Quiz https://yukicoder.me/problems/no/754 Submission https://yukicoder.me/submissions/350209 解法 N=3で書いてみると以下の和を求めればいいと分かる 配列AかBの累積和を持っておけば、和はO(N)で求められる

Quiz https://yukicoder.me/problems/no/496 Submit https://yukicoder.me/submissions/342341 類似問題（一次元） https://tdpc.contest.atcoder.jp/tasks/tdpc_contest https://tdpc.contest.atcoder.jp/submissions/5127160 解法 上記一次元のDPと同じ解…

Quiz https://yukicoder.me/problems/no/74 Submit https://yukicoder.me/submissions/339953 解法 1枚だけでflipできるコインを調べておく 2枚flipのとき a, bを一緒にflipできるなら、Union Findでunite(a, b)しておく 「一緒にflipできるグループ」ごとに…

Quiz https://yukicoder.me/problems/no/416 Submit https://yukicoder.me/submissions/339563 解法 破壊される辺以外を張っておく 破壊クエリを逆から読みながらその辺を復活させていく 木がつながったかはUnion Findで管理する 辺を繋げる前に、今回の接続…

Quiz https://yukicoder.me/problems/no/390 Submit https://yukicoder.me/submissions/19573 解法 公式解説の通りではあるが、各dp[i]についてiの約数を列挙してdpを更新してACした 配るDPがオススメされていたが、制限時間ギリギリそうな列挙でトライした …

Quiz https://yukicoder.me/problems/no/477 Submit https://yukicoder.me/submissions/336588 解法 他の人は数式で解いていたが、私は二分探索で解いた 二分探索 left = 0 (絶対にMVPが取れない) right = inf (絶対にMVPが取れる) center = (left + right) …

Quiz https://yukicoder.me/problems/no/561 Submit https://yukicoder.me/submissions/336212 解法 動的計画法を使う dp[2][N] dp[i][j] i : 0:東京 1:京都 j : j日目 (0-index)の仕事を終えた後のお金 とする 前日の稼ぎと当日の稼ぎの関係は 前日東京→ 当…

Quiz https://yukicoder.me/problems/no/198 Submit https://yukicoder.me/submissions/335991 解法 キャンディーの目的値を決めると操作回数が決まり、これは下に凸の関数になる 三分探索すればいい 学び while(right-left>3){ ll p0 = (2 * left + 1 * rig…

Quiz https://yukicoder.me/problems/no/65 Submit https://yukicoder.me/submissions/335985 解法 振る回数の更新式は提供されている E(K)以降は、もうK回を達成しているので振る回数は0であることに気づけば、後ろからのDPができる

誤差と桁あふれに注意する必要があるよい問題（教材）がある。 Quiz https://yukicoder.me/problems/no/648 Submit https://yukicoder.me/submissions/335262 解法 t秒後の合計はt * (t+1) / 2 それとnが一致する整数があればいい tについて解の公式で解く …

Quiz https://yukicoder.me/problems/no/314 Submit https://yukicoder.me/submissions/330500 他の人の解法 dp[i][j] : i番目まで見たとき、ケンの数が j である場合の数 解法 私は、直前2つの状態を見れば遷移が決まることから、 dp[i][j][k] i 番目まで見…

Quiz https://yukicoder.me/problems/no/3 Submit https://yukicoder.me/submissions/330413 解法 ある地点からの移動先は(2箇所以下に)固定されている よって、ある地点に戻って来たら、それは最短距離ではない 同じ地点を訪れないようにしながら最短距離を…

Quiz https://yukicoder.me/problems/no/4 Submit https://yukicoder.me/submissions/330176 解法 天秤の両方を気にするのは大変 重さの合計 / 2 を片側で作れるかで判定すればいい 各重りを使う・使わないで分岐したらO(2100)となってしまう dp[i][j] : i番…

Quiz https://yukicoder.me/problems/no/786 Submit https://yukicoder.me/submissions/329556 解法 dp[i] : i段登るときのパターン数とする dp[i]は、 dp[i-2]から2段UP dp[i-1]から1段UP という遷移から来ることができるので、 dp[i] = dp[i-2] + dp[i-1] …

Quiz https://yukicoder.me/problems/no/806 Submit https://yukicoder.me/submissions/328743 解法 公式解説の通り、Σmax(Deg(i)-2, 0) ポイント グラフを次数で見る 最終形の性質を観察する そして現状と比較して、その差が、すべき操作

Quiz https://yukicoder.me/problems/no/790 AC https://yukicoder.me/submissions/328008 概要 対応の取れた括弧は何パターンあるか ()()() ((())) など 解法 各位置にどちらの括弧を置くか全パターン生成してからチェックする またはカタラン数 青チャート…

Quiz https://yukicoder.me/problems/no/800 Submit https://yukicoder.me/submissions/324836 Note 4変数で半分を全探索 これは蟻本「おみくじ」で見たやつだ！ x, yは全探索, z, wから作れるパターンは事前に作っておく 二分探索 解いてみる https://yukic…

Quiz https://yukicoder.me/problems/no/793 Submit https://yukicoder.me/submissions/318975 Note 10N (N=1018) ここに高速累乗を使う。log(N) 3で割ったもののmodなのでフェルマーの小定理を使う