2021年6月の記事一覧
ABC206 F 解答
F - Interval Game 2（2221）
問題
問題文
T 個のテストケースについて、以下の問題を解いてください。
N 個の半開区間 [Li, Ri) ( 1 ≤ i ≤ N ) があり、 Alice と Bob がこの区間を使って次のようなゲームをします。
Alice から始めて、以下の操作を交互に行う。N 個の区間の中から、既に選ばれているどの区間とも共有点をもたない区間を 1
ABC206 E 解答
E - Divide Both（1745）問題
問題文
整数 L, R ( L ≤ R ) が与えられるので、以下の条件を全て満たす整数組
( x, y )の数を求めてください。
・L ≤ x, y ≤ R
・g を x, y の最大公約数とすると、以下が成立する。
g ≠ 1 かつ x / g ≠ 1 かつ y / g ≠1
制約
入力は全て整数
1 ≤ L ≤ R ≤ 10^6
ABC206 D 解答
D - KAIBUNsyo（879）
問題
問題文
N 項からなる正整数列 A = (A1, A2, … AN )が与えられます。
以下の操作を 0 回以上何度でも行える時、操作を最小何回行えば、Aを回文にすることができますか？
ある正整数の組 (x, y) を選ぶ。その後、現在 A に含まれる x をすべて y に置き換える。
なお、この問題では、全ての整数 i ( 1≤ i ≤ N )
ABC206 C 解答
C - Swappable（171）
問題
問題文
N 個の整数からなる配列 A = (A1, A2, ... , AN)
が与えられるので、次の条件を全て満たす整数組 (i, j)の数を求めてください。
・1 ≤ i < j ≤ N
・Ai≠Aj
制約
入力は全て整数
2 ≤ N ≤ 3×10^5
1 ≤ Ai ≤ 10^9
考察
異なる数字の組み合わせを数え上げます。本問題を特に工
ABC206 B 解答
B - Savings（14）
問題
問題文
シカのAtCoDeerくんは、空の貯金箱を持っています。
AtCoDeerくんは、その貯金箱に、1 日目の朝に 1 円、2 日目の朝に 2 円 … というように、i 日目の朝に i 円を貯金箱に入れます。
また、AtCoDeerくんは、毎日夜に貯金箱にいくら入っているかを確認します。AtCoDeerくんが貯金箱に N 円以上入っていることを初めて確
ABC206 A 解答
A - Maxi-Buying（5）
問題
問題文
ABC 国の消費税率は 8 パーセントです。
ABC 国にはエナジードリンク屋さんがあります。ここでは、エナジードリンク 1 本を、税抜き N 円で販売しています。
ここに消費税を加算した後の金額は ⌊1.08×N⌋ 円となります。ただし、実数 x に対し、⌊x⌋ は x 以下の最大の整数を表します。
この金額が定価の 206 円より安いなら
ABC204 D 解答
D - Cooking（832）問題
問題文
高橋君は料理 1 から N の N 品の料理を作ろうとしています。
料理 i はオーブンを連続した Ti 分間使うことで作れます。1 つのオーブンを
2 つ以上の料理のために同時に使うことはできません。
2 つのオーブンを使えるとき、N 品の料理を全て作るまでに最短で何分かかりますか？ なお、オーブンを使う時間以外は無視できるものとします。
制
ABC204 C 解答
C - Tour（629）問題
問題文
AtCoder 国には 1 から N の番号がついた N 個の都市と、1 からM の番号がついた M 個の道路があります。
道路 i を通ると都市 Ai から Bi へ移動することができます。都市 Bi から都市
Ai への通行はできません。
ピューマは、どこかの都市からスタートし、0 本以上の道路を使い移動して、どこかの都市をゴールとするような旅行の
ABC204 B 解答
B - Nuts（9）問題
問題文
N 本の木があり、i 番目の木には Ai 個の木の実が実っています。
シマリスは、次のルールで全ての木から木の実を収穫します。
・実っている木の実が 10 個以下の木からは木の実を収穫しない
・実っている木の実が 10 個より多い木からは、10 個を残して残りの全てを収穫する
シマリスが収穫する木の実の個数の合計を求めてください。
制約
1 ≤ N ≤
ABC204 A 解答
A - Rock-paper-scissors（7）問題
問題文
サーバル、フェネック、アライグマの 3 人がじゃんけんをして、あいこになりました。
フェネックが出した手を表す文字 x とアライグマが出した手を表す文字
y が与えられます。それぞれ、0 はグー、1 はチョキを、2 はパーを表します。
サーバルが出した手を表す文字を出力してください。なお、答えは一意に定まります。
制約
x
ABC203 E 解答
E - White Pawn（1750）問題
問題文
N を正の整数とします。 行と列にそれぞれ 0 から 2N までの番号が付いた
(2N+1)×(2N+1)のマス目があり、行 i かつ列 j に属するマスを ( i, j )で表します。
白のポーンが 1 つあり、最初(0, N)に置かれています。 黒のポーンは M 個あり、i 個目の黒のポーンは (Xi, Yi) に置かれています。
白
ABC203 D 解答
D - Pond（1622）問題
問題文
AtCoder 公園の敷地は東西南北に広がる N×N のマス目からなっており、北から i 番目かつ西から j 番目のマスの高さは Ai, j で与えられます。
公園の管理者である高橋君はここに K×K の区画の池を作る事にしました。
池を作るにあたって、高橋君は AtCoder 公園の敷地内に完全に含まれる K×K の区画であってその区画に含まれるマス
ABC203 C 解答
問題
問題文
10^100+1 個の村があり、それぞれ村0, 村1, … , 村10^100と番号がついています。0 以上 10^100−1 以下の全ての整数 i について、村 i で 1 円を払う事で村 (i + 1)に移動することができます。 それ以外の移動方法はありません
太郎君は初め K 円を持った状態で村 0 におり、その後、可能な限り大きな番号の村まで進もうとします。
太郎君には
ABC203 B 解答
B - AtCoder Condominium（12）
問題
問題文
AtCoder マンションは 1 階から N 階までの N 階建てのマンションです。 各階には K 室の部屋があり、1 号室から K 号室まで番号が振られています。
ここで N, K は 1 桁の整数であり、i 階の j 号室の部屋番号は i0j で表されます。 例えば、1 階の 2 号室の部屋番号は 102 です。
マンシ