問題 提出解答 解法 問題 atcoder.jp 提出解答 atcoder.jp 解法 座標平面上の点 を とする. 動的計画法で解く. に対して, で, 問題を へ制限したときの距離の総和の最小値とする. このとき, 最終解答は になる. ベースケースは のときで, このとき, 経由すべ…

問題 提出解答 解法 問題 atcoder.jp 提出解答 atcoder.jp 解法 「データ構造をマージする一般的なテク」を利用して, この問題を解く. 以下のものを用意する. を頂点に持つ Union-Find . に対して, とする. は頂点 を代表元に持つ連結成分におけるベースとな…

問題 提出解答 問題の概要 制約 解法 1 (座標圧縮) 解法 2 (方針) 解法 3 (高速化) 問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 行 列からなるマス目があり, 上から 行目, 左から 列目のマスを と書くことにする. に対して, には正の整数 が, それ以外…

問題 提出解答 問題の概要 制約 解法 である. 問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 行 列からなるグリッドがある. この中から 個のマスをランダムに選び, その 個のを含む最小の長方形に含まれるマスの数をスコアとする. スコアの期待値を求めよ…

問題 提出解答 問題の概要 制約 解法 問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 以上の整数 のうち, 以下を満たすような整数の数を求めよ. を 進法で表すと, 全ての桁について, 「その桁が または 」が成り立つ. 個のテストケースについて答えよ. 制…

問題 提出解答 問題の概要 制約 解法 1 解法 2-(a) 解法 2-(b) まとめ 問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 縦 , 横 の長方形の内部 (及び周) に含まれる正三角形の辺の長さの最大値を求めよ. 制約 解法 1 を仮定する. また, 以降では座標平面内…

問題 提出解答 問題の概要 制約 解法 問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 有向グラフ がある. ここで, である. また, 有向辺については次のようになっている. かつ の 文字目が このとき, において, は頂点 から頂点 へ到達可能か? 可能ならば…

問題 提出解答 問題の概要 制約 解法 問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 進表記において, 桁の整数 が与えられる. の全ての桁は ではない. の部分集合 に対して, を次のように定める. を長さ の文字列とみなす. となる全ての に対して, の 文…

