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

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

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 無向グラフ を以下で定義する. それぞれに対して, 次を満たす の全域部分グラフ の個数を求め, で割った余りを求めよ. は連結 制約 は素数 解法 以降では説明のために, 本の辺をそれぞれ と名付けることにす…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 を英小文字からなる集合 *1, に対して, で からなる長さ の文字列全体の集合とする. このとき, の濃度 (元の個数)を求めよ. 制約 解法 以下の包除原理を利用する. 包除原理 を集合, を部分集合とする. この…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 単純有向グラフ が与えられる. 無限長の有向パスが存在するような始点の候補はいくつか? 制約 は単純 解法1 上の関係 を を始点, を終点とする有向パスが存在する と定義する. すると, この は反射律と推移…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 頂点 辺の単純無向連結グラフ が与えられる. からなる長さ の列に対して, 以下を満たすような列 のうち, の最小値を と書くことにする. ならば, の中に が偶数回登場する. ならば, の中に が奇数回登場する.…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 1回引くと, 種類の賞品のうちどれか1種類が1個貰えるくじがある. 番目の賞品が貰える確率は である. また, 各回は独立である. このくじを 回引いたあと, 貰えた賞品がちょうど 種類である確率を求めよ. 制約…

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

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

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

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

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

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 の並び替え が与えられる. 以下の操作を 回以下行って, にできるか? となる整数 を選び, を入れ替える. 可能ならばその一例をあげ, 不可能ならばその旨を報告せよ. 制約 この問題は以下の問題と同じである. …

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 2つの整数列 が与えられる. 列 に対して, 以下の操作を任意回できる. 円払い, を選び, の値を 増やすか, 減らす. 円払い, を選び, を入れ替える. この操作によって, を に一致させるために, かかる合計費用…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 長さが の2つの列 が与えられる. 以下を満たす整数の組 はいくつか? かつ 制約 入力はすべて整数 解法 まず, かつ という条件については順序だけを見ていることから, 座標圧縮を行うことで, としてもよい. …

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 外周が 頂点からなる車輪グラフ がある. ただし, ユニバーサル頂点は頂点 , 外周はある頂点から反時計回りに頂点 と名付けられている. 各辺に以下のように重みが設定されている. 辺 の重みは である. 辺 の…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 の置換 に対して, を以下で定義する. (恒等置換) を満たす最小の正の整数 の置換 全てにおける の総和を求めよ. 制約 解法 置換 に対して, は の位数である. ここで, 置換において, 以下の性質がある. 任意…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 から までの数字のみで構成される文字列 に対して, 以下のような操作を行い, 文字列 を行う. 個ある文字の間それぞれに対して, を挿入するか, 何もしない. そして, を計算式と満たしたときの計算結果を とす…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 からなる長さ の文字列 が与えられる. 以下の 個のクエリを順に処理せよ. の 文字目と 文字目を入れ替える. の 文字目から 文字目までの部分文字列が正しい文字列かどうかを判定する. 制約 は からなる長さ …

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 頂点からなる重み付き木がある. それぞれの辺は を結び, 重みは である. そして, 各頂点には整数 が指定されている. を 最短路の重みと の和とする. このとき, に対して, 以下の値を求めよ. 制約 解法 全方…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 頂点の木 が与えられる. の直径を とする. このとき, 以下の条件を満たす部分集合 の個数を求めよ. . ただし, は における頂点 間の距離 制約 解法 において, となる2つの頂点 を取ってくる. なお, この は …