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

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

解空間:O(N!)通りの選択肢

AtCoder ARC 171 B - Chmax (水色, 600 点)

順列をどうのこうのする系、最近多いかもしれない。 問題へのリンク 問題文 考えたこと 操作の内容を解釈するのに少し苦労した。 順列 から誘導される Functional Graph を考えた。このグラフ上で、頂点 から出発して頂点番号が大きくなる限り進んでいったと…

AtCoder ABC 321 G - Electric Circuit (橙色, 600 点)

除原理! 学びの多い問題だった。Subset Convolution の方はちょっと頑張ってこの後復習する。 問題へのリンク 問題概要 頂点番号が であるグラフ がある。最初、辺は 1 本もない。 以上 以下の値からなるサイズ の 2 つの数列 と がある。 今、これら 2 つ…

Codeforces Global Round 15 C. Maximize the Intersections (R1800)

企業合コンで解いた。ギャグ系だった。 問題へのリンク 問題概要 円周上に 個の点があって、2 個ずつ 組のペアを作って線分で結ぶ。 すでに 組のペアができていて、線分が結ばれている。残りの点についてペアを作って線分を作っていったときの交差数の個数の…

AOJ 2373 HullMarathon (JAG 冬合宿 2010 day3-E) (700 点)

面白い最適化問題! 問題へのリンク 問題概要 二次元平面上で、原点からの距離が であるような 点の凸包の面積として考えられる最大値を求めよ。 制約 考えたこと 凸包というところが面倒だが、要は 本のうちの何本かを選んで それを適切な順序に並び替えた…

AtCoder ABC 318 Ex - Count Strong Test Cases (橙色, 650 点)

コンテスト終了から 8 秒後の AC で泣いた。でも、分割統治 FFT が自力で書けてよかった。想定解法は FPS だった。 問題へのリンク 問題概要 次の問題がある。 の順列 と が与えられる。 これらをもとに次のように、頂点数 、辺数 の有向グラフを作る。 頂点…

AtCoder ABC 317 G - Rearranging (橙色, 600 点)

面白かった 問題へのリンク 問題概要 のグリッドがある。各マスには数値が書かれている。 個の数値を集めると、 が 個ずつある。 今、各行について、その 個の数値を自由に並び替えていく。 その結果として、すべての列が の順列であるようにすることが可能…

AtCoder ABC 256 E - Takahashi's Anguish (水色, 500 点)

最近話題の Functional Graph の問題! 問題へのリンク 問題概要 人 がいる。各人 には 1 人ずつ嫌いな人 がいる。 今、彼らに順番にキャンディーを配る。ただし、各 について、もし人 よりも先に にキャンディーを配ると、不満度が だけ加算される。 キャン…

AtCoder ABC 025 C - 双子と○×ゲーム (試験管青色)

ゲーム探索 + bit DP。やや実装重たい。 問題へのリンク 問題概要 先手と後手が交互に のグリッドの各マス目に o や x を書いていく。先手は o を書き、後手は x を書く。 書き終わったとき、次のように得点を計算する および に対して、 マス とマス が同じ…

AtCoder Library Practice Contest E - MinCostFlow (3D)

D 問題の MaxFlow に続いて、これまた、人生で一度は解くべき超典型問題ですね。そして、D 問題とは違うやり方で、二部グラフを作ることにも注目です! 問題へのリンク 問題概要 のグリッドがあり、各マスには数値が書かれています。 これらのマスからいくつ…

AOJ 2567 SIRO Challenge (JAG 模擬地区 2013 C) (400 点)

「ABC 301 E - Pac-Takahashi」の類題とも言うべき ICPC 系の問題! 問題へのリンク (AOJ) 問題へのリンク (AtCoder) editorials 問題概要 頂点数 、辺数 の重み付き無向グラフが与えられる。頂点番号は とする。 番目の辺は頂点 を結んでおり、その重みは …

AtCoder ABC 301 E - Pac-Takahashi (青色, 475 点)

前処理して頂点数を減らしたグラフ上で TSP!!! ICPC ではすごくよく見るパターンですね! 問題へのリンク 問題概要 サイズのグリッドがある。各マスは 壁マス:'#' 通路マス:'.' お菓子マス:'o' (18 個以内であることが保証される) スタートマス:'S' …

