2021年5月の記事一覧
ABC202 E 解答
E - Count Descendants（1638）
問題
問題文
N 頂点の根付き木があり、頂点は 1, 2, … , Nと番号付けられています。
頂点 1 が根であり、頂点 i ( 2 ≤ i ≤ N ) の親は Pi です。
Q 個のクエリが与えられます。i ( 1 ≤ i ≤ Q ) 番目のクエリでは、整数 Ui, Diが与えられるので、次の条件を全て満たす頂点 u の個数を求めてく
ABC202 D 解答
D - aab aba baa（966）
問題
問題文
A 個の a と B 個の b からなる長さ A+B の文字列のうち、辞書順で K 番目のものを求めてください。
制約
1 ≤ A, B ≤ 30
A 個の a と B 個の b からなる長さ A + B の文字列の総数を S 個とおいたとき、1 ≤ K ≤ S
入力は全て整数である。
考察
辞書順の問題です。
ABCのD問題で
ABC202 C 解答
C - Made Up（204）
問題
問題文
1 以上 N 以下の整数からなる長さ N の数列
A = ( A1, A2, … , AN ), B = ( B1, B2, … , BN ), C = ( C1, C2, … , CN ) が与えられます。
1 以上 N 以下の整数 i, j の組 ( i, j ) であって、 Ai = B_{Cj} となるものの総数を求めてください。
制
ABC202 B 解答
B - 180°（１６）
問題
問題文
0、1、6、8、9 からなる文字列 S が与えられます。
S を 180 度回転したものを出力してください。すなわち、S に次の操作を施してできる文字列を出力してください。
S を反転する。0 を 0 に、1 を 1 に、6 を 9 に、8 を 8 に、9 を 6 に変換する。
制約
1 ≤ |S| ≤ 10^5
S は 0、1、6、8、9 からなる
ABC202 A 解答
A - Three Dice（４）
問題
問題文
高橋君が 3 つのサイコロを振ったところ、出た目はそれぞれ a, b, c でした。これらのサイコロについて、出た目とは反対の面が表す整数を足し合わせた値を求めてください。
ただし、高橋君が振るサイコロは全て一般的な立方体の 6 面ダイスであり、ある面とその反対側の面が表す整数を足すと 7 になります。
制約
1 ≤ a, b, c ≤ 6
ABC201 F 解答
F - Insertion Sort（2484）
問題
問題文
1 から N までの番号が振られた N 人の人が左右一列に並んでいます。はじめ、左から i 番目の人の番号は Pi です。
あなたの目標は、以下の 3 種類の操作を繰り返すことで人々が左から番号の昇順で並んでいるようにすることです。これらの操作は、任意の順に何回でも（ 0 回でもよい）行うことができます。
・整数 i ( 1 ≤
ABC201 E 解答
E - Xor Distances（1694）
問題
問題文
N 頂点の重み付き木があります。i 本目の辺は頂点 ui と頂点 vi を双方向に結んでいて、その重みは wi です。頂点の組 ( x, y ) について、dist ( x, y ) を以下のように定めます。
・x から y への最短パスに含まれる辺全ての重みの XOR
1 ≤ i < j ≤ N を満たす全ての組 ( i, j
ABC201 D 解答
D - Game in Momotetsu World（1317）問題
問題文
H 行 W 列のマス目があり、各マスは青マスまたは赤マスのどちらかです。上から i 番目、左から j 番目のマスは、Ai, j が + なら青マスであり、- なら赤マスです。
最初、このマス目の一番左上のマスに一つ駒が置かれていて、高橋君と青木君はこの駒を使ってゲームをします。
2 人の得点は最初 0 点ずつです。
ABC201 C 解答
C - Secret Number（439）
問題
問題文
高橋くんは、暗証番号を忘れてしまいました。暗証番号は 0 から 9 までの数字のみからなる 4 桁の文字列で、0 から始まる場合もあります。
0 から 9 までの各数字について、高橋くんは以下のように記憶しています。彼の記憶は長さ 10 の文字列 S0S1 … S9 によって表されます。
・Si が o のとき : 数字 i は暗証番
ABC201 B 解答
B - Do you know the second highest mountain?（32）
問題
問題文
AtCoder国には N 個の山があり、i 個目の山の名前は Si, 高さは Ti です。
2 番目に高い山の名前を答えてください。N 個の山の名前、高さはそれぞれ相異なることが保証されます。
制約
2 ≤ N ≤ 1000
1 ≤ ( Si の長さ ) ≤ 15
1 ≤ Ti
ABC201 A 解答
A - Tiny Arithmetic Sequence（12）
問題
問題文
長さ 3 の数列 A = ( A1, A2, A3 )が与えられます。
A を適切に並び替えて等差数列にすることはできますか？
即ち、A3−A2 = A2−A1を満たすように A を並び替えることはできますか？
制約
1 ≤ Ai ≤100
入力は全て整数
考察
長さ３の数列を並べ替えて条件を満たすかどうか
ABC200 F 解答
F - Minflip Summation （2556）問題
問題文
0, 1, ? のみからなる文字列 S があります。この文字列を K 個連結したものを
T とします。
この文字列の ? を全て 0 か 1 に置き換えた文字列は、S の中に含まれる ? の数を q 個とすると、全部で 2^{Kq} 通り考えられますが、その全てについて以下の問題を解いて、その答えの和を ( 10^9+7
ABC200 E 解答
E - Patisserie ABC 2（1955）問題
問題文
「ABC洋菓子店」で働くパティシエである高橋君は、ケーキを作って AtCoder Beginner Contest 200 を祝うことにしました。
高橋君の作るケーキは、「綺麗さ」「おいしさ」「人気度」の 3 つのパラメータをもち、それぞれのパラメータは 1 以上 N 以下の整数で表されます。
高橋君は、「綺麗さ」が i、「おい
ABC200 D 解答
D - Happy Birthday! 2（1217）問題
問題文
N 個の正整数からなる数列 A = ( A1, A2, … , AN )が与えられます。 以下の条件を全て満たす 2 つの数列 B = ( B1, B2, … , Bx ), C = ( C1, C2, … , Cy )が存在するか判定し、存在する場合はひとつ出力してください。
・1 ≤ x, y ≤ N
・1 ≤ B1 <