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

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

AOJ

AOJ 2644 Longest Match (JAG 夏合宿 2014 day4-F) (700 点)

Suffix Array の練習問題 問題へのリンク editorials へのリンク 問題概要 英小文字からなる文字列 と、 個のクエリが与えられる。 各クエリでは 2 つの文字列 が与えられる。 文字列 の連続する部分文字列であって、 で始まり、 で終わるものの中で、最長の…

AOJ 2207 無矛盾な単位系 (UTPC 2010 D)

これも重み付き Union-Find で解ける問題! 問題へのリンク editorial 問題概要 具体例として一つの入力ケースを示す。 7 1 kilometre = 10^3 metre 1 megametre = 10^3 kilometre 1 metre = 10^-6 megametre 1 terametre = 10^3 gigametre 1 petametre = 10…

AOJ 1330 Never Wait for Weights (ICPC アジア 2012 F) (500 点)

重み付き Union-Find の練習問題! 問題へのリンク 問題概要 個の値 があるが、それらの値がわからないので、特定したい。 次の 2 種類のクエリが 個、与えられるので順に処理せよ。 3 つの値 が与えられる。 であるという情報が与えられる。 2 つの値 を与…

JOIG 2021 D - 展覧会 2 (AOJ 0704, 難易度 6)

「競プロ典型 90 問 001 - Yokan Party」とよく似た問題! 問題へのリンク editorial 前提知識 基本的な二分探索 問題概要 枚の絵が一直線上に順に並んでいます。 枚目の絵は座標 の位置にあり、その価値は です。 今これらの絵から 枚の絵を選びます。この…

JOIG 2021 C - イルミネーション 2 (AOJ 0703, 難易度 4)

落ち着いて整理して考えましょう。問題自体は「累積和」が使える良い問題ですね! 問題へのリンク editorial 問題概要 個の電球を一列に並べていて、オンオフ状態が であるような状態を作りたいとします。ただし は 番目の電球をオンにしたいことを表し、 は…

AOJ 2345 Network Reliability (JAG 冬コン 2011 F) (700 点)

ABC 213 G の類題に挙がっていたのでやってみた! 問題へのリンク 問題概要 頂点数 、辺数 の単純無向グラフが与えられます。また 以上 以下の整数 が与えられます。 グラフの各辺は % の確率でそれぞれ独立に消失します。グラフ全体が連結である確率を求め…

JOIG 2021 A - 金平糖 (AOJ 0701, 難易度 1)

入出力の練習をしましょう。 問題へのリンク editorial 問題概要 3 人の生徒がそれぞれ 個、 個、 個の金平糖をもらいました。 これからそれぞれの生徒たちに何個かの金平糖を追加で渡すことで、3 人の生徒がもらった金平糖の個数が等しくなるようにしたいと…

AOJ 1163 カードゲーム (ICPC 国内予選 2009 E) (400 点)

典型的な二部マッチングの問題です。 問題へのリンク 問題概要 枚の赤いカードと、 枚の青いカードとの間でマッチングを作っていきます。 各カードには整数値が書かれていて、最大公約数が 1 より大きいカード同士をペアにすることができます。 最大マッチン…

AOJ 2594 Reverse a Road II (JAG 模擬地区 2014 F) (600 点)

ネットワークフローアルゴリズムの構造をちゃんと理解しているかを問う良問ですね!! 問題へのリンク editorials 問題概要 頂点数 、辺数 の有向グラフ と、2 頂点 が与えられます。 いま、グラフの辺を 1 本選んで向きを反転させます。それによって、- 間…

AOJ 2872 最短距離を伸ばすえびちゃん (RUPC 2018 day3-F)

