けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AOJ

AOJ 2566 Restore Calculation (JAG 模擬地区 2013 B)

これが生まれて初めての作問だった!!! AOJ-ICPC で ☆4 個ついてて嬉しい! 問題へのリンク editorial 問題概要 虫食算が与えられる。解の個数を 1000000007 で割ったあまりを求めたい。 より正確には長さ の 3 個の文字列 が与えられる。これらは '?' か …

AOJ 2863 Separate String (JAG 模擬地区 2017 H)

めちゃくちゃ面白かったし勉強になった! 問題へのリンク editorial 問題概要 文字列 が与えられる。それとは別に 個の文字列 が与えられる。 文字列 をいくつかの連続する区間に分割する方法であって、各区間をなす部分文字列が のいずれかに一致するような…

AOJ 2681 Parentheses (AOJ-ICPC 500 点)

めちゃくちゃ面白かった! 問題へのリンク editorial 問題概要 個のカッコ列 が与えられる。これらを並び替えて連結して 1 個の文字列を作る。 この文字列が「整合のとれたカッコ列」となるようにすることが可能かどうかを判定せよ。 制約 考えたこと 大前提…

AOJ 2679 Decoding Ancient Messages (AOJ-ICPC 550 点)

多倍長整数を活用した、重み付き二部マッチング 問題へのリンク editorial 問題概要 のグリッドが与えられる。各マスにはアルファベット (英大文字と英小文字) が描かれている。今、次の条件を満たすように 個の文字を抜き出す 各行から選ぶマスはちょうど 1…

AOJ 2677 Breadth-First Search by Foxpower (AOJ-ICPC 400 点)

LCA ライブラリを持っていれば書くだけ! 問題へのリンク editorial 問題概要 頂点の根付き木が与えられる (根は頂点 0)。この木上で幅優先探索を行う (隣接する頂点のうち、頂点番号が小さい順にキューに push する)。 このとき、探索順序が であったとした…

AOJ 2678 Cube Coloring (AOJ-ICPC 450 点)

頭整理するのが大変だった 問題へのリンク editorial 問題概要 個の格子点 (、、) がある。 これらの格子点を以下のルールに則って 色 () で塗る。 点 の、 とのマンハッタン距離が であるとき 点 を、色 % で塗る 各 について、その色で塗られた格子点が何…

AOJ 2726 Black Company (AOJ-ICPC 450 点)

素直に考えるとグラフの辺数が のオーダーになってしまうので、いかに削減するかを考える問題だった 問題へのリンク editorials 問題概要 頂点数 、辺数 の単純無向グラフが与えられる。各頂点 には値 が振られている。今、各頂点にスコア を割り振りたい。…

AOJ 2904 GuruGuru (AOJ-ICPC 200 点)

英文だし、題意をちゃんと読み解くのがちょっと大変 問題へのリンク editorial 問題概要 L と R のみから構成された文字列 が与えられる。ロボットは最初北方向を向いている。文字列 を左から順番に読んで次のように処理していく。 L のとき、ロボットは 90 …

AOJ 1618 池のある庭園 (ICPC 国内予選 2017 C)

この手の、単純だけど for 文ネストがエグい全探索、案外 AtCoder で見ないかもしれない 問題へのリンク 問題概要 の二次元グリッドが与えられる。各グリッドには 0 以上 9 以下の整数値が書かれている。 グリッド上で、以下の条件を満たす長方形領域を考え…

AOJ 1147 ICPC 得点集計ソフトウェア (ICPC 国内予選 2007 A)

平均求めるだけ 問題へのリンク 問題概要 個の 0 以上の整数 が与えられる。これらの値のうち、最大値と最小値を除去する (複数あるときはそのうちの 1 つ)。 残った 個の値の平均値 (小数点以下切り捨て) を求めよ。 制約 データセット数 考えたこと ででき…

AOJ 2333 僕の友達は小さい (AOJ-ICPC 500 点)

これ面白い!! 問題へのリンク editorials 問題概要 個の正の整数 と、正の整数 が与えられる。 個の整数の中からいくつか選ぶ方法のうち、以下の条件を満たすものの個数を 1000000007 で割ったあまりを求めよ。 選んだ数の総和は 以下である 選んだ数の総…

AOJ Course CGL_7_C: 外接円 (Circumscribed Circle of a Triangle)

内接円に続いて、外接円も 問題へのリンク 問題概要 二次元平面上に 3 点 A, B, C が与えられる。三角形 ABC の内接円の中心の座標と、半径を求めよ。誤差は まで許容。 制約 座標値の絶対値 考えたこと 内接円よりもやりやすい。 辺 AB の垂直二等分線 辺 B…

AOJ Course CGL_7_B: 内接円 (Incircle of a Triangle)

手持ちライブラリの組合せで内接円・外接円求めたりするの、結構楽しい! 問題へのリンク 問題概要 二次元平面上に 3 点 A, B, C が与えられる。三角形 ABC の内接円の中心の座標と、半径を求めよ。誤差は まで許容。 制約 座標値の絶対値 考えたこと 角 A, …

AOJ 2376 DisconnectedGame (AOJ-ICPC 600 点)

こないだの ARC でめっちゃ似た問題が出たので!これは、SolveMe を含む、りんごさんによる伝説のセット。 drken1215.hatenablog.com 問題へのリンク 問題概要 頂点数 のグラフが与えられる (入力は の隣接行列で与えられ、初期状態では非連結である)。この…

AOJ 2385 Shelter (AOJ-ICPC 700 点)

ボロノイ図の応用問題! 問題へのリンク editorials 問題概要 頂点数 の凸多角形があって、その内部に 個の点が与えられる。凸多角形の内部に一様ランダムに点を打つとき、以下の値の期待値を求めよ。 「その点 から 個の点までの距離の最小値」を二乗した値…

