問題：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が与えら…

問題：C - 五目並べチェッカー 解答：Submission #13696167 - AtCoder Regular Contest 012 解法：いろいろな最終盤面が考えられるため、うまく場合分けをしてゆくことが必要。以下、各条件はそれより上の条件でYESNOが決まらなかったもののみ到達するものと…

問題：C - 積み上げパズル 解答：Submission #13676621 - AtCoder Regular Contest 010 解法：dp[i][j][k] ： i番目のブロックまで見て、直前に使った色がj色で、今までに使用した色の集合（ビットで表現）がkであるときの得点の最大値 とし、dpする。全色ボ…

問題：C - 積み上げパズル 解答：Submission #13676621 - AtCoder Regular Contest 010 解法：dp[i][j][k] : i番目までのブロックを見て、直前の色がjであり、今まで使用した色のビット集合をkとしてdpする。 計算量は n * m * 2m ≦ 5000 * 10 * 1024 < 107 …

問題：C - 高橋君、24歳 解答：Submission #13675261 - AtCoder Regular Contest 009 解法：誤って送った友達の組み合わせ数はnCk。 誤って送られた友達を(1, 2, ..., k)とすると、誤って送る送り方は1からnまでの順列(p1, p2, ..., pn)でかつ任意のiに対しp…

問題：No.7 プライムナンバーゲーム - yukicoder 解答：#487788 (C++14) No.7 プライムナンバーゲーム - yukicoder 解法：先手番の時、先手で「後手必勝」の局面に遷移する手があれば先手の勝ち、そうでなければ後手の勝ち。 dp[i] : iの時先手必勝なら1, 後…

問題：C - THE☆たこ焼き祭り2012 解答：Submission #13652774 - AtCoder Regular Contest 008 解法：投げ手をi、受け手をjとすると、iは自分が投げれる最も速い速度でかつjが受け取れる最も投げれる速い速度で投げればよいので、投げるスピードはmin(t[i], r…

問題：C - 高橋君と国家 解答：Submission #13629952 - AtCoder Regular Contest 029 解法：都市の他に交易所をノード(okn)とし、全ての都市と交易所との間に辺を考える。辺のコストはその都市に交易所を設置するときのコストとする。 すると、この問題は「N…

問題：D - grepマスター 解答：Submission #13607531 - AtCoder Regular Contest 014 解法：-B x -A yの時にどれだけ追加的にヒットするかを確認する。 1~L1まではmin(L1-1, x)個、 L1+1~L2-1まではmin(L2-L1-1, x+y)個、 L2+1~L3-1まではmin(L3-L2-1, x+y)…

問題：C - 積み木 解答：Submission #13584602 - AtCoder Regular Contest 031 解法：まず1の移動先を考えると、これは1番左か1番右になる。仮に近い方に置くとする。 次に2の移動先を考える。これは1を除いて1番左か1番右となる。つまり、先に置いた1の位置…

問題：C - ウサギとカメ 解答：Submission #13491153 - AtCoder Regular Contest 025 解法：N ≦ 2500、M ≦ 3000 なので全点ダイクストラやっても間に合いそう。(TLEも7秒) 目的地を固定して、目的地を始点とするダイクストラをする。すると目的地から各中継…

問題：F - Select Half 解答：Submission #13466424 - AtCoder Beginner Contest 162 解法： こちらのブログを参考にしました。考察が綺麗すぎて感動です。 betrue12.hateblo.jp まず、連続しないぎりぎりで数を選ぶことを考えます。oxoxoxoのような選び方で…

問題：No.801 エレベーター - yukicoder 解答：#484275 (C++14) No.801 エレベーター - yukicoder 解法：エレベーターiはLi階からRi階を移動する。すなわち、Li ≦ j ≦ Ri なるj階から、Li ≦ l ≦ Ri なるl階に移動する。よってこの足し算をまとめて行う必要が…

問題：No.458 異なる素数の和 - yukicoder 解答：#483584 (C++14) No.458 異なる素数の和 - yukicoder 解法：20000までの素数のリストを作成する。20000までの素数の個数は2262個。 dp[i][j] ： i番目の素数までを使い、残りの数がjであるときのこれまで使っ…

問題：No.914 Omiyage - yukicoder 解答：#483578 (C++14) No.914 Omiyage - yukicoder 解法：dp[i][j] ：i番目の国まででお土産を買ったとき、残金をjにすることができるかのbool でdpする。 dpの遷移は、各iについて、残金jのとき、その国のお土産lを変え…

問題：No.533 Mysterious Stairs - yukicoder 解答：#482595 (C++14) No.533 Mysterious Stairs - yukicoder 解法：dp[i][j] を今i段目にいて、直前でj段上ったときの通り数としてdpする。 dpの遷移は配るdpとして if(j != 1) dp[i+j][j] += dp[i][1] のよう…

問題：No.800 四平方定理 - yukicoder 解答：#481517 (C++14) No.800 四平方定理 - yukicoder 解法：半分全列挙。等式を移行するとx2 + y2 = w2 - z2 + D となるので、両辺全ての組み合わせを列挙し、一致するものの個数を数える。mapだとTLEしたので配列を…

問題：No.875 Range Mindex Query - yukicoder 解答：#481502 (C++14) No.875 Range Mindex Query - yukicoder 解法：(数値, インデックス)をペアにしてセグ木に入れる。

問題：F - Three Variables Game 解答：Submission #13217763 - AtCoder Beginner Contest 166 解法：再帰で通った。計算量要確認。