D問題
問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 高橋君と青木君が次のようなゲームを行った. 個の石からなる山が1つある. 山に石がある限り, 高橋君から交互に以下の行動を行う. その時点で山にある石の数を とする. となる整数 を選び, 山から 個の石を取…
問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 問題文の図 にあるように六角形のグリッドがある. この六角形のうち, 個のマス は黒であり, それ以外のマスは全て白色である. このとき, 黒マスはいくつの連結成分からなるか? 制約 解法 今回の問題ではマス…
問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 次を満たす文字列 が存在するならば一例を挙げ, 存在しなければその一例を挙げよ. は次のようにして構成されている. の並び替え1つ取ってきて, それを とする. ( 個以上の ) ( 個以上の ) は のどれとも一致…
問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 長さ の整数列 が与えられる. の長さ の連続とは限らない部分列 における の最大値を求めよ. 制約 解法 動的計画法で求めることにする. に対して, で以下のように定める. まで見て, まで決定した場合におけ…
問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 数直線上に高橋くんがいる. 座標 に穴があいている. あなたは時刻 に穴 にいる. そして, あなたは数直線上を速さ 以下で移動できる. また, 匹のモグラが穴からでて, 番目のモグラは時刻 に穴 から出て, その…
問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 長さ の非負整数列 に対して, 以下を満たす整数 は存在するか? 制約 解法 を の累積和とする. つまり, と定義する. このとき, 同様にすると, 求めるべき問題を と簡略化することができた. を1つ固定する. す…
問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 の並び替え が与えられる. に対して隣接する文字の入れ替えを行い を にする場合, 最低でも何回入れ替えなければならないか. 制約 は の並び替え 解法 に対して, をそれぞれ に置き換えた整数列を とする. …
問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 長さ の整数列 がある. 以下の操作を順に1回だけ行う. 以上 以下の整数を1個選ぶ. その後, を満たす全ての整数 に対して, とする. 以上 以下の整数を1個選ぶ. その後, を満たす全ての整数 に対して, とする.…
問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 回のコイントスを行う. また, で初期化されているカウンタを持っている. 回目のコインの表裏によって, 以下を行う. 表の場合, 円貰い, カウンタを 増やす. 裏の場合, カウンタを にする. ここで, に対して, …
問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 から までの整数が書かれたカードが1枚ずつ計 枚あり, 裏向きで1つの山に積まれている. 上から 番目のカードに書かれているカードは である. 次の操作を 回行う. 山札の一番上のカードを引き, 表向きにする.…
問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 個の円 がある. の中心は , 半径は である. 2点 が与えられる. 次のことは可能か? から少なくとも1つの円の円周上である点を通って, に到達可能. ただし, は共にある円周上の点である. 制約 はある円周上の…
問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 個のステージからなるゲームがある. 番目のステージはストーリー映像が 分, ゲームパートが 分からなる. 各ステージをクリアするためには, ストーリー映像を見てゲームをクリアしなければならないが, 以前に…
問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 座標平面上に 点 があり, の座標は である. ジャンプ力が のとき, 以下の条件を満たす場合に限り点 から点 へ移動できる. 適切に最初に 個の点から始点とする点を 1個選び, ジャンプ力を設定することにより,…
問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 実数 に対して, とする. としたとき, 次を満たすような右半開区間の列 のうち, が最小であるような列の一例を求めよ. 制約 解法 で に関する定義関数とする. つまり, 整数 に対して, となる. このとき, 整数…
問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 長さ の整数列 が与えられる. に対して, 次の質問に答えよ. の要素を にするために以下の操作は最低でも ( 回以上) 何回必要か? 以上 以下の整数 を選び, 以下のうちのどちらかを実行する. に 加算する. か…
問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 次を満たす 以上 以下の整数の組 の個数を求めよ. が平方数になる. 制約 解法 1 正の整数 と素数 に対して, を と定義する. つまり, を で割り切れる最大の回数とする. このとき, を素数全体の集合としたと…
問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 以上 以下の整数のうち, の倍数でも の倍数でもないような整数全ての総和を求めよ. 制約 解法 集合 を : 以上 以下の整数全体の集合 : 以上 以下の整数のうち, の倍数であるもの全体の集合 : 以上 以下の整…
問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 次を満たす 以下の整数 の個数を求めよ. 次を満たす素数 が存在する: 制約 解法 素因数分解の一意性から, 求めるべき答えは なる素数 の形で表せる 以下の整数である. の範囲について, 素数は 以上なので, …
問題 atcoder.jp 提出解答 解法1 atcoder.jp 解法2 atcoder.jp 問題の概要 長さ の整数列 が与えられる. 次を満たす整数のトリプル *1 を求めよ. 制約 解法 で にある の個数を表すとする. また, なので, 求めるべきは である. 従って, を満たすトリプル を…
問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 整数列 が与えられる. 次の質問に 個答えよ. にある の個数を求めよ. 制約 解法 に対して, で にある の個数とする. このとき, 列 を以下を満たすような列とする (このような列達は から一意に定まる). この…
問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 空の筒がある. 次の 個のクエリを順に処理せよ. (Type 1) と書かれたボールを 個筒の右から入れる. (Type 2) 筒の左から のボールを取り出し, 取り出したボールに書かれている数の総和を求め, 出力する. 制…
問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 以下を満たす最小の整数 を求めよ. を満たす非負整数 が存在する. 制約 解法 に対する答えを と書くことにし, とする. そして, であり, という制約から, である. また, ならば, である. よって, として, の…
問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 次多項式 と 次多項式 がある. ここで, の各係数の絶対値は 以下である. としたとき, が与えられるので, を求めよ. ただし, が一意に定まるような が与えられる. 制約 の各係数の絶対値は 以下 は一意に存在…
問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 の並び替え が与えられる. 次の操作を に対してちょうど 回行って, にできるか? 整数 を 以上 以下の異なる整数とする. を入れ替える. 制約 は の並び替え. 解法 2つの要素の入れ替えを 回行うということは,…
問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 頂点からなる完全二分木があり, 個の頂点にはそれぞれ と名付けられている. ここで, この二分木は以下のようにして構成されている. に対して, 頂点 の左の子, 右の子はそれぞれ である. 最初, 頂点 がマーク…
問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 からなる文字列 が与えられる. 文字列の列 を以下のようにして生成する. は の各文字において, を に, を に, を に同時に置き換えてできる文字列. 次の 個の問 に答えよ. の先頭から 文字目は何か? 制約 は…
問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 長さ の列 が与えられる. 以下を満たす 以上 以下の組 の個数を求めよ. を筆算で計算すると, 繰り上がりが発生しない. 制約 解法1 (条件) とする. 以上 以下の整数からなる列の集合を とする. このとき, と …
問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 筒の中にボールを入れていく. 各ボールには 以上の整数が書かれている. と書かれたボールが筒の中で 個連続すると, その 個は消滅する. 番目には と書かれたボールを入れるとき, それぞれに対して, 番目のボ…
問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 高橋君と青木君が以下のゲームを行う. 高橋君は 以上 以下の整数 を1つ選び, 青木君に伝える. 青木君は 以上 以下の整数 を1つ選ぶ. が素数ならば青木君の勝ち, 素数でなければ高橋君の勝ち. 両者が勝利のた…
問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 次を満たす非負整数 は存在するか? ただし, 2つの非負整数 に対して, でビットごとの論理積とする. ※ 個のマルチケース 制約 解法 まず, 和とビットごとの論理積を関連付けると等式として, 2つの非負整数 に…