AtCoder ABC 009 C - 辞書式順序ふたたび (試験管青色)

旧 ABC の C 問題の中でも、個人的に最難だと思う問題! 現代の ABC で出題されても水色 diff になると思う。 問題へのリンク 問題概要 英小文字のみからなる長さ の文字列 が与えられる。 の各文字を並べ替えてできる文字列 のうち、 となる が 個以下であ…

AtCoder ABC 282 E - Choose Two and Eat One (青色, 500 点)

これをグラフの問題だと思えるかどうか! 問題へのリンク 問題概要 箱の中に 個のボールが入っており、各ボールには 以上 以下の整数が書かれている。 番目のボールに書かれた整数は ​ である。 箱の中に 2 個以上のボールが残っている限り、下記の行動を繰…

AtCoder ARC 050 D - Suffix Concat (試験管橙色)

めっちゃ面白い問題だった! Suffix Array の練習問題。 問題へのリンク 問題概要 英小文字からなる長さ の文字列 が与えられる。 の suffix は空文字列を除いて 個ある。これらの suffix を適切な順序で連結させて 1 つの文字列を作るとき、それが辞書順最…

Educational Codeforces Round 9 C. The Smallest String Concatenation (R1700)

すごくシンプルな面白い問題。 問題へのリンク 問題概要 個の文字列 が与えられる。 これらを並び替えて連結して 1 つの文字列を作る。作れる文字列のうち、辞書順最小のものを求めよ。 制約 解法 単純に を辞書順にソートして、小さい順に連結するのでは反…

AOJ 2297 Rectangular Stamps (JAG 夏合宿 2011 day2-H) (450 点)

状態空間を上手に削減する系の問題 問題へのリンク editorial 問題概要 種類の長方形形状 () をしたスタンプがある (それぞれ「赤」「緑」「青」の 3 種類がある)。 これらを使って 4 × 4 のグリッド上に所望の模様を作りたい。グリッドからはみ出して押して…

AOJ 2681 Parentheses (JAG 春コン 2014 E) (500 点)

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

AtCoder ABC 180 E - Traveling Salesman among Aerial Cities (水色, 500 点)

TSP だ!! 問題へのリンク 問題概要 3 次元空間内に 個の都市、都市 1 から 都市 N がある。 座標 の都市から の都市に移動する際には のコストがかかる。 都市 1 からスタートし、全ての都市を 1 度以上巡って都市 1 に戻るまでの最小コストを求めよ。 制…

AOJ 3191 Watering (AUPC 2020 day3-G)

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

diverta 2019 F - Edge Ordering (銅色, 1200 点)

こういうの素早く解けるようになりたいね。 いわゆる「トポロジカルソート順の数え上げ」という高難易度でたまに見るパターンの問題。 問題へのリンク 問題概要 頂点 辺の無向グラフが与えられる。ここで、辺 が全域木を形成していることが保証されている。 …

diverta 2019 C - AB Substrings (緑色, 400 点)

ペアリングを場合分けしてルールベースで頑張る系の問題、過去に何度もやらかしていて苦手意識が強い 問題へのリンク 問題概要 個の文字列 が与えられる。 これらを任意の順序で連結してできる 通りの文字列のうち、その中に "AB" を連続部分列として含んで…

CS Academy 081 DIV2 E - Fold Polygon

の Kruskal 法ではダメで、 な Prim 法なら OK という稀有なパターンの問題。Dijkstra 法でも priority_queue を使ったやつは 愚直なやつは と二種類の実装があって前者の方が速いと言及されるケースも多いけど、密グラフ ( なグラフ) では後者の方が速い。P…

AtCoder AGC 025 C - Interval Game (黄色, 700 点)

コンテスト本番における 僕のコード: https://beta.atcoder.jp/contests/agc025/submissions/2612210 tourist のコード: https://beta.atcoder.jp/contests/agc025/submissions/2609185 解けたとはいえ、反省点も多い感じですね。。。 問題へのリンク 問題概…