問題 提出解答 問題の概要 制約 解法 問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 インタラクティブ問題 以上 以下の整数 が設定されているが, これは秘密である. このとき, 次の手順を踏むことにより, を特定し, を出力せよ. (Input) 以上 以下の整数 …

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 長さ の英子文字列 と 以上 以下の整数 対して, を とする. ただし, 英子文字列 の長さを と書く. 英小文字列 と に対して, を の 文字目から 文字目の連続英子文字列とする (ただし, の場合は空文字列とす…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 インタラクティブ問題 次の2つの Phase を完遂せよ. Phase 1 が与えられる. 以上 以下の整数 を出力する. 個の整数の組 を出力する. ただし, でなくてはならない. Phase 2 が与えられる. 以下を 回行う. 回…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 個の非負整数 が与えられる. 次の値を求めよ. ただし, を非負整数全体の集合とする. 制約 解法 非負整数列 に対するこの問題の答えを と書くことにする. の2進表記における最大の桁数を とする. このとき, …

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 無向グラフ が与えられる. なお, である. ここで, 辺を使って頂点を移動すると, 次のようにポイントが変動する. 番目の辺を用いて頂点 から頂点 へ移動すると, ポイントが 増加する. 番目の辺を用いて頂点 …

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 個の箱 と 個のボール がある. 最初, 箱 にはボール のみが入っている. 次の 個のクエリを順に処理せよ. Type 1 : 箱 に入っているボールを全て箱 に移す. Type 2 : この時点で 個の箱に入っているボールの…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 個の文字列 が与えられる. 先手と後手の2人がこの 個の文字列を用いてしりとりをする. 先手から交互に以下を満たすような整数 を選ぶ. はこれまで1回も選ばれていない. 先手の第1ターン, または直前に選ばれ…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 整数列 がある. それぞれに対して以下の問に答えよ. 確率変数 をそれぞれ から一様ランダムに決定する (重複がある場合はその分だけ 2倍, 3倍になる). このとき, の期待値を求めよ. 制約 解法1 まず, を固定…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 長さ の整数列 が与えられる. に対して, 次の問題を解け. から連続部分列を選び, その部分を削除することを 回以上行い, 残った整数列における整数の総和を にすることは可能か? 可能ならば操作回数の最小値…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 行 列のマス目があり, 上から 行目, 左から 列目をマス と呼ぶことにする. マス には非負整数 が書かれている. マス から右か下のマスに移動することを繰り返すことによってマス へ移動する方法のうち, 通っ…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 AtCoder 国は 個の島からなる島国である. 最初, どの島にも空港, 港はなく, どの2つの島の間にも道路はない. 次のことをそれぞれ好きなだけ行うことができる. なる整数 を選び, 円支払って 島 に空港を建設…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 2重添字数列 を 次の 個の問に答えよ. 以下を求めよ. 制約 解法1 とする. このとき, に対して, を とすると, であるから, を高速に求められれば良い. 解法2 ここで, を初項 , 交差 , 項数 の等差数列の和と…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 からなる文字列 に対するスコア を次のように定める. に対して, をみたす整数の組 の数を とする. 個の からなる文字列 に対して, の並び替え に対する を全て考えた時のスコアの最大値を求めよ. 制約 は か…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 頂点の木 が与えられる. ただし, 次の 個の問に答えよ. 問 : 頂点 からの距離が である頂点は存在するか? また, 存在するならばそのような頂点の例を1つ挙げよ. 制約 は木. 解法 木 上の2頂点 間の距離を と…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 行 列からなるマス目がある. 上から 行目, 左から 列目のマス (以降ではマス と呼ぶことにする) は ならば白, ならば黒である. 以下の操作から1つ選び, 実行することを 回以上行うことができる. なる整数 を…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 人 , , 人 の 人からなるじゃんけん大会がある. このじゃんけん大会は次の形式で開催される. 参加者を人 , , 人 の順に横 列に並べる. 次のことを 回繰り返す ( 回目). に対して, 左から 人目と 人目がじゃ…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 頂点数が , 辺の数が の二部グラフ がある. ここで, この おいて, 長さ のサイクル は存在するか? 存在するならば, を成す頂点の一例を求めよ. 制約 解法 が二部グラフなので, に が存在することと, 以下は…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 頂点の木 がある. 番目の辺は頂点 と頂点 を重み で結ぶ. 以下を満たす の全域部分グラフ のうち, にある辺の重みの総和の最大値を求めよ. 各頂点 に対して, における頂点 の次数は 以下である. 制約 は に…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 無向グラフ が以下で与えられる. に対して, 頂点 と頂点 を同一視したグラフを とする. このとき, に対して, 以下の問 に答えよ. 上で, 頂点 と頂点 は連結か? 連結ならば 上で頂点 , 頂点 間の距離を求めよ…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 長さ の整数列 が与えられる. 次の 個のクエリを順に処理せよ. Type 1: Type 2: を の累積和, を の累積和, を の累積和としたとき, の第 項目を求めよ. 制約 解法 の第 項目, の第 項目, の第 項目, の第 …

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 長さが の整数列 と2重添字数列 がある. ここで, である. 次の 個の質問に答えよ. における全ての の最大公約数求めよ. 制約 解法 に対する最大公約数を と書くことにする. このとき, 次が成り立つ. を整数…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 連結単純無向グラフ がある. 次を満たす の全域部分グラフ を一つずつ求めよ. を頂点 を根付き木としたとき, 任意の に対して, とすると, は において先祖と子孫の関係である. を頂点 を根付き木としたとき,…