問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 縦 行, 横 列のマスからなる将棋盤と, 黒の飛車 個, 白の飛車 個がある. この将棋盤に 個の飛車を置く. 以下を満たすような置き方は何通りか? 個の飛車全てが置かれている. 各マスに置かている飛車は高々1個…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 正の整数 に対して, を2進表記した際に末尾に連続する の数を と書くことにする. 次を満たす長さ の正の整数列 において, の最小値を求めよ. は狭義単調増加 制約 解法 正の整数 と非負整数 に対して, 以下…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 で初期化された変数 がある. の順に以下の操作を行う. ならば, ならば, ただし, この 個の操作のうち, 高々 個の操作を無視することができる. このとき, 最終的な の最大値を求めよ. 制約 解法 のときの操作…

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

問題 atcoder.jp 提出解答 解法1 atcoder.jp 解法2 atcoder.jp 問題の概要 長さ の整数列 が与えられる. 次を満たす整数のトリプル *1 を求めよ. 制約 解法 で にある の個数を表すとする. また, なので, 求めるべきは である. 従って, を満たすトリプル を…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 英小文字からなる 個の文字列 がある. の中から好きな個数を選び抜く. このとき, 「「選んだ文字列において, ちょうど 個の文字列にその英小文字が存在する」を満たす英小文字の個数」の最大値を求めよ. 制…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 英大文字, 英小文字からなる文字列 がある. は以下の3個の条件を全て満たすか? の中に英大文字が存在する. の中に英小文字が存在する. に現れる文字はすべて異なる. 制約 は英大文字, 英小文字からなる文字…

問題 atcoder.jp 提出解答 解法1 atcoder.jp 解法2 atcoder.jp 問題の概要 高橋君と青木君は次のようにジョギングする. 高橋君: 「 秒間秒速 メートルで歩き, 秒間休む」を繰り返す. 青木君: 「 秒間秒速 メートルで歩き, 秒間休む」を繰り返す. 2人が同時に…

問題 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. ここで, 整数 と整数 に対して, …

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 空の筒がある. 次の 個のクエリを順に処理せよ. (Type 1) と書かれたボールを 個筒の右から入れる. (Type 2) 筒の左から のボールを取り出し, 取り出したボールに書かれている数の総和を求め, 出力する. 制…

問題 atcoder.jp 提出解答 解法 1 atcoder.jp 解法 2 atcoder.jp 解法 3 atcoder.jp 問題の概要 整数の列の列 を以下で定める. を求めよ. 制約 解法 解法 1 に関する漸化式が与えられているので, この漸化式を利用して再帰的に求めることができる. また, の…

問題 atcoder.jp 提出解答 解法1 atcoder.jp 解法2 atcoder.jp 問題の概要 英小文字からなる 個の文字列 がある. 次を満たすような 個の英小文字の組 は存在するか? に対して, または に対して, 以下が成立: かつ を満たす全ての整数に対して, 制約 は長さ …

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 横一列に4個のマスが並んでいる. 長さ の からなる文字列 が与えられる. の 文字目が ならば, 左から マス目に人がおり, ならばそこにはいない. 全員が1個右のマスに移動する (一番右端のマスにいる人は消え…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 長さ の非負整数列 の先頭 項の総和を と書くことにする. とする. に対して, 隣接項の入れ替えを何回か行い, 操作後の整数列を としたとき, とできるか? できる場合, その入れ替えの最小回数を求めよ. 制約 …

問題 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 問題の概要 平面上に長方形がある. この長方形の各辺はどちらかの軸に平行であり, 面積は ではない. また, 長方形の4個の頂点のうち, 3個は であることがわかっている. 残りの1頂点を求めよ. 制約 を頂点に持つ条件を満…