問題 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 問題の概要 同じ日における 時 分 秒は 時 分 秒よりも前か? 後か? 制約 解法 基本的に, 同じ日における時間の判定は (時, 分, 秒) の辞書式順序によって判定できる. よって, であるから, これをそのまま判定すればよい.

問題 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 問題の概要 最初, 原点にいて, 軸正の向きを向いている. 文字列 に対して, の順に次のように行動する. ならば, 今向いている方向に 進む. ならば, その場で時計回りに 回転する. 回の行動終了後にいる座標を答えよ. 制…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 長さ の英小文字列 の末尾の文字を出力せよ. 制約 は英小文字からなる文字列 解法 実際に, を受け取ったあと, の末尾を出力すれば良い. ちなみに, の長さは なので, の末尾とは, の 文字目でもある, 多くの…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 からなる列 がある. この に対して, 次の操作を1回だけ行う. 連続する区間 (空も認める) を選び, その区間にある要素を元が ならば に, ならば にする. 操作後の列 に対して, とする. 操作後の列 に対して, …

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 を求めよ. 制約 解法 素数の間隔 - Wikipedia このサイトによると, 以下において, 素数の間隔は高々 である. ここで, 以下の最大の素数を とすると, の中に の倍数でない整数 が存在して, である. よって, …

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 次を満たす長さ の列 の個数を求めよ. に対して, に対して, である. 個のテストケース 制約 解法 1 まず, である. なので, とした は を意味する. より, 「長さ 」は「長さ (可算) 無限」に置き換えても良い…

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

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 重みつき連結無向グラフ が与えられる. ただし, である. このとき, 以下を満たす の部分集合 のサイズの最大値を求めよ. は連結. ただし, 連結グラフ と に対して, で 間の距離とする. 制約 は単純無向連結…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 頂点からなる完全二分木があり, 個の頂点にはそれぞれ と名付けられている. ここで, この二分木は以下のようにして構成されている. に対して, 頂点 の左の子, 右の子はそれぞれ である. 最初, 頂点 がマーク…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 人の人が座標平面上の異なる地点におり, 番目の人は にいる. また, それぞれの人は右か左を向いており, ならば右を向いている ならば左を向いている 確認が同じ速さで等速直線移動しはじめたとき, 衝突は発…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 各項が異なる長さ の整数列の が与えられる. 以下を満たす整数の個数をそれぞれ求めよ. に共通して存在し, その場所も一致する整数 に共通して存在するが, その場所は異なる整数 制約 は全て異なる は全て異…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 高橋家では毎日父が [ml], 母が [ml], 高橋くんが [ml] のシャンプーをこの順に使用する. ある日, 最初シャンプーは [ml] あった. 途中でシャンプーを継ぎ足さない場合, 初めてシャンプーが不足するのは誰が…

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

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 以下を満たす文字列 の個数を求めよ. は英大文字からなる長さ の文字列 は辞書式の意味で である回分. ※ 個のマルチケース 制約 は英大文字からなる長さ の文字列 個のケースにおける の総和を とすると, で…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 からなる文字列 が与えられる. 文字列の列 を以下のようにして生成する. は の各文字において, を に, を に, を に同時に置き換えてできる文字列. 次の 個の問 に答えよ. の先頭から 文字目は何か? 制約 は…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 次を見たす整数 の個数を求めよ. 桁の正の整数 の各桁を としたとき, 以下を満たす. 制約 解法 各桁の数字が 以上 以下の 桁の整数と長さが で各桁が 以上 以下の整数からなる整数列を同一視する. 動的計画…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 英小文字からなる文字列 が与えられる. を並び替えてできる文字列のうち, 辞書式最小の文字列を求めよ. 制約 は英小文字からなる文字列 解法 辞書式順序の最小化より, 先頭から決定していく. 文字目について…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 あるプログラミングコンテストでは, 以下のようにして参加者に T シャツをプレゼントする. 上位 位以上の人全員 上位 位以下, 上位 位以上の人から一様に抽選で 人 同率がないとき, 位の人が T シャツを貰え…