問題：Problem - D - Codeforces 解答：Submission #74875019 - Codeforces 解法：解説AC。配列Tの長さの偶奇が本質的。 まず、全ての要素が同じ場合は、全部1としてよい。これ以降は、配列Tの中の（n-1→0を含めた）隣接2項で異なる要素があるため、少なくと…

問題：C - eject 解答：Submission #11256765 - CODE FESTIVAL 2014 Middle 解法：2項係数の問題、なんだけど浮動小数点の取扱いが難しい。 cmathのpowを使う、long doubleにする、でうまくいった。（リテラルちゃんとする、もあるかもしれない。）

問題：D - 高橋くんと数列 解答：Submission #11255665 - Indeedなう（予選B） 解法：数字xについて愚直に(l, r)の組を数えることを考える。lごとに該当するrの数を数えるとする。 a[l] = x：r = l からnまでがxを含む部分列になる。 a[l] ≠ x：l' > lかつ a…

問題：B - Password 解答：Submission #11252972 - DigitalArts プログラミングコンテスト2012 解法：aもしくはz*20の場合は同じハッシュ値を持つパスワードがないのでNO。それ以外は次のように生成する。 ①1文字でa以外：1文字をXとすると(X -1)aの2文字と…

問題：B - ヘイホー君と削除 解答：Submission #11251025 - CODE FESTIVAL 2015 あさぷろ Middle 解法：文字列sをある場所を区切って文字列aとbに分割する。aで平方の前半、bで平方の後半を作るとする。このとき作れる平方文字の最大長はaとbのLCS（最長部分…

問題：B - ディスコ社内ツアー 解答：Submission #11247515 - DISCO presents ディスカバリーチャンネル プログラミングコンテスト2016 予選 解法：見ていく順番は一意に決まるので何周するかを求めればよいが、Nに関するループの繰り返しにするとTLE。 同じ…

問題：B - DDPC特別ビュッフェⅡ 解答：Submission #11246595 - DISCO presents ディスカバリーチャンネル プログラミングコンテスト2016 本選 解法：「時刻tで美味しさの総和がX以上になるか」という二分探索をする。二分探索内の条件判定では、時刻tからさ…

問題：C - だれじゃ 解答：Submission #11167793 - AtCoder Regular Contest 024 解法： s[i : j]をsのi+1文字目からj文字目までの部分文字列とする。マッチングをチェックするのは以下の範囲。 s[k : 2k]はs[0 : k]をチェック s[k+1 : 2k+1]はs[0 : k], s[1…

問題：B - 123 Triangle 解答：Submission #11073495 - AtCoder Grand Contest 043 解法：a[i]を-1して各要素を0, 1, 2で考える。各ステップに現れる数字も0, 1, 2のいずれかであり、最終的な数字も0, 1, 2のいずれかである。 ここで、次のような場合分けが…

問題：A - Range Flip Find Route 解答：Submission #11068021 - AtCoder Grand Contest 043 解法：DFSしてゆく。白から黒に移動するときにカウントアップする。各マスのカウントの最小値を保持して枝刈りする。

問題：C - 行列のできるドーナツ屋 解答：Submission #11037583 - Donutsプロコンチャレンジ2015 解法：スタックを準備し、数列を前から見てゆく。人iについて出力するのはその人より前でできている狭義単調減少列の長さであり、その単調列をスタックに格納…

問題：C - 身体バランス 解答：Submission #11036772 - CODE FESTIVAL 2014 Easy 解法：sからとtからでそれぞれダイクストラし、d1[u] == d2[u]かつd1[u] < INFであるものがあれば、uを出力する。

問題：B - Tokyo 7th シスターズ 解答：https://atcoder.jp/contests/donuts-2015/submissions/11032269 解法：bit全探索で全てのユニットの組み合わせを試せばよい。計算量は216 * 50 * 9 = 29491200で何とか間に合う。

問題：C - 錬金術士 解答：Submission #11032114 - CODE FESTIVAL 2014 予選B 解法：まず、各文字種('A' - 'Z')について、S1内の個数とS2内の個数の和がS3内の個数より小さいものがあれば、NOを出力。全ての場合でそうでないなら、「S1から何個、S2から何個…

問題：B - 天下一後入れ先出しデータ構造 解答：Submission #10994449 - 天下一プログラマーコンテスト2013予選B 解法：Stackされる数とその個数をそれぞれ管理するスタック(snum, scnt)を準備し、Push・Pop命令は1つのクエリをまとめて処理する。

