問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 長さ の列 が与えられる. 以下を満たす 以上 以下の組 の個数を求めよ. を筆算で計算すると, 繰り上がりが発生しない. 制約 解法1 (条件) とする. 以上 以下の整数からなる列の集合を とする. このとき, と …

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 長さ の列 が与えられる. に対して次の操作を 回以上行い, と一致させられるか? 以上 以下の整数を つ選ぶ. をそれぞれ に置き換える. 制約 解法1 (必要十分条件) まず, において出現回数が異なる整数が異な…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 からなる長さ の文字列 が与えられる. に対して, 以下の操作を 回以上行ってできる文字列のうち, 辞書式最小のものを求めよ. にある を に置き換える. にある を に置き換える. 制約 は からなる長さ の文字…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 行 列のマス目にはそれぞれ白または黒で塗られている. 高々 個の白マスを黒マスに塗り替えることにより, 縦横斜めの向きに 個以上黒マスを連続させることは可能か? 制約 解法 ある方向に連続する6マスにおい…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 本のパスタがあり, 番目のパスタの長さは である. 次の 日間の予定を完遂できるか? 日目において, 長さがちょうど のパスタ 本を食べる (食べたらなくなる) (そのような長さが存在しない場合, 失敗). 制約 …

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 の状態から, の操作を3回行うと, は何になるか? 制約 解法 求めるべきは である. これは を入力で受け取った後, で求めることができる.

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 長さが の整数列 がある. これらはそれぞれ以下で与えられる. の最初の 項は , 続く 項は 最後の 項は は の累積和 は の累積和 このとき, を求めよ. 制約 解法 整数列 をそれぞれ 項, 項, 項で分割する. 分…

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

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 筒の中にボールを入れていく. 各ボールには 以上の整数が書かれている. と書かれたボールが筒の中で 個連続すると, その 個は消滅する. 番目には と書かれたボールを入れるとき, それぞれに対して, 番目のボ…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 以下を満たす列 は存在するか? 制約 解法 この問題はある意味での部分和問題である. そして, がそれほど大きくはないので, 今回は動的計画法で解くことにする. で まで決めたとき, 和を にすることができる…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 個の整数 に現れる整数の種類数を求めよ. 制約 解法 求めるべき答えは集合 の濃度 (元の個数) と等しい. よって, 集合 を作り, の濃度を調べれば良い.

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 問題文の図 (問題 URL 参照) にある十角形において, と書かれている点と と書かれている点は直接結ばれているか? 制約 解法 と書かれている点と と書かれている点が直接結ばれているための必要十分条件は で…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 頂点 辺のグラフ が与えられる. 以下を満たすような拡大グラフ は存在するか? 存在するならば条件を満たす における の一例を求めよ. はサイズ (辺の数) が の連結グラフ に対して, である. 制約 解法 条件…

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

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 高橋君と青木君が以下のゲームを行う. 高橋君は 以上 以下の整数 を1つ選び, 青木君に伝える. 青木君は 以上 以下の整数 を1つ選ぶ. が素数ならば青木君の勝ち, 素数でなければ高橋君の勝ち. 両者が勝利のた…

問題 atcoder.jp 提出解答 (解法1) atcoder.jp (解法2) atcoder.jp 問題の概要 次を満たす平面上の点 は存在するか? . つまり, は格子点 制約 解法1 整数 に対する方程式 の解は の8個に限られる. よって, との距離が である格子点は 個だけである. このよう…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 を求めよ. 制約 解法 この問題を解くためには自分が使っている言語の性質について注意しなければならない. 例えば, が正のとき, が何を意味するか? がある. よく使われる C++, Python においては C++ では …

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 地上 メートルから見える水平線は メートル先であると知られている. この計算式において, 地上 メートルから見える水平線の高さを求めよ. 制約 解法 整数 受け取り, 実数として を出力すれば良い. ただし, …

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 非負整数列 に対して, 次の操作を 回以上行う. を選ぶ. このとき, 操作後の の最大値を求めよ. 制約 解法1 (操作後の整数列) 操作後の にどのような特徴があるかをみる. まず, 1回も操作しないことで, 自身…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 次を満たす長さ の整数列 は存在するか? 存在するならばその一例を挙げよ. 制約 解法 と固定すると, 2つ目の条件から, は (整数の範囲で) 一意に定まる. 以降では を固定した際の を と書くことにする. この…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 黒板には整数 が書かれている. 以下の操作を任意回行う. 黒板に書かれている整数を1つ選び, それを とする. 黒板に書かれている を1つ消し, を書き加える. この操作後, 黒板に書かれている整数の総積の最大…

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

問題 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 問題の概要 以下を全て満たす整数列の個数を求めよ. 長さ 各項は 以上 以下 最長増加部分列の長さがちょうど ただし, 最長増加部分列は狭義単調増加な部分列に対して適用される. 制約 解法 LIS を求める方法はいくつか…

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

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 数列 と長さ の からなる文字列 が与えられる. 以下を の順に処理し, 完成する数列を求めよ. ならば, にある のすぐ左に を挿入する. ならば, にある のすぐ右に を挿入する. 制約 は からなる文字列 解法 …