2023-12-01から1ヶ月間の記事一覧
AtCoder Beginner Contest 333 (ABC333) のF問題 (Bomb Game 2) の解説記事です。
AtCoder Beginner Contest 333 (ABC333) のE問題 (Takahashi Quest) の解説記事です。
AtCoder Beginner Contest 333 (ABC333) のD問題 (Erase Leaves) の解説記事です。
AtCoder Beginner Contest 333 (ABC333) のC問題 (Repunit Trio) の解説記事です。
AtCoder Beginner Contest 333 (ABC333) のB問題 (Pentagon) の解説記事です。
AtCoder Beginner Contest 333 (ABC333) のA問題 (Three Threes) の解説記事です。
問題 頂点からなる木構造のグラフと、整数 が1個ずつランダムに入った順列 が与えられる。 ここで、グラフ内の頂点 の距離を とする。 組の整数 が与えられるので、そのそれぞれについて が成立するような が の中に含まれるか判定せよ。 入力 まず最初の1行…
問題 木構造のグラフとは、 ループを含まない 頂点 辺のグラフのことを指す。 頂点の木構造のグラフに対して、 日間で整数 が1日ごとに与えられる。 また、グラフは1日1回までなら、以下の操作を行うことができる。 ある頂点 と、 に隣接している頂点 と隣接…
問題 個の整数からなる数列 が与えられる。 この数列 に対して以下の操作を行う。 の最初の要素を最後に持ってくる。 その要素が、1つ前の要素より真に大きくなるまで前の要素と位置を入れ替える。 もし入れ替えを経て、その要素が再び先頭になった場合は操…
問題 個の整数からなる数列 が与えられる。 この数列の要素 に対し、 と定めるとき、 が成立するような整数 の組(ただし、 )の個数を求めよ。 入力 まず最初の1行目に、テストケースの個数を表す整数 が与えられる。 その後、 個のテストケースのそれぞれ…
問題 個の整数からなる数列 が与えられる。 数列 の連続部分列のうち、どの要素も隣接する数字の偶奇が異なるようなものについて、部分列内の要素の和の最大値を求めよ。 入力 まず最初の1行目に、テストケースの個数を表す整数 が与えられる。 その後、 個…
問題 個の箱があり、 番目の箱は トンの重さである。 この 個の箱を 個ずつ順番に運び、トラックに積むことを考える。 すなわち、 最初の 個の箱を最初のトラックに積む。 次の 個の箱を2番目のトラックに積む。 最後の 個の箱を 番目のトラックに積む。 と…
問題 最初に整数 が与えられる2人用のゲームがある。 片方の参加者のターンとして、「与えられた整数に対して を加える」か「 を減らすか」のいずれかの操作を行い、もう片方のターンにするということを繰り返す。 また、先手の勝利条件は「先手の操作直後に…
問題 整数 に対して、関数 を「 となるように並び替えたときの の値」を返す関数として定義する。 要素数が 個の整数列 が与えられるので、 であるすべての に対して の値の総和を求めよ。 すなわち、 の値を求めよ。 入力 まず最初の1行目に、テストケース…
問題 頂点 を根とした 頂点の二分木がある。 各頂点は最大で2個の子を持っており、また頂点 は文字 をそれぞれ持っている。 ただし、 は U, L, R のいずれかである。 この二分木について、頂点 から以下のように動くことを考える。 いまいる頂点での文字が U…
問題 数字 がそれぞれ 個、 個、 個黒板にかかれている。 この状況下で、以下の操作を行う。 2つの異なる数字を1個ずつ選び黒板から消し、それらとは異なる数字を黒板に1個追加する。 例えば、黒板に と書かれていた場合、 を消して を追加することにより、…
問題 1行からなる 個のセルがあり、一部はブロックされており、一部は空である。 以下の2つの操作を行い、すべての空のセルを水で埋めることを考える。 操作1: ある空のセルに水を入れる。 操作2: 水の入ったセルから水を抜き、別の空のセルにその水を入れる…
問題 長さ の整数列 と正の整数 が与えられる。 この数列 に対して、ある要素を だけ増やすという作業を最大 回行うことができる。 作業終了後に、 の各要素の bitwise AND を取ったときの最大値を求めよ。 ただし、 の値は全部で 個与えられるので、その 個…
問題 個の要素からなる整数列 が与えられる。 これをいくつかの空でない部分列に分割する。 番目の部分列の要素の合計を とし、部分列の個数を 個とするとき、 の最大値を求めよ。 例 例えば、 とし、この数列 を と分割したとき、 \begin{align} \sum_{i = …
問題 すべての要素が非負整数からなる 行 列の行列 が与えられる。 この行列 に対して、以下の条件をすべて満たす 個の要素からなる整数列 が存在するかを判定せよ。 がすべての である に対して成立する。 ただし、 は bitwise OR を表す。 入力 まず最初の…
問題 個の要素からなる数列 が与えられる。 ただし、 個目の要素は である。 ここで、 の部分列のうち、 個以下の長さのものを逆順にする、という作業が何回でもできるとき、 を昇順にすることができるかどうかを判定せよ。 ただし「逆順にする」とは、整数 …
問題 頂点の木があり、頂点は と、辺は と番号をつけられている。 また、辺 (ただし、 )は頂点 と頂点 を結んでいる。 を満たすすべての整数組 に対して、以下の値の総和を求めよ。 頂点 から出発し、番号が 以上 以下である辺のみを 本以上辿って到達でき…
問題 数直線上の 個の区間 が与えられる。 集合 の部分集合 は、次の条件を満たすときに良い集合と呼ばれる。 任意の に対して、以下の2つのうち少なくとも一方が成立する。 区間 は区間 を含む。 区間 は区間 を含む。 ここで、「区間 が区間 を含む」とは…
問題 整数屋さんでは 以上 以下の整数が売られている。 整数 の値段は を10進法表記したときの各位の和を とするとき、 円である。 所持金が 円のとき、購入可能な最大の整数を求めよ。 入力 1行に整数 が順に与えられる。 条件 出力 答えとなる整数を1行に…
問題 平面上の点 と、4つの整数からなる 個の組 (ただし、 )が与えられる。 このとき、以下の手順を考える。 点 を始点、点 を終点とする有向曲線 を任意に1つ選ぶ。 次に、 以上 以下の相異なる 個の整数 を任意に選ぶ。 その後、 に対して、下記を行う。…
問題 から までの番号がついた 人の人がいる。 「人 は人 よりも背が高い」という情報が 個与えられるとき、これらの情報に矛盾がないかを判定せよ。 入力 まず最初の1行目には、整数 が与えられる。 次の 行については、順に整数 が与えられる。 条件 出力 …
問題 10進法表記で 桁である整数 が与えられる。 である整数 について、 の上から 桁目を とするとき、 \begin{align} \sum^{d - 1}_{i = 1} \sum^{d}_{j = i + 1} | {a}_{i} - {a}_{j} | \end{align} の値を求めよ。 入力 最初の1行目に、桁数を表す整数 が…
問題 長さ の整数列 が与えられる。 を満たす整数組 を任意に選ぶときの、 の値としてありえる最大値を求めよ。 入力 まず最初の1行目に整数 が与えられる。 その次の1行に 個の整数 が順に与えられる。 条件 入力はすべて整数 出力 最大値を1行で出力するこ…
問題 4人用対戦ゲームを 試合行い、1位を 回、2位を 回、3位を 回、4位を 回取った。 平均順位を 以下にするには、最低でもあと何試合行うことが必要か答えよ。 入力 まず最初の1行目に整数 が与えられる。 次の1行には、整数 が与えられる。 最後の1行には…
問題 (, ) からなる文字列のうち、連続する () を消すことを0回以上繰り返すことにより空文字列になる文字列のことを、正しい括弧列と呼ぶ。 (), (()), (()())() は正しい括弧列である。 )(, ()), (()()))(() は正しい括弧列ではない。 文字列 が与えられる…