記事一覧
ABC210 E 解答
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
ABC210 D 解答
D - National Railway（1507）
問題
問題文
高橋王国は H 行 W 列のグリッドで表されます。北から i 行目、西から
j 列目のマスを(i, j)で表します。
このたび、高橋王国の国民から交通の利便性のために鉄道の建設を求める声が多数寄せられ、国王の高橋君は鉄道を建設しなければならなくなりました。
鉄道建設は以下の 2 つのステップからなります。
まず、2 つの異な
ABC210 C 解答
問題
問題文
N 個のキャンディが左右一列に並んでいます。
それぞれのキャンディは、色1、色2、…、色10^9の、10^9種類の色のうちいずれかの色をしています。
i=1,2,…,Nについて、左から i 番目のキャンディの色は色 ci です。
高橋君は並んでいるキャンディのうち、連続して並んだ K 個のキャンディをもらうことができます。
すなわち、1≤i≤N−K+1を満たす整数 i を選んで、
ABC210 B 解答
問題
問題文
N 枚のカードからなる山札があります。
それぞれのカードは、「良いカード」か「悪いカード」かのどちらかです。高橋君と青木君は、この山札を使って対戦ゲームをします。このゲームでは、2 人は交互に山札の一番上のカードを引いて、そのカードを食べます。
先に悪いカードを食べたプレイヤーの負けです。（ここで、山札には少なくとも 1 枚の悪いカードが含まれていることが保証されます。）
0 と
ABC210 A 解答
問題
問題文
高橋君はキャベツ屋さんにやってきました。
キャベツ屋さんでは、 キャベツを 1 個 X 円で買うことができます。
ただし、キャベツを A 個よりも多く買う場合、A+1 個目以降に買うキャベツについては 1 個 Y 円で買うことができます。（ここで、Y < X が保証されます。）
高橋君がキャベツを N 個買うために必要な金額を出力してください。
制約
1 ≤ N ≤ 10^5
ABC209 F 解答
F - Deforestation（2307）
問題
問題文
N 本の木が左右一列に並んでおり、左から i ( 1≤ i ≤ N ) 本目の木 i の高さは
Hi です。
あなたは、好きな順番でこれら N 本の木を全て伐採します。具体的には、
( 1, 2, … ,N ) の並び替えによって得られるある順列 P について、i = 1, 2, 3, ... , N の順に、H_{P_{i−1
ABC209 E 解答
E - Shiritori（2153）
問題
問題文
高橋辞書には N 個の単語が載っており、i ( 1 ≤ i ≤ N ) 番目の単語は si
です。高橋君と青木君は高橋辞書を使って 3 しりとりをします。 3 しりとりのルールは以下です。
・高橋君と青木君は、高橋君から始めて交互に単語を言い合っていく。
・各プレーヤーは前の人が言った単語の最後の 3 文字で始まる単語を言わなければならない
ABC209 D 解答
D - Collision（686）
問題
問題文
高橋王国は N 個の街と N−1 本の道路からなり、街には 1 から N の番号がついています。また、i ( 1 ≤ i ≤ N−1 ) 本目の道路は街 ai と街 bi を双方向に結んでおり、どの街からどの街へもいくつかの道路を通ることで移動できます。道路は全て同じ長さです。
Q 個のクエリが与えられます。 i ( 1 ≤ i ≤ Q )
ABC209 C 解答
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 ≤
ABC209 B 解答
B - Can you buy them all?（13）
問題
問題文
高橋商店では N 個の商品が売られています。i (1 ≤ i ≤ N ) 番目の商品の定価は Ai円です。今日はセールが行われており、偶数番目の商品は定価の 1 円引きの値段で買うことができます。奇数番目の商品は定価で売られています。
あなたの所持金は X 円です。これら N 個の商品を全て買うことができますか？
制
ABC209 A 解答
A - Counting（5）問題
問題文
A 以上かつ B 以下の整数はいくつありますか？
制約
1 ≤ A ≤ 100
1 ≤ B ≤ 100
A, B は整数である。
考察
A 以上、 B 以下の数を求めます。シンプルな問題文ですね。AからBまでfor文を回してあげても求めることができますが、せっかくなので計算で求める方法を説明していきます。
説明すると言いましても、BからAを
ABC208 F 解答
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)で割った余りを求めてください。
制約
ABC208 E 解答
E - Digit Products（2024）問題
問題文
N 以下の正の整数のうち、各桁の数字の積が K 以下であるものは何個ありますか？
制約
1 ≤ N ≤ 10^18
1 ≤ K ≤ 10^9
入力は全て整数である。
考察
桁DPをやりましょう。というメッセージが伝わってきますので、それに従います。桁DPを考えていきます。
今回は最も工夫をしない単純な3次元dpにて解いて
ABC208 D 解答
D - Shortest Path Queries 2（1190）問題
問題文
高橋王国には N 個の都市と M 本の道路があります。
都市には 1 から N の番号が、道路には 1 から M の番号が割り振られています。道路 i は都市 Ai から Bi へ向かう一方通行の道で、移動するのに Ci 分かかります。
f (s, t, k) を次のクエリへの答えとして定めます。
・都市 s を出