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

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

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

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 座標平面の原点にコマがある. このコマに対して, 以下の3種類の操作から1つを選び, 実行することを 回繰り返す. コマが にいるとしたとき, に移動させる. コマが にいるとしたとき, に移動させる. コマが に…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 個の都市と 個の発電所からなる国がある. これらを総称して地点と呼ぶ. 個の都市は地点 と, 個の発電所は地点 と名付けられている. この国には 本の電線があり, 番目の電線は地点 , 地点 を結ぶ. ここから …

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 マス からマス からなるマスがある. 最初, マス にいる. マス からマス にはサイコロが1個あり, マス にあるサイコロには 以上 以下の整数が等確率で出る (毎回独立). マス に到達するまでサイコロを振り, …

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 頂点 辺の単純無向グラフ が与えられる. ただし, である. この各頂点を赤または青で塗る. 以下を満たすような塗り方は何通りか? 赤で塗られている頂点は 個 端点が異なる色で塗られている辺は偶数本 制約 は…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 以下を満たす の連続部分列の個数を それぞれの場合について求めよ. 任意の に対して, その連続部分列は または を含む. 長さが 制約 解法 上の条件を条件 (A) と呼ぶことにする. 連続部分列の末項で場合分…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 個の整数 がある. これらはそれぞれ素数 と正の整数 を用いて, である. このとき, それぞれに対して以下を求めた際に得られる整数の個数を求めよ *1 . 制約 は素数 解法1 のときは のみなので, 答えは であ…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 個からなるじゃがいもの列がある. 先頭から 番目のじゃがいもの重さは である. このじゃがいも達を次のルールによって箱に詰めていく. 空の箱を用意する. じゃがいもがある限り以下の操作を続ける. その時点…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 円と整数 を持っている. 最初, である. 以下の操作を任意回できる. 以上 以下の整数 を1つ選び, 円払って, を で置き換える. 円の予算内で可能な最終的な の最大値を求めよ. 制約 解法 整数の大小について, …

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 は全て である 以上 以下の整数である. の並び替え に対する 番目の不満度を以下のようにして定義する. 整数 は であるとする. このとき, ならば, 番目の不満度は , そうでなければ 番目の不満度は . 全ての…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 次を満たす長さ の整数列全体 の集合を とする. に対して, となる. に対して, を となる 以上 以下の整数の個数と定める. このとき, を求めよ. 制約 解法1 実は次の定理が成り立つ. 定理 F.1. を整数全体の…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 頂点 辺からなる単純無向グラフ がある. ただし, とする. なお, 各頂点の次数は 以下である. 次の 個の質問に答えよ. 質問 : 頂点 からの距離が 以下であるような頂点全てにおける番号の総和を求めよ. 制約 …

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 次を満たす長さ の整数列 の個数を求めよ. 制約 解法 動的計画法で解く. を次のように定義する. 長さが である条件を満たすような列のうち, 末項が であるような数列の数. このとき, 最終解答は である. ベ…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 集合 があり, 最初, である. 次の操作を好きなだけ行なう. 円払い, に を加える. 円払い, に を加える. 円払い, に を加える. 円払い, に を加える. 円払い, に を加える. 円払い, に を加える. にするため…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 とする. 次の 個の質問 に答えよ. 質問 : か? 制約 解法 する. 次のようにして定義された列 を用いて, かどうかを判定できる. の定義 に対して, のとき, かつ, に対して, 「 ならば, 」が成り立つとき, , そ…

問題 atcoder.jp 提出解答 (※ 解説と動的計画法の添字の順番が逆になっている) atcoder.jp 問題の概要 文字列 に対して, 以下の方法で生成される文字列を *1 と書くことにする. を以下を満たすように連続する部分列で分割する. 各部分列にある文字は全て同じ…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 座標平面上に 異なる 点 がある. このとき, 点以上を通る直線の数を求め, 有限ならばその数を無限ならばその旨を報告せよ. 制約 解法 1 ( のとき) のとき, に対して, 直線 は点 を通る直線であり, 写像 は単…

問題 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 問題の概要 以下を満たす文字列 の個数を求めよ. は英大文字からなる長さ の文字列 は辞書式の意味で である回分. ※ 個のマルチケース 制約 は英大文字からなる長さ の文字列 個のケースにおける の総和を とすると, で…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 頂点 を根とする根付き木がある. 番目の辺は頂点 を結ぶ. 自然数の部分集合 を 以上 以下の整数全体の集合とする. また, 頂点 に対して, で の子孫全体の集合とする. 以下を満たす 個の整数の組 の内, を最…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 頂点からなる頂点 を根とする根付き木がある. 番目の辺は頂点 を結ぶ. また, 頂点 には整数 が書かれている. 次の 個の問題に答えよ. 頂点 を根とする部分木にある頂点に書かれている整数のうち, 番目に大き…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 長さ の整数列 が与えられる. 次の 個の情報 を用いて, を求めることは可能か? と 制約 解法 を の累積和とする. つまり, とする. このとき, である. よって, 問題は と の情報から が特定できるか? という…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 スキー場には 個の広場があり, 広場 の標高は である. また, 個の坂があり, 広場 と広場 を双方向に行き来可能にする. この坂でのみ広場を移動でき, 標高が である広場から, 広場 である広場へ坂を利用して…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 枚のカードがあり, 左から 番目には と書かれている. この [tex; N] 枚から何枚かのカードを取り出す. ただし, 2枚連続で取り出さないことは禁止されている. 可能な取り出し方全てを考えたとき, 取り出した…