問題：C - ロミオとジュリエット 解答：Submission #10395643 - AtCoder Regular Contest 022 解法：木の直径を求める問題。下記サイトを参考にした。 qiita.com

問題：C - 器物損壊！高橋君 解答：Submission #10395427 - AtCoder Regular Contest 005 解法： BFSしてゆくが、通常のBFSと異なりこれまで壊した壁の数に応じて壁が通れるか通れないかが異なる。なので、壁を壊した数を保持しながら探索する。 適度に枝刈…

問題：C - アットコーダー王国の交通事情 解答：Submission #10395104 - AtCoder Regular Contest 035 解法：N ≦ 400で、N3 = 6.4 * 107なので数回ならワーシャルフロイドが可能。ただしクエリ全てでワーシャルフロイドはできない。 まずはワーシャルフロイ…

問題：C - 無駄なものが嫌いな人 解答：Submission #10394973 - AtCoder Regular Contest 017 解法：半分全列挙。wの前半と後半で作れる数字をmapに保持し、wの前半の全ての数字について、その数字に足すとxになる数字が後半のmapにあるかを調べてゆく。

問題：D - All Your Paths are Different Lengths 解答：Submission #10121089 - AtCoder Regular Contest 102 メモ：解説AC。。 多重辺が許容されているのが重要。Lが2べきの時は、例えば頂点①②③④のようなグラフに対し、①→②に長さ1の辺と0の辺、②→③に長さ2…

問題：D - Forest 解答：Submission #10116025 - AtCoder Petrozavodsk Contest 001 メモ：森がnfor個あったとすると、その森を連結にするにはnfor-1個の辺を追加する必要がある。 このとき、2 * nfor - 2個の頂点を選ぶ必要があり、nfor個の頂点は各木で最…

問題：O - Endurance 解答：Submission #10095653 - 第一回 アルゴリズム実技検定 過去問 メモ： 各試行で現れるサイコロの目を数列にすると、狭義単調増加になる。 特に、全てのサイコロの中で最も大きい目を出すと、その時点で操作終了となる。 サイコロを…

問題：N - Land Clearing 解答：Submission #10067145 - 第一回 アルゴリズム実技検定 過去問 メモ： 車が通る場所を決めると、各石について取り除く必要があるかどうかが一意に決まる。石が[li, ri]にある場合、車が通る場所の左端点が(li - c, ri)となる場…

問題：M - Auto Choice 解答：Submission #10040347 - 第一回 アルゴリズム実技検定 過去問 メモ：蟻本P.132の平均最大化の応用。 平均（1質量あたりの価値）最大化は二分探索の応用で、「C(x)：平均をx以上にできるか」という条件について「 Σ(v[i] - x * w…

問題：L - Gradation 解答：Submission #10039480 - 第一回 アルゴリズム実技検定 過去問 メモ：小さい塔のうち連結するものをあらかじめ決めておき、大きな塔すべてと決めておいた小さい塔の最小全域木の構成コストをクラスカル法で求める。小さい塔の組み…

J - Leveling 概要 H×Wのグリッドが与えられる。各グリッドには非負整数A[i][j]が書かれている。 隣接するグリッドを通って左下マス⇒右下マス⇒右上マスに移動することを考える。このとき、各マスに移動する際は移動先のマスの数字分コストがかかる。ただし、…

問題：F - Many Many Paths 解答：Submission #10018266 - AtCoder Beginner Contest 154 メモ：2項係数の公式に次のようなものがあります。これを使えば一発です。

問題：E - Almost Everywhere Zero 解答：Submission #9994981 - AtCoder Beginner Contest 154 メモ：桁DP。 dp[i][j][l] i：i桁目まで見た j：0じゃない数を何個使ったか l：1なら元の数と等しい、0なら元の数より小さい

問題：H - Bulk Selling 解答：Submission #9963675 - 第一回 アルゴリズム実技検定 過去問 メモ：セット販売、全種類販売を逐一処理していると間に合わない。「全体の最小値」「奇数番目の最小値」「全種類販売の購入数」「セット販売の購入数」を保持して…

問題：Problem - C - Codeforces 解答：Submission #70595567 - Codeforces メモ：ロボットのパスのうち、2回通る座標があれば、2回の間の長さの最小のものを出力する。なので、mapでロボットが通った各座標について、最後に通った時間を記録しておけばよい。…

D - Swap and Flip 概要 カードがN枚ある。i番目のカードの表面には1以上の整数A[i]が、裏面には1以上の整数B[i]がそれぞれ記載されている。 最初、全てのカードが表面を上にして置かれている。この状態から次の操作を好きなだけ繰り返し、見えているカード…

問題：C - 節約生活 解答：Submission #9892233 - AtCoder Regular Contest 007 メモ：2回目以降のテレビをいつから点けるかの全探索。 2020年現在だと300～400点くらい？

問題：D - Greedy customers 解答：Submission #9879171 - CODE FESTIVAL 2016 qual B メモ：小さい数から売ってゆくとよさそう。 最初は1を売ってゆく。最初の数が1になるまで売る。すると次は2を売ることになる。 次の数が5である場合、2を2つ売ると5-4=1…