問題：D - 日本沈没 (Japan Sinks) 解答：Submission #19057982 - JOI 2018/2019 予選 過去問 解答：まずは初期状態の島の個数を数える。これは「i = 0かつa[i] > 0」もしくは「i > 0かつa[i-1] == 0かつa[i] > 0」の時にカウントアップすることで求まる。 …

問題：B - JJOOII 2 (JJOOII 2) 解答：Submission #19057001 - JOI 2019/2020 本選 過去問 解法：まず、Oの選び方を考える。最初に用いるOを選んだとき、それ以降のOはそこからなるべく近くにあるOを選んでいったほうが良い。すると、使用するOが決まる。さ…

問題：B - JJOOII 2 (JJOOII 2) 解答：Submission #19057001 - JOI 2019/2020 本選 過去問 解法：まず、Oの選び方を考える。最初に用いるOを選んだとき、それ以降のOはそこからなるべく近くにあるOを選んでいったほうが良い。すると、使用するOが決まる。さ…

問題：A - 長いだけのネクタイ (Just Long Neckties) 解答：Submission #19055773 - JOI 2019/2020 本選 過去問 解法：試着会のネクタイ(a)を除いた後に奇妙さを調べる際は、試着会のネクタイ・社員のネクタイ(b)どちらも昇順ソートしてmax(a - b, 0)を調べ…

問題：L - マンションの改築 解答：Submission #18663672 - 第四回 アルゴリズム実技検定 解法： mapに(隣接項の差, 偶奇)ごとの個数を記憶しておく。 また、t=1による増減分をev, t=2による増減分をodという変数に持たせることとする。 t=1, 2の時ev, odを…

問題：https://onlinejudge.u-aizu.ac.jp/courses/library/7/DPL/4/DPL_4_B 解答：https://onlinejudge.u-aizu.ac.jp/status/users/misora192/submissions/1/DPL_4_B/judge/5014179/C++14 解法：半分全列挙で、かつデータ構造が肝。 cnt[x][y]：配列aの前半n…

問題：https://onlinejudge.u-aizu.ac.jp/problems/DPL_3_B 解答：https://onlinejudge.u-aizu.ac.jp/status/users/misora192/submissions/1/DPL_3_B/judge/5013955/C++14 解法： 参考サイト： ALGORITHM NOTE 長方形探索： 最大長方形の面積 Largest Rectan…

問題：E - Payment 解答：Submission #16213292 - AtCoder Beginner Contest 155 解法：dp[i][j] ：上からi桁までの支払金額が決まっていて、j=0ならぴったり支払い、j=1ならキャリーがある状態、としてDP。DPはサンプルを合わせた…

問題：C - 節制 解答：Submission #16166455 - AtCoder Beginner Contest 013 解法：普通の食事をi回する場合、質素な食事の回数jの条件は、 j < (H - (N - i) * E + i * B) / (B - D)を満たすことである。よって、各iごとにjが最大である場合のコストを比較…

問題：D - Match Matching Python解答：Submission #16067781 - AtCoder Beginner Contest 118 Python解法：dp[i]：残りマッチ棒がi本の時に作れる最大の数字 として配るDPをする。dp[0]が答え。 C++解答：Submission #16083490 - AtCoder Beginner Contest …

問題：https://atcoder.jp/contests/abc054/tasks/abc054_d 解答：Submission #16049869 - AtCoder Beginner Contest 054 解法：薬品量の最大値は薬品A, Bともに400グラムであるため、以下のDPが間に合う。 dp[i][j][k] : i番目のお店の混合液までで、薬品Ａ…

問題：D - 語呂合わせ 解答：Submission #15893924 - AtCoder Beginner Contest 031 解法：各数字に対し、対応する単語の文字長を決めると、各v[i], w[i]の対応においてどの数字がどの単語にあたるかが一意に決まる。よって各数字に対応する単語の文字長（1…

問題：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であるため、全ての種類の硬貨…