E - Ring MST（1610）
問題
問題文
N 個の頂点と 0 本の辺からなる無向グラフがあります。 N 個の頂点をそれぞれ頂点 0、頂点 1、頂点 2、…、頂点 N − 1 と呼びます。
このグラフに対する M 種類の操作を考えます。
i = 1 , 2, … , M について、i 番目の操作は「 0 ≤ x < N を満たす整数 x を選び、頂点 x と頂点 (x+Ai ) mod N を結ぶ無向辺を追加する」という操作です。ただし、a mod b は a を
ABC210 D 解答
D - National Railway（1507）
問題
問題文
高橋王国は H 行 W 列のグリッドで表されます。北から i 行目、西から
j 列目のマスを(i, j)で表します。
このたび、高橋王国の国民から交通の利便性のために鉄道の建設を求める声が多数寄せられ、国王の高橋君は鉄道を建設しなければならなくなりました。
鉄道建設は以下の 2 つのステップからなります。
まず、2 つの異なるマスを選び、それぞれに駅を建設する。マス (i, j) に駅を建設すると Ai
ABC210 C 解答
問題
問題文
N 個のキャンディが左右一列に並んでいます。
それぞれのキャンディは、色1、色2、…、色10^9の、10^9種類の色のうちいずれかの色をしています。
i=1,2,…,Nについて、左から i 番目のキャンディの色は色 ci です。
高橋君は並んでいるキャンディのうち、連続して並んだ K 個のキャンディをもらうことができます。
すなわち、1≤i≤N−K+1を満たす整数 i を選んで、 左から i 番目、i+1番目、i+2番目、…、i+K−1番目のキャンディをもら
ABC210 B 解答
問題
問題文
N 枚のカードからなる山札があります。
それぞれのカードは、「良いカード」か「悪いカード」かのどちらかです。高橋君と青木君は、この山札を使って対戦ゲームをします。このゲームでは、2 人は交互に山札の一番上のカードを引いて、そのカードを食べます。
先に悪いカードを食べたプレイヤーの負けです。（ここで、山札には少なくとも 1 枚の悪いカードが含まれていることが保証されます。）
0 と 1 からなる文字列 S が与えられます。i = 1, 2, … , N につい
問題
問題文
高橋君はキャベツ屋さんにやってきました。
キャベツ屋さんでは、 キャベツを 1 個 X 円で買うことができます。
ただし、キャベツを A 個よりも多く買う場合、A+1 個目以降に買うキャベツについては 1 個 Y 円で買うことができます。（ここで、Y < X が保証されます。）
高橋君がキャベツを N 個買うために必要な金額を出力してください。
制約
1 ≤ N ≤ 10^5
1 ≤ A ≤ 10^5
1 ≤ Y < X ≤ 100
入力はすべて整数
F - Deforestation（2307）
問題
問題文
N 本の木が左右一列に並んでおり、左から i ( 1≤ i ≤ N ) 本目の木 i の高さは
Hi です。
あなたは、好きな順番でこれら N 本の木を全て伐採します。具体的には、
( 1, 2, … ,N ) の並び替えによって得られるある順列 P について、i = 1, 2, 3, ... , N の順に、H_{P_{i−1}}+H_{P_{i}}+H_{P_{i+1}} のコストを支払った後、木 Pi
D - Collision（686）
問題
問題文
高橋王国は N 個の街と N−1 本の道路からなり、街には 1 から N の番号がついています。また、i ( 1 ≤ i ≤ N−1 ) 本目の道路は街 ai と街 bi を双方向に結んでおり、どの街からどの街へもいくつかの道路を通ることで移動できます。道路は全て同じ長さです。
Q 個のクエリが与えられます。 i ( 1 ≤ i ≤ Q )番目のクエリでは整数 ci, di が与えられるので、以下の問題を解いてください
C - Not Equal（285）
問題
問題文
長さ N の整数列 C が与えられます。以下の条件を全て満たす長さ N の整数列 A の個数を求めてください。
・1 ≤ Ai ≤ Ci ( 1 ≤ i ≤N )
・Ai ≠ Aj ( 1 ≤ i < j ≤ N )
ただし、答えは非常に大きくなる可能性があるので、( 10^9+7 )で割った余りを出力してください。
制約
1 ≤ N ≤ 2×10^5
1 ≤ Ci ≤ 10^9
入力は全て整数
考察
条件を満た
B - Can you buy them all?（13）
問題
問題文
高橋商店では N 個の商品が売られています。i (1 ≤ i ≤ N ) 番目の商品の定価は Ai円です。今日はセールが行われており、偶数番目の商品は定価の 1 円引きの値段で買うことができます。奇数番目の商品は定価で売られています。
あなたの所持金は X 円です。これら N 個の商品を全て買うことができますか？
制約
1 ≤ N ≤ 100
1 ≤ X ≤ 10000
1 ≤ Ai ≤ 10
A - Counting（5）問題
問題文
A 以上かつ B 以下の整数はいくつありますか？
制約
1 ≤ A ≤ 100
1 ≤ B ≤ 100
A, B は整数である。
考察
A 以上、 B 以下の数を求めます。シンプルな問題文ですね。AからBまでfor文を回してあげても求めることができますが、せっかくなので計算で求める方法を説明していきます。
説明すると言いましても、BからAを引くだけです。ただし、次の２点に注意です。
１）計算は植木算になる
A以上B
F - Cumulative Sum（2772）
問題
問題文
非負整数 n, mに対して関数
f(n,m) を正の整数 Kを用いて次のように定めます。
f(n, m)
= 0 (n=0)
n^k (n>0,m=0)
f(n-1,m)+f(n,m-1) (n>0,m>0)
N, M, K が与えられるので、
f(N, M) を (10^9+7)で割った余りを求めてください。
制約
0 ≤ N ≤ 10^18
0 ≤ M ≤ 30
1 ≤ K ≤ 2.5×10^
E - Digit Products（2024）問題
問題文
N 以下の正の整数のうち、各桁の数字の積が K 以下であるものは何個ありますか？
制約
1 ≤ N ≤ 10^18
1 ≤ K ≤ 10^9
入力は全て整数である。
考察
桁DPをやりましょう。というメッセージが伝わってきますので、それに従います。桁DPを考えていきます。
今回は最も工夫をしない単純な3次元dpにて解いていきます。dpの構成は次の通りです。
dp[ i ] [ j ][ t ]:
D - Shortest Path Queries 2（1190）問題
問題文
高橋王国には N 個の都市と M 本の道路があります。
都市には 1 から N の番号が、道路には 1 から M の番号が割り振られています。道路 i は都市 Ai から Bi へ向かう一方通行の道で、移動するのに Ci 分かかります。
f (s, t, k) を次のクエリへの答えとして定めます。
・都市 s を出発して都市 t に到着するまでの最短時間を計算してください。ただし、通ってよい都
