問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 有向グラフ が与えられる. 部分有向グラフ を として, とする. に対して, 次を満たすような は存在するか? 存在するならば最小値を求めよ. において, 頂点 から へちょうど 本の有向辺をたどって移動できる.…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 を 以下の正の整数の集合とする. の部分集合で以下を満たすような 全体の集合を とする. として, を適当に選ぶことで, とできる. このとき, を求めよ. 制約 解法 xor 演算は有限体 を係数体するベクトル空間…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 枚のカードがあり, 左から 番目には と書かれている. この [tex; N] 枚から何枚かのカードを取り出す. ただし, 2枚連続で取り出さないことは禁止されている. 可能な取り出し方全てを考えたとき, 取り出した…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 二重添字整数列 が与えられる. ただし, である. の並び替え全体の集合を とするとき, を求めよ. 制約 *1 解法1 (計算量の見積もり) のペアの作り方を考える. すると, 作り方の場合の数は であり, とすると, …

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 個の駅があり, 普通列車は駅 の順に停まる. 一方, 急行列車は駅 の順に停まる. に対して, 駅 には急行列車が停まるかどうかを判定せよ. 制約 は長さが 以上 以下の英小文字からなる文字列 は の部分列 解法 …

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 と書かれたカードが 枚ずつ, 合計 枚ある. この中から 枚抜き出した. 残りの 枚に書かれている整数は である. 抜き出したカードに書かれている整数は何か? 制約 に対して, となる は 個以下 解法 の中にある…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 文字列 の 文字目と 文字目を入れ替えた文字列を答えよ. 制約 は英小文字からなる文字列 解法 を受け取って, の 文字目と を入れ替えた後にその文字列を出力すれば良い. 文字列, 整数の受け取り方, 一番左の…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 から の並び替え が与えられる. 以下を満たすような整数列 における長さの最大値を求めよ. 制約 は の並び替え. 解法 動的計画法を考える. を第 項目までみて, 特に と をマッチングさせるような取り出し方…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 整数列 が与えられる. に存在する整数 を1つ選び, から を全て取り除く. この操作によってできる列 のうち, 辞書式最小であるものを求めよ. 制約 解法 として を選んだときに完成する列を と書く. 指定すべ…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 株のリンゴの苗, 株のバナナの苗, 株のサクランボの苗がある. これらの苗を 個の庭に植える. ただし, 以下の条件を満たさなければならない. (a) 全ての庭には少なくとも1株以上の苗を植える. (b) 1つの庭に…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 個の部署からなる会社があり, 番目の部署の人数は である. 以下を満たす 人からなるグループをいくつか作るとき, そのグループの数の最大値を求めよ. どのグループにおいても, 人の属する部署は全部異なる. …

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 重み付き連結無向グラフ が与えられる. ただし, である. 以下の質問に 回答えよ. とする. 以下で構成される重み付き無向グラフ の最小全域木に辺 は含まれているか? ただし, とする. ここで, 以下のことが証…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 整数 に対して, 以下の操作を行い, を更新していく. で, が の倍数ではないとき, の末尾の数字を先頭に移動させる. 最初, であるが, 操作を繰り返すことにより, にすることは可能か? 可能ならば操作回数の最…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 長さ の列 が与えられる. 次の 個の質問に答えよ. ただし, 番目の質問は整数の組 で与えられる. の項を第 項から見たとき, が 回目に登場するのは の第何項目か (存在しない場合, その旨を報告せよ)? 制約 …

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 個の台があり, 番目の台の高さは である. 最初, 一番左の台の上に立っている人は以下の規則に従ってできるだけ行動をする. 今立っている台が一番右の台でなく, 右隣の台の高さが今立っている台の高さよりも…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 個の数字 をこの順に並べてできる 桁の整数を とする. を求めよ. 制約 解法 なので, である.

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 から連続とは限らず1文字以上抜き出した後, 並び替えることでできる文字列はいくつか? 制約 は英小文字からなる文字列 解法 で英小文字全体の集合とし, と文字列 に対して で に含まれる の数とする. 非空文…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 整数の10進法表記において, 各桁の数字が左から等差数列になるとき, その整数は等差列であるという. 以上の最小の等差列を求めよ. 制約 解法 長さが有限の等差数列は初項 と公差 と長さ で完全に決定づけら…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 の並び替え が与えられる. に対して, 以下を求めよ. において 番目に大きい整数 制約 は の並び替え. 解法 各 ごとに 番目を求めていくと, 計算量 で間に合わないが, 出力すべき整数は単調増加になっている.…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 進法において からなる正の整数のうち, 番目に小さいものを正確に求めよ. 制約 解法 問題文の を に置き換えると, その問題文は, 「 の2進表記を求めよ」と等価になることがわかる. よって, の2進表記を求め…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 座標平面上に相異なる 点があり, 番目の点の座標は である. この 点から 点を選ぶとき, その 点を端点とする線分の長さの最大値を求めよ. 制約 解法 2点を選ぶ方法は 通りで, としても 通りと非常に小さい. …

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 とする. このとき, を求めよ. 制約 解法 問題文の通りに関数 を実装し, 問題文のように求めるべき式を計算させれば良い.