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

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 各項が 以上 以下の整数である長さ の列 がある. 次の問題を に対して解け. とする. の順に以下を実行する. と を入れ替える. を満たす を求めよ. 制約 解法 をそれぞれ 番目と を入れ替える作用素とする. …

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

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 縦 行, 横 列からなるグリッドがある. 上から 行目, 左から 行目にあるマス目を と書く. には整数 が書かれている. ただし, である. を満たす整数の組 全てについて次の問に答えよ. を満たす を塗りつぶす. …

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 頂点 辺の単純無向グラフ がある. なお, である. また, 各辺は赤または青の色があり, ならば赤, ならば青である. 高橋君は最初, 頂点 にいるとき, と青い辺で接続している頂点に移動できる. しかし, 個の頂…

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

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 に対して文字 があり, は のどれかである. また, であるような は唯一つである. このとき, 以下を満たすような整数の組の列 は存在するか? に対して, に対して, に対して, 制約 は 以上の整数で は のどれか…

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

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 個のマスがあり, 各マスにはマス , マス , マス と名付けられている. 最初, コマはマス にある. ルーレットで から等確率で1つの整数を決定し, その数だけコマを進める. ただし, マス をオーバーした場合は…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 2次元座標上に 個の街と 個のブースターがある. 番目の街は座標 にあり, 番目のブースターは にある. ブースターを 個獲得するごとに移動速度が 倍になる. 最初, 原点にいる高橋君が全ての街を訪れ, 原点に…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 の順列 が与えられる. 以下の条件を共に満たす長さ の整数列 の数を求めよ. 各項は 以上 以下の整数 とすると, は より辞書順で小さい. 制約 は の順列. 解法 各項が 以上 以下である長さ の整数列全体の集…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 空数列 と長さ の整数列の列 がある. の各項は空列である. 次の 個のクエリを順に処理せよ. : の末尾に を加える. : の末尾を削除する. ただし, が空列の場合は何もしない. : : 各クエリ終了後における の末…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 が の倍数であるという条件下における の最小値を求めよ. ケースのマルチケース 制約 解法 を固定する. このとき, が の倍数になるような最小の非負整数 を と書くことにする. のとき このとき, であるから,…

B# 問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 長さ の整数列 がある. 次の操作を 回行う. の第 項に を加算する. 各操作後において, に含まれない最小の非負整数を求めよ. 制約 解法 一般的に, 以下が成り立つ. 長さが の整数列 において, に含まれな…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 次を満たすような二重添字整数列 を一つ求めよ. である. に対して, となる整数の組 が唯一存在する. 行 列のマスにおいて, 上から 行目, 左から 行目に整数 を書き込んだ場合, どの上下左右に隣接する2つの…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 整数列 に対して, の最長増加部分列の長さを と書くことにする. の並び替え が与えられる. 次の操作を 回以上行うことができる. となる整数 を選び, と を, と をそれぞれ交換する. 操作後における の最大値…

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

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 重み付き有向グラフ が与えられる. なお, である. 次を満たす有向パス は存在するか? 存在するならばそのような有向パスのうち, 長さの総和の最小値を求めよ. は を始点, を終点とする. は の連続とは限らな…

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

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 個のかごが円状に置かれている. に対して, かご の右隣にはかご が置かれている. なお, かご はかご とみなす. 最初, かご には 個のりんごがある. 高橋君は最初, かご の前にいる. ここから, 合計で 個のり…

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

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 インタラクティブ問題 行 列のマスからなるチェス盤と 個のルークがある. このうち, 個のルークが以下を満たすように置かれている. どの行にも2個以上のルークが置かれていない. どの列にも2個以上のルーク…

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

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 円卓の周りを人 , 人 , , 人 がこの順に反時計回りに等間隔に座っている. 各人 の前には料理 がある. 次の操作を 回以上できる. 円卓を だけ反時計回りに回す. これによって, 人 の前にあった料理は人 に移…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 頂点からなる根付き木 は頂点 を根とし, 頂点 の親は頂点 である. 各頂点には表裏のあるコインとボタンがある. ボタンを押すと, その頂点を根とする部分木にある全ての頂点のコインの表裏が入れ替わる. 次の…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 からなる文字列 に対して, で を 度回転させた文字列とする. からなる長さ の文字列 に対して, 以下の操作を高々 回行うことができる. なる整数の組 を一つ選び, を に置き換える. 最終的な としてあり得る…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 の順列 がある. 以下の操作を繰り返し行い, を昇順に並び替えたい. 操作 (A): を選び, を入れ替える. 操作 (B): を選び, を入れ替える. このとき, 操作 (A) の回数が最小であり, 合計操作回数が 以下である…

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

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 頂点 辺の単純無向グラフ が与えられる. ただし, とする. また, 頂点 には整数 が書かれている. 次の操作を 回行う. にある頂点 を一つ選ぶ. の における近傍にある頂点に書かれている整数の総和をコストと…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 正多面体のダイスがあり, このダイスを振ると のうちランダムで1つである. このダイスを用いて, 以下を考える. ダイスの出目をスコアにする. ただし, 気に入らないならば 回まで以下を行うことができる. そ…