2021年3月の記事一覧
ABC197 F 解答
F - Construct a Palindrome (1945)問題文
N 頂点 M 辺の、単純とは限らない連結な無向グラフがあります。
辺 i は頂点 A_i と頂点 B_i を結んでおり、文字 C_iが書かれています。
頂点 1 から頂点 N へのパス (同じ辺や頂点を複数回通っても構わない) を 1 つ選び、通る辺に書かれている文字を順に並べて文字列を作ります。
この文字列が回文になるこ
ABC197 E 解答
E - Traveler(1379)問題文
数直線上にボール 1 からボール N までの N 個のボールがあります。ボール i は座標 X_i にあります。各ボールには 1 以上 N 以下の整数で表される色がついていて、ボール i の色は整数 C_i で表されます。
今座標 0 にいるあなたは、毎秒 1 の速さで数直線上を動き、全てのボールを回収してから再び座標 0に戻ります。このとき、ボールの
ABC197 D 解答
D - Opposite (831)問題文
x 軸の正の向きを右、y 軸の正の向きを上とする 2 次元座標平面上に、p_0, p_1, p_2, … , p_(N-1)の N 個の頂点からなる正 N 角形があります。
ここで N は偶数であることが保証され、頂点 p_0, p_1, p_2, … , p_(N-1) はこの順に反時計回りに並んでいます。p_i の座標を(x_i, y_i) としま
ABC197 C 解答
C - ORXOR (809)問題文
長さ N の数列 A が与えられます。この数列を、1 つ以上の空でない連続した区間に分けます。その後、分けた各区間で、区間内の数のビット単位 OR を計算します。こうして得られた全ての値のビット単位 XOR
として考えられる最小値を求めてください。
制約
1 ≤ N ≤20
0 ≤ A_i < 2^30
入力に含まれる値は全て整数である
考察
まず、
ABC197 B 解答
B - Visibility(96)問題文
縦 H 行、横 W 列のマス目があり、いくつかのマスには障害物が置かれています。上から i 番目、左から j 番目のマスをマス(i, j)と表すことにします。
H 個の文字列 S_1, S_2, S_3, … , S_H が与えられます。S_i の j 文字目はマス (i, j)の状態を表し、'#' なら障害物が置かれていることを、'.' なら障害物が
ABC197 A 解答
A - Rotate (6)問題文
長さ 3 の文字列 S が与えられます。
S の先頭の文字を S の末尾に移動して得られる文字列
S′を出力してください。
制約
S は英小文字のみからなる長さ3の文字列である
考察
s は3文字であることがわかっていますので、それを使って簡単に実装してしまいましょう。C++では、string型の文字列は配列のように i 番目の文字にアクセすることが
ABC196 F 解答
F - Substring 2 (2274)問題
0, 1 からなる文字列 S, T が与えられます。
T が S の部分文字列となるように、Tのいくつかの文字を書き換えます。
少なくとも何文字書き換える必要がありますか？
制約
S, T は 0, 1 からなる
1 ≤ |T| ≤ |S| ≤ 10^6
考察
本問題はFFT（高速フーリエ変換）を用いて解きました。しかし、本記事ではFFT
ABC196 E 解答
E - Filters (1650)問題文
整数列 A = (a_1, a_2, … ,a_N), T = (t_1, t_2, … , t_N), X = (x_1, x_2, … , x_Q)が与えられます。N 個の関数 f_1(x), f_2(x),…, f_N(x)を、
f_i (x) =
x+a_i (t_i = 1)
max(x, a_i) (t_i = 2)
min(x, a_i
ABC196 D 解答
D - Hanjo (1277)問題文
縦 H メートル、横 W メートルの長方形の部屋があります。
この部屋に 2 メートル × 1メートルの区別できない畳 (長方形のタイル) A 枚と、1メートル × 1メートルの区別できない半畳 (正方形のタイル) B枚を敷き詰めます。2メートル × 1メートルの畳は縦長にも横長にも使うことができます。敷き詰める方法は何通りあるでしょうか？
なお、2A+B
ABC196 C 解答
C - Doubled (244)
問題文
整数 N が与えられます。
以下の条件を満たす 1 以上 N 以下の整数 x は何個あるでしょうか？
・x の十進表記 (先頭に 0 を付けない) は偶数桁であり、その前半と後半は文字列として等しい。
制約
N は整数
1 ≤ N < 10^12
考察
本問題の考え方として次の2つがあると思います。
・ N 以下の数において条件を満たすも
ABC196 B 解答
B - Round Down (39)問題文
整数または小数 X が与えられるので、小数点以下を切り捨てて整数で出力してください。
制約
・0 ≤ X ≤10^100
・X は整数、または小数点以下が 100桁以下の小数であり、先頭に余計な 0 は付かない
考察
型をうまく扱う問題ですね。これは言語によって可能な方針が異なると思います。本記事ではC++で可能な手法で解いています。
整数
ABC196 A 解答
A - Difference Max (9)問題文
整数 a, b, c, dが与えられます。
a ≤ x ≤ b, c ≤ y ≤ d となるように整数 x, y を選ぶとき、x−y の最大値を求めてください。
制約
入力は全て整数
−100 ≤ a ≤ b ≤ 100
−100 ≤ c ≤ d ≤ 100
考察
計算式を考えて、ぱっと答えを求めてしまいましょう。
本問題では
x
ABC195Fの解答
F - Coprime Present (2068)
問題文
あなたは A 以上 B 以下の整数が書かれたカードを各 1 枚、合計 A 以上 B 以下の整数が書かれたカードを各 1 枚、計 B−A+1 枚持っています。 この中から何枚かを選んで (0枚でもよい) ペットのすぬけ君にプレゼントしようと考えています。
すぬけ君は、プレゼントされたカードたちについて、どの相異なる 2 枚に書かれた数も
ABC195Eの解答
E - Lucky 7 Battle (1609)問題文
0, … ,9 からなる長さ N の文字列 S と、A,T からなる長さN の文字列 X が与えられます。また、空文字列で初期化された文字列 T があります。
高橋君と青木君がこれらを使ってゲームをします。ゲームは N ラウンドからなり、i 回目 (1 ≤ i ≤ N )のラウンドでは次の操作が行われます。
・X_i が A なら青木君が