2021年4月の記事一覧
ABC199 F 解答
F - Graph Smoothing(2065)
問題文
N 頂点 M 辺の単純無向グラフがあります。頂点には 1 から N までの、辺には 1 からM までの番号がついています。辺 i は頂点 Xi と頂点 Yi を結んでいます。また、頂点 i には最初整数 Ai が書かれています。
あなたは K 回にわたって以下の操作を行います。
・M 本ある辺の中から、一様ランダムかつ他の選択と独立に
ABC199 E 解答
E - Permutation（1814）
問題文
( 1, 2, 3, … , N )を並び替えてできる数列 a であって、以下の条件を満たすものの数を出力してください。
1 ≤ i ≤M を満たす全ての整数 i について、a1, a2, a3, … ,aXi の中に Yi 以下の数は Zi 個以下しか存在しない
制約
2 ≤ N ≤ 18
0 ≤ M ≤100
1 ≤ Xi <N
1 ≤
ABC199 D 解答
D - RGB Coloring 2 (1804)
問題文
N 頂点 M 辺の単純無向グラフがあります。頂点には 1 からN までの、辺には 1 からM までの番号がついています。
辺 i は頂点 Ai と頂点 Bi を結んでいます。このグラフの各頂点を赤、緑、青の 3 色のいずれかで塗る方法であって、以下の条件を満たすものの数を求めてください。
辺で直接結ばれている 2 頂点は必ず異なる色で塗
ABC199 C 解答
C - IPFL （436）
問題文
長さ 2N の文字列 Sがあります。
この文字列に対して Q 個のクエリが与えられます。
i 番目のクエリでは 3 つの整数 Ti, Ai, Bi が与えられるので、以下の処理をします。
・Ti = 1のとき : S の Ai 文字目と Bi 文字目を入れ替える
・Ti = 2のとき : Sの前半 N 文字と後半 N文字を入れ替える( Ai, Biの値は用い
ABC199 B 解答
B - Intersection（37）
問題文
長さ N の数列 A = (A1, A2, A3, … , AN ), B = ( B1, B2, B3, … , BN)が与えられます。
以下の条件を満たす整数 x の個数を求めてください。
1 ≤ i ≤ N を満たす全ての整数 i について Ai ≤ x ≤ Bi
制約
1 ≤ N ≤ 100
1 ≤ Ai ≤ Bi ≤ 1000
入力
ABC199 A 解答
A - Square Inequality (5)
問題文
整数 A, B, Cが与えられます。
A^2 + B^2 < C^2かを判定してください。
制約
0 ≤ A ≤ 1000
0 ≤ B ≤ 1000
0 ≤ C ≤ 1000
A, B, C は整数である
考察
数式を判定する問題です。ということで、数式を判定してあげましょう。
いきなり結論ですが
if(A*A + B*B
ABC198 E 解答
E - Unique Color(1161)問題文
N 頂点からなる木が与えられます。
i 番目の辺は頂点 Ai と頂点 Bi をつないでいます。頂点 i は色 Ci で塗られています (この問題では、色は整数として表されます)。
頂点 1 から頂点 x への最短パスに、頂点 x と同じ色で塗られた頂点が頂点 x 以外に存在しないとき、頂点 x は よい頂点 であるといいます。
よい頂点を全て求
ABC198 D 解答
D - Send More Money（1224）問題文
英小文字からなる文字列 S1, S2, S3 が与えられます。
覆面算 S1+S2=S3 を解いてください。
正確には、次の 3つの条件をすべて満たすような正の整数の組 N1, N2, N3 が存在するか判定し、存在するならばそのうち 1 つを求めてください。ここで、N1,N2,N3を (先頭に余分な 0 をつけないで) 十進表記した文字
ABC198 C 解答
C - Compass Walking(413)
問題文
2 次元平面上の原点に高橋君がいます。
高橋君が 1 歩歩くと、いまいる点からのユークリッド距離がちょうど R であるような点に移動することができます(移動先の座標が整数である必要はありません)。これ以外の方法で移動することはできません。高橋君が点 ( X, Y )に到達するまでに必要な歩数の最小値を求めてください。なお、点 (x1, y
ABC198 B 解答
B - Palindrome with leading zeros(58)問題文
整数 N が与えられます。N を十進法で表した文字列の先頭に
0 個以上の 0 をつけることで、回文にすることはできますか？
制約
0 ≤ N ≤ 10^9
考察
まず、可能な操作についてです。回文を作るために私たちができるのは
数字の先頭に0をつける
ただこれだけです。となると、作れる回文の種類も自
ABC198 A 解答
A - Div(10)問題文
N 個の互いに区別できないお菓子を、A君とB君で分け合います。 両者とも 1 個以上の整数個のお菓子を得るような分け方は何通りありますか？
制約
N は整数
1 ≤ N ≤ 15
考察
本問題で重要なのは
0個分けてはいけない
ことでしょう。Aさんが0個、BさんがN個という分け方は禁止されています。ですので、分け方は次の通りとなります。
1, N-1