問題：E - Common Subsequence 解答：Submission #15893522 - AtCoder Beginner Contest 130 解法：dp[i][j] ： sのi番目、tのj番目を最後に使うときの共通部分列の個数（空集合は除く）、 sm[i][j]：dpの二次元累積和 とすると、s[i] == t[j]の場合にdp[i+1…

問題：D - 徒競走 解答：Submission #15838027 - AtCoder Beginner Contest 041 解法： bitDPでトポロジカルソートの通り数を数える。 考え方としては、「すでに使用した頂点集合」をbitとして持たせてDPする。すなわち入次数の小さい頂点から推移させていく…

問題：C - たんごたくさん 解答：Submission #15800122 - 天下一プログラマーコンテスト2016本戦（オープンコンテスト） 解法：トライ木を使用する。 ei1333.github.io dp[i]：Sのi文字目までの単語の重みの最大値とする。 あらかじめ各単語をトライ木に格納…

問題：D - 映画の連続視聴 解答：Submission #15529217 - Code Formula 2014 本選 解法：それなりに探索しないといけなそう。DPを行う。 前処理として、時間0と終了時間を含む（重複のない）配列を作成しておき、また終了時間からその配列のインデックスが分…

問題：E - M's Solution 解答：Submission #15474499 - M-SOLUTIONS Programming Contest 2020 解法：追加する線路は集落を通るとしてよい。集落を通らない線路は「移動させてもコストが変わらない」「片方に移動させるとコスト増、もう片方に移動させるとコ…

問題：No.1103 Directed Length Sum - yukicoder 解答：#516999 (C++14) No.1103 Directed Length Sum - yukicoder 解法：木DP。 dp1[p]：頂点p以下の各頂点同士のパス長合計 dp2[p]：頂点p以下の頂点数合計 dp3[p]：頂点pと頂点p以下の頂点を結ぶパス長合計…

問題：C - 偶然ジェネレータ 解答：Submission #15324937 - AtCoder Regular Contest 036 解法：作成された文字列について前から文字を見てゆき、1なら+1、0なら-1する変数xを準備する。max(x) - min(x)がK以下ならその文字列は採用される。 このような文字…

問題：C - 暗闇帰り道 解答：Submission #15293678 - AtCoder Regular Contest 003 解法：「明るさの最小値をxとしてゴールまでたどり着けるか」の二分探索をやる。各試行では、グリッドグラフでダイクストラ法を行う。

問題：C - 幼稚園児高橋君 解答：Submission #15266646 - AtCoder Regular Contest 039 解法：例えば辿ったマスを記憶しておき、辿ったマスへ移動した場合はもう一回移動する、のような解法だとO(N2)でTLE。 Dancing Linksという典型的なテクニックがあるら…

問題：C - 仕事計画 解答：Submission #15233951 - AtCoder Regular Contest 032 解法：区間スケジュールで最も多くの仕事をこなすには、終了時間の速い順に仕事をソートし、貪欲に仕事を選んでゆけばよい。 ただしこの問題では、仕事の数が同数の場合は選ん…

問題：F - Intervals on Tree 解答：Submission #15077700 - AtCoder Beginner Contest 173 解法：超重要な公式として「森の連結成分 = 頂点数 - 辺数」がある。これはn個の頂点から1つずつ辺を増やすことで連結成分数が1つずつ減っていくことに対応する。ま…

問題：No.365 ジェンガソート - yukicoder 解答：#507527 (C++14) No.365 ジェンガソート - yukicoder 解法：嘘解法を量産しました。。 正解はn - 「数列を後ろから見て、n, n-1, n-2, ....と降順にとれる項数」です。 嘘解法としては、「数列を前から見て自…

問題：F - Removing Robots 解答：Submission #14877202 - AtCoder Beginner Contest 158 解法：ロボットを座標順にソートする。 f(i)：i番目のロボットを動かそうとしたとき、連鎖的にどこまでのロボットが動くか の関数とする。 このとき、iが直接動かせる…

問題：E - NEQ 解答：Submission #14790587 - AtCoder Beginner Contest 172 解法：A、Bの数列の条件を言い換えると、①「同じ位置にあるAとBの要素は異なる」、②「数列Aの各要素は互いに異なる。また、数列Bの各要素も互いに異なる。」となる。 問題の設定と…

問題：E - Handshake 解答：Submission #14704600 - AtCoder Beginner Contest 149 解法：「億マス計算」の類題。下記のブログを参考にしました。 tt-conpetitive.hatenablog.com ひとまずAは昇順ソートする。 「M回の握手の幸福度の最大化」は「A[i] + A[j]…

