AOJ
愚直にやると 本の辺がある問題に対して、上手にやる系の問題 問題へのリンク 問題概要 グリッドグラフがある。 広義単調増加な正整数列 があり、それぞれの長さは となっている。 頂点 と頂点 は、重みが である無向辺で結ばれている 頂点 と頂点 は、重み…
近年非常によく見る DP 高速化系問題！！ 問題へのリンク 問題概要 長さ の 3 つの数列 が与えられる。 いま、数列 をいくつかの連続する部分列に分割することを考える。 分割 に対して、スコアを、各区間についての以下の値の最小値として定める。 その区間…
山登り法で見つかった！スコアが下がっていくのを眺めるの快感！ 問題へのリンク 問題概要 のグリッドに以下の条件を満たすように英小文字を入れよ。 横方向、縦方向に連結しているマス目を抜き出してできる文字列は 個ある そのすべてが互いに相異なる これ…
こういう条件を言い換えながら数え上げる問題好き！ 問題へのリンク 問題概要 タプリスちゃんは現在、長さ 1 の数列 を持っている。 タプリスちゃんは に対して、以下のいずれかの操作を選んで行うことを 回繰り返すことにした。 の末尾に または を追加する…
面白かった 問題へのリンク 問題概要 という 個の整数がある。これらを 2 個以上のグループに分ける。各グループの整数の総和が互いに等しくなるようにグループ分けすることが可能かどうかを判定し、可能ならば具体例を構築せよ。 制約 考えたこと こういう…
DP 高速化系問題 問題へのリンク 問題概要 のグリッドが与えられる。各マス には数値 が書かれている。 各行から 1 個ずつ数値を選んで行順に並べてできる数列を考える。そのような数列は 通り考えられるが、そのうち広義単調増加なものが何通りあるか、1000…
これが生まれて初めての作問だった！！！ AOJ-ICPC で ☆4 個ついてて嬉しい！ 問題へのリンク editorial 問題概要 虫食算が与えられる。解の個数を 1000000007 で割ったあまりを求めたい。 より正確には長さ の 3 個の文字列 が与えられる。これらは '?' か …
めちゃくちゃ面白かったし勉強になった！ 問題へのリンク editorial 問題概要 文字列 が与えられる。それとは別に 個の文字列 が与えられる。 文字列 をいくつかの連続する区間に分割する方法であって、各区間をなす部分文字列が のいずれかに一致するような…
めちゃくちゃ面白かった！ 問題へのリンク editorial 問題概要 個のカッコ列 が与えられる。これらを並び替えて連結して 1 個の文字列を作る。 この文字列が「整合のとれたカッコ列」となるようにすることが可能かどうかを判定せよ。 制約 考えたこと 大前提…
多倍長整数を活用した、重み付き二部マッチング 問題へのリンク editorial 問題概要 のグリッドが与えられる。各マスにはアルファベット (英大文字と英小文字) が描かれている。今、次の条件を満たすように 個の文字を抜き出す 各行から選ぶマスはちょうど 1…
LCA ライブラリを持っていれば書くだけ！ 問題へのリンク editorial 問題概要 頂点の根付き木が与えられる (根は頂点 0)。この木上で幅優先探索を行う (隣接する頂点のうち、頂点番号が小さい順にキューに push する)。 このとき、探索順序が であったとした…
頭整理するのが大変だった 問題へのリンク editorial 問題概要 個の格子点 (、、) がある。 これらの格子点を以下のルールに則って 色 () で塗る。 点 の、 とのマンハッタン距離が であるとき 点 を、色 % で塗る 各 について、その色で塗られた格子点が何…
素直に考えるとグラフの辺数が のオーダーになってしまうので、いかに削減するかを考える問題だった 問題へのリンク editorials 問題概要 頂点数 、辺数 の単純無向グラフが与えられる。各頂点 には値 が振られている。今、各頂点にスコア を割り振りたい。…
英文だし、題意をちゃんと読み解くのがちょっと大変 問題へのリンク editorial 問題概要 L と R のみから構成された文字列 が与えられる。ロボットは最初北方向を向いている。文字列 を左から順番に読んで次のように処理していく。 L のとき、ロボットは 90 …
この手の、単純だけど for 文ネストがエグい全探索、案外 AtCoder で見ないかもしれない 問題へのリンク 問題概要 の二次元グリッドが与えられる。各グリッドには 0 以上 9 以下の整数値が書かれている。 グリッド上で、以下の条件を満たす長方形領域を考え…
平均求めるだけ 問題へのリンク 問題概要 個の 0 以上の整数 が与えられる。これらの値のうち、最大値と最小値を除去する (複数あるときはそのうちの 1 つ)。 残った 個の値の平均値 (小数点以下切り捨て) を求めよ。 制約 データセット数 考えたこと ででき…
これ面白い！！ 問題へのリンク editorials 問題概要 個の正の整数 と、正の整数 が与えられる。 個の整数の中からいくつか選ぶ方法のうち、以下の条件を満たすものの個数を 1000000007 で割ったあまりを求めよ。 選んだ数の総和は 以下である 選んだ数の総…
内接円に続いて、外接円も 問題へのリンク 問題概要 二次元平面上に 3 点 A, B, C が与えられる。三角形 ABC の内接円の中心の座標と、半径を求めよ。誤差は まで許容。 制約 座標値の絶対値 考えたこと 内接円よりもやりやすい。 辺 AB の垂直二等分線 辺 B…
手持ちライブラリの組合せで内接円・外接円求めたりするの、結構楽しい！ 問題へのリンク 問題概要 二次元平面上に 3 点 A, B, C が与えられる。三角形 ABC の内接円の中心の座標と、半径を求めよ。誤差は まで許容。 制約 座標値の絶対値 考えたこと 角 A, …
こないだの ARC でめっちゃ似た問題が出たので！これは、SolveMe を含む、りんごさんによる伝説のセット。 drken1215.hatenablog.com 問題へのリンク 問題概要 頂点数 のグラフが与えられる (入力は の隣接行列で与えられ、初期状態では非連結である)。この…
ボロノイ図の応用問題！ 問題へのリンク editorials 問題概要 頂点数 の凸多角形があって、その内部に 個の点が与えられる。凸多角形の内部に一様ランダムに点を打つとき、以下の値の期待値を求めよ。 「その点 から 個の点までの距離の最小値」を二乗した値…
ボロノイ図 問題へのリンク editorials 問題概要 頂点の凸多角形と、その内部に 個の点が与えられる。それらの各 個の点に対して、以下の問に答えよ。 凸多角形のうち、その点に最も近い領域の面積を求めよ 制約 考えたこと まさにボロノイ図を求めよ、とい…
ボロノイ図！！ 問題へのリンク editorial 問題概要 頂点の凸多角形と、 個の点が与えられる。以下の条件を満たす最小の正の実数 を求めよ。 個の点を中心とした半径 の円を考える 凸多角形の周および内部のどの点も、いずれかの円に包含される 制約 考えた…
これ好き！！！ 問題へのリンク editorial 問題概要 の順列が与えられる。これらの順列のうち、 個を赤く塗り、 個を青く塗る方法であって、次の条件を満たすようにするものは存在するか、判定せよ。 赤い要素同士を swap することを好きな順序で好きな回数…
こういうのを素早く解けるようになりたい 問題へのリンク editorial 問題概要 頂点 辺の重み付き無向グラフがある。各頂点 には そこで売ってるパンを買ったときの美味しさ そこで売ってるジャムの種類 そこで売ってるジャムを買ったときの美味しさ という 3…
これ好き！！ 問題へのリンク editorial 問題概要 長さ の整数列 と、長さ の整数列 が与えられる。 すべての に対する % の値の総和を求めよ。 制約 考えたこと や の値が 以下であることがポイントに思えてくる。一般に に対して = % の総和がどう求められ…
テスターだった。 簡単枠の Easy ヴァージョンに対して「制約あげられるね」と提案して、正式に問題セットになった！ 問題へのリンク editorial 問題概要 のグリッドがあって、各マスは '.' か 'B' から成っている。'B' マス間のマンハッタン距離として考え…
この問題のテスターをやってた！ 今流行の NTT 系問題！！しかも分割統治 + FFT というカッコいいやつ！！ 問題へのリンク editorial 問題概要 'U', 'M', 'G' のみからなる長さ の文字列 の UMG 数を、以下の条件を満たす添字 の組の個数として定義する。 T[…
これの原案だった！！ 「対称戦略」が印象的なゲームの問題を作ろうとして作った 問題へのリンク editorial 問題概要 1 × 1 × 1 の立方体を の直方体形状に積み上げたものがある。これを使って 2 人でゲームする。 交互に、直方体のある面のあるマスを選んで…
二乗の木 DP を応用したもの。このセットの運営チームだった。 問題へのリンク editorial 北大アーカイブ 問題概要 頂点からなる木が与えられる。 この木の 個の空でない部分グラフの組であって、各部分グラフがいずれも連結で、どの二つの相異なる部分グラ…
