問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 次のようにして数列 が定められている. このとき, となる非負整数 は存在するか? 存在するならばそのような の最小値を求めよ. 個のマルチケース形式 制約 は素数 解法 以降の解説では の世界で考えることし…

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

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

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 高橋君と青木君が次のようなゲームを行った. 個の石からなる山が1つある. 山に石がある限り, 高橋君から交互に以下の行動を行う. その時点で山にある石の数を とする. となる整数 を選び, 山から 個の石を取…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 頂点からなる木 が与えられる. このとき, 上の頂点 を始点, 頂点 を終点とする (単純) パスを求めよ. 制約 は木である. 解法 グラフ上のパスを求める問題なので, DFS や BFS をそのまま実装すればよい. また…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 数直線上の原点に高橋君がいる. また, 座標 には壁があり, この壁を越えて移動はできない. しかし, 座標 にあるハンマーを取得した後ならば, この壁を破壊して通過できるようになる. 高橋君は座標 に到達可…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 3問からなるテストがあり, 各問の得点は 1点, 2点, 4点である. このテストで高橋君は 点, 青木君は 点であった. すぬけ君は高橋君, 青木君のうち少なくとも一方が正解できた問題のみ正解できた. すぬけ君の…

問題 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 問題の概要 以下の条件を全て満たす非負整数 を昇順に全て列挙せよ. の2進数表記において, 任意の非負整数 で の の位が ならば, の の位も である. 制約 の 進数表記において, である位の数は 個以下. 解法1 の の位が…

問題 atcoder.jp 提出解答 (解法 1) atcoder.jp (解法 2) atcoder.jp 問題の概要 次のようにして 個の文字列 を生成した. に対して, とする. 次を満たす4個の整数をそれぞれ を選ぶ. を満たす全ての整数の組 に対して, の 文字目を に置き換える. 完成後の …

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 行目には を出力し, 行目には を出力せよ. 制約 解法 問題文のように出力すれば良い. ただし, 改行と空白の出力を混同しないように.

問題 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 問題の概要 長さ の非負整数列 が与えられる. 次のようにして長さ の非負整数列 を作成する. をうまく選び, に出てくる整数の種類の数の最小値を求めよ. 制約 解法 まず, とすると の各項が or になり, 種類の数が高々 …

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 次を満たす文字列 が存在するならば一例を挙げ, 存在しなければその一例を挙げよ. は次のようにして構成されている. の並び替え1つ取ってきて, それを とする. ( 個以上の ) ( 個以上の ) は のどれとも一致…

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

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 英文字列 について, は の接頭語か? 制約 は長さ 以上 以下の英子文字列 解法 が の接頭語であるための必要十分条件は である. これをそのまま実装すればよい.

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 5個の整数 には何種類の整数があるか? 制約 解法 求めるべきは集合 の濃度である. 例えば集合などの重複を考慮しないデータ構造の "大きさ *1 " を答えれば良い. *1:使うデータ構造によって呼び方が変わる

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

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 長さ の正の整数列 がある. 次の操作を の長さが になるまで繰り返し行う. を満たす 以上 以下の整数 を1つ取る. その後, を で置き換える. そして, ならば, から を取り除く. このとき, 各操作において, 条…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 個の整数 の中から奇数個選び, 和を にする選び方の数を求めよ. 制約 解法 制約から, である. まず, ならば, 答えは明らかに なので, 以降は であると仮定する. このとき, と の値によって, 次のように を定…

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

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

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 長さ の整数列 が与えられる. の長さ の連続とは限らない部分列 における の最大値を求めよ. 制約 解法 動的計画法で求めることにする. に対して, で以下のように定める. まで見て, まで決定した場合におけ…