問題：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の倍数が含まれているかどうかを確認すればよい。 こ…