「最短路に含まれる可能性のある辺を列挙する」という考え方と、最小カットを組み合わせます。教育的な良問といえますね。 問題へのリンク editorial なお、この問題の設定を少し変えると非常に難しい問題が得られることも知られています (難しい問題: AOJ 2…

AOJ 2536 Median Tree (JAG 模擬地区 2012 C) (400 点)

グラフの最小全域木の構造に関する理解を問う良問ですね。 問題へのリンク (AOJ) 問題へのリンク 2 (AtCoder) editorials 問題概要 連結な重み付き無向グラフ が与えられます (頂点数 、辺数 )。 の全域木のうち、全域木に含まれる 本の辺の重みのメディアン…

JOI 本選 2007 E - 最軽量のモビール (AOJ 0520, 難易度 7)

読解が大変だけど、本質的には木 DP な問題 ジャッジへのリンク AOJ ページ 問題概要 本の棒を用いて、下図のようなモビールを作りたい。 入力としては、各棒 についての 左端から支点までの長さ 右端から支点までの長さ 左端からつながっている棒の index (…

JOI 本選 2007 D - 最悪の記者 (AOJ 0519, 難易度 7)

トポロジカルソートせよ、という問題! 問題へのリンク 問題概要 頂点数 、辺数 の DAG (閉路のない単純有向グラフ) が与えられる。 このグラフのトポロジカルソート順を一つ求めよ。また、トポロジカルソート順が唯一かどうかを判定せよ。 制約 考えたこと …

JOI 二次予選 2021 E - スパイ 2 (難易度 10)

面白かった。 問題へのリンク 問題概要 人がいて、それぞれ「スパイ」か「非スパイ」かのどちらかである。 人のうち、何人かについてはスパイかどうかが予めわかっている ( で与えられる)。 個の証言がある。各証言は人 が証言者によってなされ、「人 はスパ…

JOI 二次予選 2021 D - 安全点検 (AOJ 0694, 難易度 7)

難易度 8 でもおかしくないと思った。 B や C より易しい気がしなくもないけど、本番の緊張感で B や C を飛ばして D を本気で考える決断はなかなかできなさそう。今回は B - パンケーキを見て冷静になれたか勝負だね... 問題へのリンク 問題概要 個の工場が…

JOI 本選 2014 D - フクロモモンガ (AOJ 0601, 難易度 8)

dp の値そのものを用いて現在状態を復元する系の問題。 問題へのリンク editorial 問題概要 個の木 があって、それぞれ高さは である。 フクロモモンガは最初は、木 1 の高さ の地点にいる。フクロモモンガは木を飛び移りながさ、最終的に木 の頂上にたどり…

JOI 二次予選 2021 C - イベント巡り (AOJ 0693, 難易度 8)

これはアレだ!!! DP の最適値そのものの値を利用して次の遷移を作る系。フクロモモンガなんかもそういう系の問題だった覚えがある。 問題へのリンク 問題概要 2 つの町 (1 と 2) がある。 個のイベントがあって、それぞれ町 において発生し、時刻 に始ま…

JOI 二次予選 2021 B - パンケーキ (AOJ 0692, 難易度 7)

難しかった!!! 予選の問 2 からこういうの出るのびっくり!!! 問題へのリンク 問題概要 "A", "B", "C" からなる文字列 に対して、以下の操作を繰り返すことでソートされた状態 ("A" の前には "B" や "C" がなく、"B" の前には "C" がない状態) にするこ…

JOI 二次予選 2021 A - 往復すごろく (AOJ 0691, 難易度 5)

結構アドホックで難しいと思った! 問題へのリンク 問題概要 マスが横一列に並んだすごろくが与えられる ( と番号づけされている)。すごろくの各マスは . と x と # のいずれかである。 マス とマス は X である 他のマスは長さ の文字列 で与えられる X は…

JOI 本選 2011 B - 古本屋 (AOJ 0561, 難易度 6)

こういうのは DP! ジャッジページ AOJ の問題文 問題概要 冊の古本があって、 番目の本のベース価格は 円である。またこれらの本は 10 種類のジャンルに分かれており、 番目の本のジャンルは で与えられる。 これらの本から 冊を古本屋で売りたい。ただし同…

JOI 本選 2010 C - つらら (AOJ 0551, 難易度 6)

実装をどうしようかを色々悩んでしまう系 ジャッジページ AOJ の問題文 問題概要 本のつららが一列に並んでいる。それぞれ長さは となっている。各つららは以下のルールに従って長さが変わる。 一度でも長さが 0 になったならば、伸びることはない 左右のつ…

JOI 予選 2010 E - 通勤経路 (AOJ 0547, 難易度 6)

JOI 難易度 6 の中では難しい方だと思った! 問題へのリンク editorial 問題概要 のグリッドの左下マス から右上マス へと至る最短経路 (上または右にのみ移動可能) のうち、以下の条件を満たすものの個数を 100000 で割ったあまりを求めよ。 曲がってから、…

JOI 本選 2007 A - 最大の和 (AOJ 0516, 難易度 4)

累積和を使う代表的な問題ですね。 ジャッジへのリンク 問題文へのリンク 問題概要 個の整数からなる数列 と、整数 が与えられる。 数列から連続する 個の値を選んで総和をとる。この総和として考えられる最大値を求めよ。 制約 前提知識 まず、愚直な解法で…

JOI 本選 2009 B - ピザ (AOJ 0539, 難易度 6)

ひょっとしたら難易度 5 との境界の問題だったかもしれない。lower_bound() を試すいい感じの例題。 ジャッジページへのリンク 問題文 editorial 問題概要 一周の長さが であるような周回コースがあって、コース上に 個の店舗がある。コース上の 1 点の座標…

AOJ 2880 エレベータ (RUPC 2018 day1-G)

昔はこういうの苦手だったけど、今ならできる! 問題へのリンク 問題概要 階建ての建物があって、後述するエレベータの建設をなくしては、下への移動は自由にできるが、上への移動は自由にできない。 個のエレベータ建設計画がある。 番目の計画では、 日目…

AOJ 2877 水槽 (RUPC 2018 day1-D)

とてもよくある区間分割していくタイプの DP 問題へのリンク 問題概要 個の正の整数 がこの順に一列に並んでいる。これらの整数を 個以下の区間に分割したい。 このとき、「各区間の値の平均値の総和」として考えられる最小値を求めよ。 制約 考えたこと 「…

AOJ 1208 Rational Irrationals (ICPC アジア 1999 A)

Stern-Brocot 木がちょうどよく使える 問題へのリンク 問題概要 正の整数 が与えられる。分子・分母がともに 以下の正の整数であって、既約分数であるような分数の集合を と表すことにする。 を満たす最大の の要素 を満たす最小の の要素 をそれぞれ求めよ…

JOI 予選 2009 C - 連鎖 (AOJ 0534, 難易度 6)

いろんな実装方法がありそう。でも が間に合うので、すべての書き換え方法について でできるなら十分。 問題へのリンク 問題概要 1 と 2 と 3 のみからなる長さ の数列が与えられる。同じ数値が 4 個以上連続することはない。 この数列のうちの 1 箇所の値を…

AOJ 3217 Cafe au lait (OUPC 2020 I)

数学っぽい問題好き!!! 問題へのリンク editorials 問題概要 個のカフェオレがある。 番目のカフェオレは、コーヒーが mg、ミルクが mg だけ入っている (ともに整数)。 これらを混ぜて作れるカフェオレのうち、コーヒー量 とミルク量が がともに正の整数…

AOJ 3213 Xor Mart (OUPC 2020 E)

半分全列挙 + Binary Trie!! あるいは、Binary Trie 自体を意識しなくても、上の位から順に桁 DP 的発想で考えていると、それが自然に Binary Trie 上の探索そのものとみなせる! すごくいい Binary Trie の経験になった!! 問題へのリンク editorial 問…