300 pts
問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 正の整数 に対して, を次のように定める. を次のようにして定める: の十進表記を左右反転して, 先頭の を削除できるだけ削除した整数を とする. となる整数のうち, を満たす整数はいくつか? 制約 解法 の作…
問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 3行3列からなるマス目がある. この 個のマス目のそれぞれに整数を書くとき, 以下を全て満たすような整数の書き込み方は何通りか? 整数は全て正の整数. 上から 行目に書いた 個の整数の総和は である (). 左…
問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 初項 , 公差 , 項数 の等差数列を とする. 最初, 整数 が与えられる. が の要素であるようにするために, 以下の操作は最低でも何回 ( 回以上) しなければならないか? 次のうちどちらかを選び実行する. に 加…
問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 長さが の整数列 がある. この列に対して, 以下の操作を0回以上行い, を昇順に並び替えることができるか? 以上 以下の整数 を選び, と を入れ替える. 制約 解法 以下では数列の添字を1ずつ減らして 0-indexe…
問題 atcoder.jp 提出解答 (ヒープ) atcoder.jp 問題の概要 多重集合 がある. 最初, は空集合である. 次の 個のクエリを順に処理せよ. Type 1: に を 個追加する. Type 2: から を 個削除する. ただし, は にある の個数. Type 3: を出力する. 制約 Type 3 …
問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 個の がちょうど 回ずつ現れる文字列 がある. 各リールは停止していない限り表示が毎秒 と変化する. 秒あたり高々 個のリールを停止させることができるとき, 全てのリールが停止した上で同じ整数を表示させ…
問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 次を満たす正の整数列 を一つ構成せよ. 以上 以下の全ての整数 に対して, 以下が成立する. から異なる要素を高々 個選び, その和を にすることができる. 制約 解法 の場合の を構成できればよいので, とする…
問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 個のポエム と, 各ポエムに対する得点 がある. 次を満たすようなポエム はオリジナルであるという. を満たす全ての整数 に対して, である. オリジナルのポエムのうち, 得点が最大であるのはどれか? なお, 同…
問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 長さ の整数列 がある. 最初, である. の順に以下のようにして に対して操作する. ならば, として, を入れ替える. ならば, を入れ替える. 最終的な を求めよ. 制約 解法 数列 だけでなく, 次のようにして, …
問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 正の整数 に対して, を2進表記した際に末尾に連続する の数を と書くことにする. 次を満たす長さ の正の整数列 において, の最小値を求めよ. は狭義単調増加 制約 解法 正の整数 と非負整数 に対して, 以下…
問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 英小文字からなる 個の文字列 がある. の中から好きな個数を選び抜く. このとき, 「「選んだ文字列において, ちょうど 個の文字列にその英小文字が存在する」を満たす英小文字の個数」の最大値を求めよ. 制…
問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 以下を満たす長さ の整数列 の個数を求めよ. 制約 解法 動的計画法で解く. で, 先頭 項まで決定し, 和が になるような整数列の個数とする. ベースケースは である. 更新式は, 第 項で分割することにすると, …
問題 atcoder.jp 提出解答 解法 1 atcoder.jp 解法 2 atcoder.jp 解法 3 atcoder.jp 問題の概要 整数の列の列 を以下で定める. を求めよ. 制約 解法 解法 1 に関する漸化式が与えられているので, この漸化式を利用して再帰的に求めることができる. また, の…
問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 個の商品があり, 番目の商品は 円である. クーポンを 枚持っており, 円の商品に対して 枚のクーポンを消費すると, その商品を 円で買うことができる. 全ての商品を買うためには最低でも何円必要か. 制約 解…
問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 長さ の正の整数列 が与えられる. 以下を満たす非正の整数列 は存在するか? または 制約 解法 を の順で決めていこうとすると, の決定に必要な情報は だけである. また, か であることから, 次のような動的…
問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 インタラクティブ問題 自分とコンピュータで以下のゲームを行う. 自分から交互に 以上 以下の整数のうち, まだ宣言していない整数を つ宣言する. 先に宣言できなくなったほうが負け. このゲームにおいて, う…
問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 を求めよ. 制約 解法 素数の間隔 - Wikipedia このサイトによると, 以下において, 素数の間隔は高々 である. ここで, 以下の最大の素数を とすると, の中に の倍数でない整数 が存在して, である. よって, …
問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 人の人が座標平面上の異なる地点におり, 番目の人は にいる. また, それぞれの人は右か左を向いており, ならば右を向いている ならば左を向いている 確認が同じ速さで等速直線移動しはじめたとき, 衝突は発…
問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 次を見たす整数 の個数を求めよ. 桁の正の整数 の各桁を としたとき, 以下を満たす. 制約 解法 各桁の数字が 以上 以下の 桁の整数と長さが で各桁が 以上 以下の整数からなる整数列を同一視する. 動的計画…
問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 からなる長さ の文字列 が与えられる. に対して, 以下の操作を 回以上行ってできる文字列のうち, 辞書式最小のものを求めよ. にある を に置き換える. にある を に置き換える. 制約 は からなる長さ の文字…
問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 行 列のマス目にはそれぞれ白または黒で塗られている. 高々 個の白マスを黒マスに塗り替えることにより, 縦横斜めの向きに 個以上黒マスを連続させることは可能か? 制約 解法 ある方向に連続する6マスにおい…
問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 以下を満たす列 は存在するか? 制約 解法 この問題はある意味での部分和問題である. そして, がそれほど大きくはないので, 今回は動的計画法で解くことにする. で まで決めたとき, 和を にすることができる…
問題 atcoder.jp 提出解答 (解法1) atcoder.jp (解法2) atcoder.jp 問題の概要 次を満たす平面上の点 は存在するか? . つまり, は格子点 制約 解法1 整数 に対する方程式 の解は の8個に限られる. よって, との距離が である格子点は 個だけである. このよう…
問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 黒板には整数 が書かれている. 以下の操作を任意回行う. 黒板に書かれている整数を1つ選び, それを とする. 黒板に書かれている を1つ消し, を書き加える. この操作後, 黒板に書かれている整数の総積の最大…
問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 を以下を満たす正の整数の個数とする. 以下 と桁数が等しい. このとき, を求めよ. 制約 解法 が 桁の整数のとき, である. よって, が 桁の整数であるとすると, である. ここから更に式変形を進めてもよいが,…
問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 文字列 が与えられる. この の先頭に 個以上の を加えて, 回分にできるか? 制約 は英小文字からなる文字列 解法 が からなる文字列だった場合, 答えは明らかに Yes なので, 以降ではそうでないとする. ここ…
問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 個の駅があり, 普通列車は駅 の順に停まる. 一方, 急行列車は駅 の順に停まる. に対して, 駅 には急行列車が停まるかどうかを判定せよ. 制約 は長さが 以上 以下の英小文字からなる文字列 は の部分列 解法 …
問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 整数列 が与えられる. に存在する整数 を1つ選び, から を全て取り除く. この操作によってできる列 のうち, 辞書式最小であるものを求めよ. 制約 解法 として を選んだときに完成する列を と書く. 指定すべ…
問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 長さ の列 が与えられる. 次の 個の質問に答えよ. ただし, 番目の質問は整数の組 で与えられる. の項を第 項から見たとき, が 回目に登場するのは の第何項目か (存在しない場合, その旨を報告せよ)? 制約 …
問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 進法において からなる正の整数のうち, 番目に小さいものを正確に求めよ. 制約 解法 問題文の を に置き換えると, その問題文は, 「 の2進表記を求めよ」と等価になることがわかる. よって, の2進表記を求め…