AOJ 2160 Voronoi Island (AOJ-ICPC 450 点)

ボロノイ図 問題へのリンク editorials 問題概要 頂点の凸多角形と、その内部に 個の点が与えられる。それらの各 個の点に対して、以下の問に答えよ。 凸多角形のうち、その点に最も近い領域の面積を求めよ 制約 考えたこと まさにボロノイ図を求めよ、とい…

AOJ 3049 A Polygon And Circles (ACPC 2018 day2-K)

ボロノイ図!! 問題へのリンク editorial 問題概要 頂点の凸多角形と、 個の点が与えられる。以下の条件を満たす最小の正の実数 を求めよ。 個の点を中心とした半径 の円を考える 凸多角形の周および内部のどの点も、いずれかの円に包含される 制約 考えた…

AOJ 2955 Two Colors Sort (HUPC 2019 day2-D)

これ好き!!! 問題へのリンク editorial 問題概要 の順列が与えられる。これらの順列のうち、 個を赤く塗り、 個を青く塗る方法であって、次の条件を満たすようにするものは存在するか、判定せよ。 赤い要素同士を swap することを好きな順序で好きな回数…

AOJ 2956 ジャム (Jam) (HUPC 2019 day2-E)

こういうのを素早く解けるようになりたい 問題へのリンク editorial 問題概要 頂点 辺の重み付き無向グラフがある。各頂点 には そこで売ってるパンを買ったときの美味しさ そこで売ってるジャムの種類 そこで売ってるジャムを買ったときの美味しさ という 3…

AOJ 2957 MOD Rush (HUPC 2019 day2-F)

これ好き!! 問題へのリンク editorial 問題概要 長さ の整数列 と、長さ の整数列 が与えられる。 すべての に対する % の値の総和を求めよ。 制約 考えたこと や の値が 以下であることがポイントに思えてくる。一般に に対して = % の総和がどう求められ…

AOJ 2953 Hokkaido University Hard (HUPC 2019 day2-B)

テスターだった。 簡単枠の Easy ヴァージョンに対して「制約あげられるね」と提案して、正式に問題セットになった! 問題へのリンク editorial 問題概要 のグリッドがあって、各マスは '.' か 'B' から成っている。'B' マス間のマンハッタン距離として考え…

AOJ 2959 Revenge of UMG (HUPC 2019 day2-H)

この問題のテスターをやってた! 今流行の NTT 系問題!!しかも分割統治 + FFT というカッコいいやつ!! 問題へのリンク editorial 問題概要 'U', 'M', 'G' のみからなる長さ の文字列 の UMG 数を、以下の条件を満たす添字 の組の個数として定義する。 T[…

AOJ 2954 串刺し (Skewering) (HUPC 2019 day2-C)

これの原案だった!! 「対称戦略」が印象的なゲームの問題を作ろうとして作った 問題へのリンク editorial 問題概要 1 × 1 × 1 の立方体を の直方体形状に積み上げたものがある。これを使って 2 人でゲームする。 交互に、直方体のある面のあるマスを選んで…

AOJ 2958 Tree (HUPC 2019 day2-G)

二乗の木 DP を応用したもの。このセットの運営チームだった。 問題へのリンク editorial 北大アーカイブ 問題概要 頂点からなる木が与えられる。 この木の 個の空でない部分グラフの組であって、各部分グラフがいずれも連結で、どの二つの相異なる部分グラ…

AOJ 3165 Triangle Addition (HUPC 2020 day1-B)

いもす法 問題へのリンク editorial 問題概要 要素からなる数列がある。初期状態では全要素の値が 0 である。以下の 回の操作を行なって得られる数列を出力せよ。 各クエリでは整数 が与えられる。区間 に対して、初項 1、交差 1 の等差数列を加算する 制約 …

AOJ 3166 Not Found (HUPC 2020 day1-C)

単純に bit 全探索で良さそう。 問題へのリンク editorial 問題概要 長さ の 0 と 1 からなる文字列が 個与えられる ()。以下の条件を満たす文字列 が存在するかどうかを判定し、存在するならば具体例を一つ与えよ。 の長さは は '0' と '1' と '*' のみで構…

AOJ 3167 Many Points (HUPC 2020 day1-D)

面白かった! 問題へのリンク editorial 問題概要 次の問題が ケース分与えられる。 二次元平面上に 個の格子点が与えられる。これらに対し、以下の条件を満たす直線 が存在するかどうかを判定せよ。 どの点に対しても、 との距離が等しい 制約 考えたこと …

AOJ 3168 Capture Ebichan (HUPC 2020 day1-E)

アルファベットは 26 文字!26 は偶数! 問題へのリンク 問題概要 (意訳) 頂点数 、辺数 の無向単純グラフ が与えられる。各頂点 には、1 文字の英小文字 が振られている。ここで正の整数 が与えられ、改めて次のように定義されるグラフ を考える の頂点集合…

AOJ 3169 Pyramid Graph (HUPC 2020 day1-F)

ゴリ (prd さん) と一緒に出て楽しかったコンテスト。 そして「グラフのサイクル・パスの列挙」に関する問題は北大セットの定番というイメージになってきた。 問題へのリンク 問題概要 下図のような 角錐が与えられる (底面が 角形で "頂点" の頂点番号を 0 …

AOJ 3191 Watering (AUPC 2020 day3-G)

この問題に似てた drken1215.hatenablog.com 問題へのリンク editorial 問題概要 の順列 を最適化したい。以下の手順にしたがって、各要素 のスコアが定まる。この 個のスコアの最大値の最小値を求めよ。 値が のいずれかであるような数列 ( 項) が与えられ…