問題 提出解答 問題の概要 制約 解法 問題 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 問題の概要 で初期化されているカウンタがある. に対して, 毎日 時に以下を行う. のとき, % の確率で高橋君がカウンタを 増やす. のとき, % の確率で青木君がカウンタを 増やす. ある日の 時直前からにこの一連の行動を…

問題 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 問題の概要 の順列 に対して, スコア を次のように定める. を順序を保ったまま, 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 問題の概要 次を満たす長さ の列 の個数を求めよ. に対して, に対して, である. 個のテストケース 制約 解法 1 まず, である. なので, とした は を意味する. より, 「長さ 」は「長さ (可算) 無限」に置き換えても良い…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 長さ の整数列 が与えられる. 次の 個の問 に答えよ. 以下を満たす最大の を求めよ. 個の整数 は互いに異なる. 制約 解法 まず, が与えられたときの答え を考える. で にある の数とする. すると, となるこ…

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

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 の並び替え が与えられる. 次の 個のクエリを順に処理した場合, はどこにあるか? のとき, を昇順に並び替える. のとき, を降順に並び替える. 制約 は の並び替え 解法 求めるのは最終的な の位置である. そ…

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

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

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 個の変数 があり, 最初は全て である. ここで, 以下を計 回実行する. 以上 以下の整数 を等確率 (各回ごとで独立) で選び, に を加算する. この操作後の の期待値を求めよ. 制約 入力はすべて整数 解法 とな…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 重複がない正の整数の列 があり, 以下のゲームを行う. ただし, 正の整数の列 に対して, で, の全ての要素における XOR とする. 先手から次の行動を交互に行う. から1要素取り除く. そのとき, ならば, その人…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 グラフ の最大マッチングの大きさを とする. 木 に対し, を満たす頂点の数を求めよ. 制約 グラフは木 解法1: を求める. まず, を求めることにする. 木DP で求めることにする. を適当な頂点 を根とする根付き…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 二項係数 の正の約数の個数を求めよ. 制約 解法 約数に関する問題なので, 素因数分解に着目する. である. ここで, で正の素数全体の集合として, で表せるとき, 各素数 に対して, とすると, 任意の素数 に対…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 縦 行, 横 行からなるマス目がある. マス にバツ印を書くと, 点入る. 一方で, 1本の斜め線を引くごとに 点失う. ここで, 斜めに隣接するマスに対して, 斜め線はまとめて引くことができる. 最大で獲得できる…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 変数 があり, 最初, と設定されている. 以下の2つの操作を好きな回数できる. のとき, 円払って とする. 円払って, とする. ただし, は の中から当確率でランダムに選ぶ関数. にするための費用の期待値を最小…