問題：E - Smooth Subsequence 解答：https://atcoder.jp/contests/abc339/submissions/49982630 解法：解説AC。dp[i][x]を「数列をi番目まで見たとき、①そのi番目の数がxであればi番目まででできる題意を満たす部分列の最大長、②そのi番目の数が0でなければ…

問題：F - Merge Set 解答：https://atcoder.jp/contests/abc302/submissions/41636421 解法：解説AC。 頂点1からNの後に、1からMまでの整数に対応する超頂点を導入する。どちらも0-indexに変換して、0~N-1を頂点に、N~N+M-1を超頂点に対応させる。また、集…

問題：D - Three Days Ago 解答：https://atcoder.jp/contests/abc295/submissions/40056127 解法：l, r間で各数字が偶数個出ていればOK。数字の個数を累積和で管理すると、l, rで各数字の個数の偶奇がそろっていればよい。 とすると、各数字の個数は偶奇の…

問題：D - Project Planning 解答：Submission #27305078 - KEYENCE Programming Contest 2021 (AtCoder Beginner Contest 227) 解法：何となく部署の人数が多い方から一人ずつ集めるとよさそうだが、a[i]を減らしていって新たにタイが発生するところからわ…

問題：F - Blocked Roads 解答：Submission #25886274 - AtCoder Beginner Contest 218 解法：各辺を除いて逐一最短経路の算出をやると、辺の数がN2のオーダーなので、例えばダイクストラならO(N3logN)で間に合わないっぽい。 ここで一つ最短経路が見つかっ…

問題：E - Safety Journey 解答：Submission #24919698 - AtCoder Beginner Contest 212 解法：DP。 dp[i][j]：i日目に都市jにいるときの場合の数とする。答えはdp[K][0]である。 Eを使える道の集合とする。 dp[i][j] = Σdp[i-1][k] ( (k, j) in E) = Σdp[i-…

問題：E - Stronger Takahashi 解答：Submission #24895895 - AtCoder Beginner Contest 213 解法：01BFSが使える。 移動先をdequeに格納する。通常の移動はpush_front、パンチ後の移動をpush_backするとよい。

問題：F - GCD or MIN 解答：Submission #20060874 - AtCoder Beginner Contest 191 解法： 「最終的に残る数」の構成 gcd(a, b) ≦ min(a, b) より、最終的に残る数はmin(A)以下である（以降min(A)をAminと呼ぶ）。また、あるAi1, Ai2, ..., Aixに対し、gcd(…

問題：F - Sugoroku2 解答：Submission #19664058 - AtCoder Beginner Contest 189 解法：M個以上の連続した「スタートに戻る」マスがあればゴールに到達不可能であり、その場合は-1を出力する。それ以外はゴールに到達可能となる。 期待値の独立性より、あ…

問題：E - Rotate and Flip 解答：Submission #19699054 - AtCoder Beginner Contest 189 解法：与えられた4種類の座標変換は、tT = [x, y, 1]に対し、3×3の行列Aを左から乗じることで計算することが出来る。具体的には下記の通りである。 [[0, 1, 0], [-1, …

問題：E - ∙ (Bullet) 解答：Submission #19557514 - AtCoder Beginner Contest 168 解法：美味しさA、香り高さBのイワシを(A, B)と表記する。 (0, 0)のイワシはどのイワシとも一緒にクーラーボックスに入れない。よって(0, 0)のイワシは別に考え、最終的な…

問題：F - Contrast 解答：Submission #19529927 - AtCoder Beginner Contest 178 解法：AとB合わせてN+1個以上含まれる数字がある場合は、どのように並べ替えてもAとBとでかぶる場所が生じてしまうためNoを出力する。実はそれ以外の場合はBを適切に並べ替え…

問題：C - Robot on Grid 解答：Submission #19484879 - KEYENCE Programming Contest 2021 解法：空白マスの取扱いが難しい。(1, 1)から(r, c)までの1つのパスを考える。通常このパスは1通りであるが、パス中に空白マスがある場合、この空白マスはXまたは(R…

問題：F - Rook on Grid 解答：Submission #19457973 - Panasonic Programming Contest (AtCoder Beginner Contest 186) 解法：右→下と動く場合と下→右と動く場合に分けて考える。 ①右→下と動く場合：各列ごとに最初に当たる障害物の行座標を覚えておき、そ…

問題：F - Close Group 解答：Submission #19455050 - AtCoder Beginner Contest 187 解法：元のグラフをG = (V, E)とする。S ⊂ Vに対し、f(S)を誘導部分グラフ(S, Es)に対する元の問題の答えとすると、f(S)はSが完全グラフ（すべての頂点間に辺が張られたグ…

問題：F - Close Group 解答：Submission #19454159 - AtCoder Beginner Contest 188 解法：解説どおりに逆から考える。下記が言える。 「+1, -1」、「-1, + 1」は意味がない 「+1,+1,/2」よりも「/2, +1」の方がお得 「-1,-1,/2」よりも「/2, -1」の方がお…

問題：B - Reversible Cards 解答：Submission #19370578 - AtCoder Regular Contest 111 解法：解説通り、カードに書いてある数字を頂点、カードの数字の組み合わせを辺とするグラフを考えるのがミソ。すると問題は各辺のうち片方の頂点に色付けし、色のつ…

問題：Aizu Online Judge 解答：Aizu Online Judge 解法：一点更新区間加算のセグメント木を使う。タイプ0のクエリ(u, v)は、オイラーツアーとセグメント木を対応させ、オイラーツアーでvが最初に出てくるところに+wし、最後に出てくるところの次で-wする。…

問題：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…