yutasの競技プログラミング勉強帖

競技プログラミングの問題についての解説記事を主に書いています。

Codeforces Round 909

G - Unusual Entertainment / Codeforces Round 909 (Div. 3)

問題 頂点からなる木構造のグラフと、整数 が1個ずつランダムに入った順列 が与えられる。 ここで、グラフ内の頂点 の距離を とする。 組の整数 が与えられるので、そのそれぞれについて が成立するような が の中に含まれるか判定せよ。 入力 まず最初の1行…

F - Alex's whims / Codeforces Round 909 (Div. 3)

問題 木構造のグラフとは、 ループを含まない 頂点 辺のグラフのことを指す。 頂点の木構造のグラフに対して、 日間で整数 が1日ごとに与えられる。 また、グラフは1日1回までなら、以下の操作を行うことができる。 ある頂点 と、 に隣接している頂点 と隣接…

E - Queue Sort / Codeforces Round 909 (Div. 3)

問題 個の整数からなる数列 が与えられる。 この数列 に対して以下の操作を行う。 の最初の要素を最後に持ってくる。 その要素が、1つ前の要素より真に大きくなるまで前の要素と位置を入れ替える。 もし入れ替えを経て、その要素が再び先頭になった場合は操…

D - Yarik and Musical Notes / Codeforces Round 909 (Div. 3)

問題 個の整数からなる数列 が与えられる。 この数列の要素 に対し、 と定めるとき、 が成立するような整数 の組(ただし、 )の個数を求めよ。 入力 まず最初の1行目に、テストケースの個数を表す整数 が与えられる。 その後、 個のテストケースのそれぞれ…

C - Yarik and Array / Codeforces Round 909 (Div. 3)

問題 個の整数からなる数列 が与えられる。 数列 の連続部分列のうち、どの要素も隣接する数字の偶奇が異なるようなものについて、部分列内の要素の和の最大値を求めよ。 入力 まず最初の1行目に、テストケースの個数を表す整数 が与えられる。 その後、 個…

B - 250 Thousand Tons of TNT / Codeforces Round 909 (Div. 3)

問題 個の箱があり、 番目の箱は トンの重さである。 この 個の箱を 個ずつ順番に運び、トラックに積むことを考える。 すなわち、 最初の 個の箱を最初のトラックに積む。 次の 個の箱を2番目のトラックに積む。 最後の 個の箱を 番目のトラックに積む。 と…

A - Game with Integers / Codeforces Round 909 (Div. 3)

問題 最初に整数 が与えられる2人用のゲームがある。 片方の参加者のターンとして、「与えられた整数に対して を加える」か「 を減らすか」のいずれかの操作を行い、もう片方のターンにするということを繰り返す。 また、先手の勝利条件は「先手の操作直後に…