問題：D - 登山家 解答①：Submission #10974270 - CODE FESTIVAL 2014 予選B 解答②：Submission #10977004 - CODE FESTIVAL 2014 予選B 解答③：Submission #10993670 - CODE FESTIVAL 2014 予選B 解法：i番目の山小屋について、その山小屋より左側、右側でそ…

問題：C - 仲良し文字列 解答：Submission #10929382 - Code Formula 2014 予選B 解法：1回のスワップでab間の異なる文字が同じになるのは高々2文字なので、7文字以上異なる場合はその時点でNO。6文字であれば3回スワップしても計算量は66=46636で間に合う。…

問題：C - 木 解答：Submission #10920720 - Indeedなう（予選B） 解法：dfsで各頂点を探索していく。いったん隣接頂点を全て確認した後、それをpriority_queueに格納しておき、次に探索するのはpriory_queueの中の最小の頂点とする。

問題：B - エターナルスタティックファイナル 解答：Submission #10902648 - 天下一プログラマーコンテスト2014予選B 解法：dp[i]をi文字目までを作るときの作り方の通り数とする。 元の文字列sのi文字目について、全ての文字列の候補でマッチするかどうかを…

問題：Problem - E - Codeforces 解答：Submission #73178165 - Codeforces 解法：dp[i][j]をi回目の睡眠で睡眠開始がjであるときのgood睡眠の最大値とする。 このときi回目で睡眠開始がj であるとき、i+1回目の睡眠開始はj + a[i]もしくはj + a[i] - 1なの…

問題：Problem - D - Codeforces 解答：Submission #73177810 - Codeforces 解法：ai + aj > bi + bj ⇔ ai - bi > aj - bj よりci = ai - bi とし、ci > cjとなる(i, j)の個数を探す。 cを昇順ソートする。iとjを逆にし、ci < cj (i < j)を探す。 ci > 0 で…

問題：E - LISDL 解答１（通常座圧）：Submission #10767274 - AtCoder Regular Contest 091 解答２（自前計算座圧）：Submission #10767259 - AtCoder Regular Contest 091 解法：次のような2次元マトリクスを考える。 このマトリクスから次のようにN個の数…

問題：C - ThREE 解答：Submission #10717648 - Social Infrastructure Information Systems Division, Hitachi Programming Contest 2020 解法：piとpjの和または積が3の倍数であることは、「pi, pjが1 (mod 3), 2(mod 3)のそれぞれどちらか」または「pi, p…

問題：E - Divisible Substring 解答：Submission #10651412 - AtCoder Beginner Contest 158 解法：解説AC。 s[i: j]をsのi文字目からj文字目までの部分文字列を評価した整数とする。するとs[i: j] = (s[i: N] - s[j+1: N]) / 10j - i +1であることが重要。…

問題：C - Removing Coins 解答：Submission #10579618 - AtCoder Grand Contest 033 解法：木の直径に注目すると、直径の端点を選んだ場合は直径が1減少し、それ以外の点を選んだ場合は直径が2減少する。 よってこのゲームは「木の直径から1または2を交互に…

問題：C - ウサギ跳び 解答：Submission #10535617 - AtCoder Regular Contest 041 解法：左の壁から連続するLと右の壁まで連続するRについては、壁（もしくは先にいるウサギ）に突き当たるまで進ませる。 R...RL...Lになっている並びのウサギを考える。まず…

問題：D - Pair Cards 解答：Submission #10528447 - CODE FESTIVAL 2016 Final 解法：mod Mごとに数をグループ分けする。ペアの作り方は下記の3通り。 同じ数同士でペアを作る 同じグループの違う数同士でペアを作る 異なるグループの数同士でペアを作る グ…

問題：B - GCD Sequence 解答：Submission #10499621 - AtCoder Grand Contest 022 解法：解説AC。 aiの和をSとすると、gcd(ai, S) > 1 でgcd(a1, a2, ..., an) = 1を満たすaiの構築をすればよい。 制約がN ≦ 20000、ai ≦ 30000であり、N = 20000の時は30000…

問題：C - 最高のトッピングにしような 解答①：Submission #16192313 - AtCoder Regular Contest 027 解法①：スペシャルチケットがx枚であるときは、x種類までしか品物を選ぶことができない。逆に、x種類までで品物を選ぶとしたらその中では通常のチケットと…

問題：E - Simple String Queries 解答：Submission #10469785 - AtCoder Beginner Contest 157 解法： 各アルファベットに対応する長さnのセグ木を作り、s[i]がそのアルファベットなら+1、そうでないなら0とする。 クエリ1は変更前、変更後のアルファベット…