問題：D - Classified 解答：Submission #14684809 - Japanese Student Championship 2019 Qualification 解法：同じ頂点に戻るときの経路長が偶数のみ⇒奇数長のサイクルを持たない⇒2部グラフ、ということで完全グラフを2部グラフに分けてゆく。 例：Ｎ=7 ①{…

問題：D - Squirrel Merchant 解答：Submission #14666566 - diverta 2019 Programming Contest 2 解法：解説解。 取引所Aでドングリ⇒金属、取引所Bで金属⇒ドングリの交換をそれぞれ行うことを考える。例えば金を用いた場合は、ドングリgA個を用いてドングリ…

問題：No.817 Coin donation - yukicoder 解答：#501352 (C++14) No.817 Coin donation - yukicoder 解法：i円の硬貨が何枚あるかを累積的に管理し、個数がk以上となるときのiを出力すればよい。ただし、硬貨の種類の上限が109であるため、全ての種類の硬貨…

問題：F - Strivore 解答：Submission #14600583 - AtCoder Beginner Contest 171 解法：最終的にできた文字列を次のように解釈する。（例：oof） ①o②o③f④ ①：o以外の文字からなる長さ0以上の文字列 ②：o以外の文字からなる長さ0以上の文字列 ③：f以外の文字…

問題：F - Knapsack for All Segments 解答：Submission #14462241 - AtCoder Beginner Contest 159 解法：Ax1 + Ax2 + ... + Axk = Sなる(x1, x2, ..., xk)が見つかったとして、この(x1, x2, ..., xk)がΣf(L, R) に与える寄与を考える。 L ≦ x1 かつ xk ≦ R…

問題：D - Knapsack Queries on a tree 解答：Submission #14401193 - Tokio Marine & Nichido Fire Insurance Programming Contest 2020 (yosupoさんのほぼ丸写し…) 解法：愚直にやると18 * LのナップサックをQ回やることになり、間に合わない。途中まで前…

問題：C - 掛け算 解答：Submission #14204559 - AtCoder Regular Contest 051 解法：数列を昇順にし、a[0], a[1], ..., a[n-1]と並べる。a[0] * A ≧ a[n-1] となる場合、a[1] * A ≧ a[0] * Aである。つまり、一旦最小値をA倍した数が数列の最大値以上になる…

問題：D - パズル 解答①：Submission #14186203 - Indeedなう（予選A） 解法①：最小手数が24手以内という上限があるため、これをうまく使う。 半分全列挙の応用。最初の盤面から12手以内で到達できる盤面とその盤面に到達する最小手数のmap(mp)、最後の盤面…

問題：F - LIS on Tree 解答：Submission #14166837 - AtCoder Beginner Contest 165 解法：dfsで各頂点を辿りながらLISのdpを更新、巻き戻しを行う。 巻き戻す際は、dfsでLISを更新する際に更新するインデックス、更新前の値、更新後の値を保持して置き、隣…

問題：D - 壊れた電車 解答：Submission #14146276 - CODE FESTIVAL 2015 予選A 解法： 時間kを決め打ちし、その時間で電車の点検が完了できるかの二分探索を行う。 二分探索の各試行では左の整備士から整備範囲を貪欲に決めることができる。 実装としては、…

問題：https://atcoder.jp/contests/abc169/tasks/abc169_f 解答：https://atcoder.jp/contests/abc169/submissions/14125789 解法： こちらを参考にしました。 sen-comp.hatenablog.com Ax1 + Ax2 + ... + Axk = Sとなる(x1, x2, ..., xk)なる組み合わせが…

問題：C - 蛍光灯 解答：Submission #14082949 - AtCoder Regular Contest 026 解法：dp[x] = xまでは照らされているときのコストの最小値とする。lの値が小さい順に処理してゆく。 (l, r, c)によるdpの更新はt = dp[l]とし、chmin(dp[l], t + c), chmin(dp[…

問題：No.1049 Zero (Exhaust) - yukicoder 解答：#491520 (C++14) No.1049 Zero (Exhaust) - yukicoder 解法： i回目の操作後に、1, 2, ..., p-1となる操作数は、実はそれぞれ等しい。 そのため、a : 0となる操作の個数、b : 1となる操作の個数（=2となる操…

問題：No.1048 Zero (Advanced) - yukicoder 解答①：#491132 (C++14) No.1048 Zero (Advanced) - yukicoder 解答②：#491139 (C++14) No.1048 Zero (Advanced) - yukicoder 解法：[l * k, r * k] の区間にMの倍数が含まれているかどうかを確認すればよい。 こ…

問題：http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2331&lang=jp 解答：AIZU ONLINE JUDGE: Code Review 解法：x人が参加するとした場合に、参加できる人の数を数え、それがx-1人（「私」を除くため）以上でる最も大きなxが答え。 xが与えら…