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

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

2020-09-01から1ヶ月間の記事一覧

AOJ 3169 Pyramid Graph (HUPC 2020 day1-F)

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

ACL Beginner Contest F - Heights and Pairs (橙色, 600 点)

こういうのは包除原理しかない! 問題へのリンク 問題概要 人の人がいる。 人 の身長は である。以下の条件を満たすように、 組のペアを作る方法は何通りあるか、998,244,353 で割ったあまりを求めよ。 どの人もちょうど一つのペアに含まれる。 どのペアも、…

ACL Beginner Contest E - Replace Digits (青色, 500 点)

まさに遅延評価セグメント木の練習問題!!! 問題へのリンク 問題概要 長さ の文字列 S がある。 最初は のすべての文字が 1 である。以下の 回のクエリに答えよ。 各クエリは整数 が与えられる () の 番目から 番目までをすべて に書き換える を数値とみな…

ACL Beginner Contest D - Flat Subsequence (水色, 400 点)

LIS を求める in-place DP を応用すればできる! でも、400 点問題で「DP 配列をセグ木に乗せて」「in-place に更新することで高速化する」という問題が出るとは思わなかった! in-place DP に馴染みのない方は先にこっちを qiita.com 問題へのリンク 問題概…

ACL Beginner Contest C - Connect Cities (茶色, 300 点)

Union-Find の練習問題という雰囲気ながら、DFS や BFS でも解ける 問題へのリンク 問題概要 頂点数 、辺数 の単純無向グラフが与えられる。これに最小本数の辺を追加することで全体が連結となるようにしたい。その最小本数を求めよ。 制約 考えたこと 全体…

ACL Contest 1 E - Shuffle Window (橙色, 900 点)

コンテスト中に まで導いておきながら、最後詰めきれなかったのは反省。 問題へのリンク 問題概要 の順列 と、2 以上の整数 が与えられる。 に対して順に以下の操作を行う。 をランダムシャッフルする 回の操作後に得られる順列の転倒数の期待値を、mod 9982…

ACL Contest 1 D - Keep Distances (橙色, 800 点)

これは天才!!! 問題へのリンク 問題概要 一直線上に 個の点が順に並んでいる (座標が )。 個のクエリが与えられる。 各クエリでは区間 () が与えられる 個の点のうち のみを取り出してできる 個の点について以下の問に答えよ 与えられた点集合から、どの …

ACL Contest 1 C - Moving Pieces (青色, 600 点)

フローって確かに天才パズルな問題はすごく天才的なんだけど、典型的な問題もたくさんある! 問題へのリンク 問題概要 下図のような の盤面が与えられる。盤面は通路 ('.') と壁 ('#') がある。いくつかの通路にはコマ ('o') が配置されている。 コマは下方…

ACL Contest 1 B - Sum is Multiple (青色, 600 点)

中国剰余定理使う問題楽しいよね! 問題へのリンク 問題概要 正の整数 が与えられる。以下の条件を満たす最小の正の整数 を求めよ。 が の倍数である 制約 考えたこと まず、 なので、問題の条件は次と同値になる。 が の倍数である ここで改めて を で置き…

ACL Contest 1 A - Reachable Towns (水色, 300 点)

えーーー、300 点!? 問題へのリンク 問題概要 二次元平面上に 点が与えられる。これらの点の x 座標、y 座標を抽出すると、それらは の順列となっている。 各 に対して、点 から 自分よりも x 座標と y 座標がともに大きな点 自分よりも x 座標と y 座標が…

AOJ 3191 Watering (AUPC 2020 day3-G)

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

AOJ 3190 Ribbons on A Perfect Binary Tree (AUPC 2020 day3-F)

こういうのは探索順序を適切に定めることがめっちゃ重要! 問題へのリンク 問題概要 高さ の完全二分木と、 長さが 2 のリボンが 本 長さが 4 のリボンが 本 ... 長さが のリボンが 本 が与えられる。各リボンは、完全二分木において「葉」と「葉」を始点と…

AOJ 3189 Mod Rush (HUPC 2020 day3-E)

これ好き!楽しい!! 問題へのリンク 問題概要 長さ の数列 で定義される、全 ステップの操作が与えられる。操作は整数 に対して行うものであり、 回目の操作は次のものである: を % で置き換える 個の整数 それぞれに対して ステップの操作を行って得られ…

AOJ 3188 Mod Rally (AUPC 2020 day3-D)

最初誤読して、「何度でもスタート地点にワープして戻っても良い」というバージョンの問題を解いていた。 問題へのリンク editorial 問題概要 個の整数 と 2 以上の整数 が与えられる。 頂点からなる以下のような有向グラフであって、頂点 1 を始点として、…

AOJ 3187 Mod Reap (AUPC 2020 day3-C)

DP の添字を mod をとった値にするテクニック 問題へのリンク 問題概要 個の正の整数 が与えられる。これらの中からいくつか選びたい。選んだ整数のスコアを以下で定める。 整数の総和を として + % スコアの最大値を求めよ。 制約 考えたこと そもそも「整…

AtCoder ABC 179 C - A x B + C (灰色, 300 点)

でもできる! 問題へのリンク 問題概要 正の整数 が与えられる。 を満たすような正の整数 の組の個数を求めよ。 制約 考えたこと こういう整数問題は、実のところ本当に整数論的考察を必要とするパターンは少なくて、大抵は探索ベースの解法が有効になる!!…

AtCoder ABC 179 E - Sequence Sum (緑色, 500 点)

この手の 周期性を利用する ダブリングする のどちらでも解けるタイプの問題、最近めっちゃ多いね。 問題へのリンク 問題概要 を で割ったあまりを で表す。 整数 が与えられる。以下で定まる漸化式の最初の 項の総和を求めよ。 制約 考えたこと 最初誤読し…

AtCoder ABC 179 D - Leaping Tak (水色, 400 点)

DP 高速化系問題。こういうのが緑 diff になるようになったんかーー (水色 diff にアップグレードした!) 問題へのリンク 問題概要 マスからなるマス目が与えられる。また、 個の互いに disjoint な区間 が与えられる。この区間に属する整数からなる集合を …

AtCoder ABC 179 F - Simplified Reversi (青色, 600 点)

早速遅延セグ木があればできる問題来た!! AC Library の出番かと思った!!! 問題へのリンク 問題概要 縦 マス、横 マスのグリッドがあり、はじめグリッドの中央 マスには黒い石が 1 個ずつ置いてあり、下辺と右辺の計 マスには白い石が 1 個ずつ置いてあ…

AOJ 3196 Increasing Sequence (AUPC 2020 day1-D)

in-place な DP にもっと慣れていきたい 問題へのリンク 問題概要 個の数列がある。 個目の数列は 個の要素からなる。 個目の数列の 番目の要素は と表す。 個目の数列から 1 個以下の要素を選び、選んだ要素を元の数列の順番通りに並べた数列を とする。 数…

AOJ 3182 Umg Kart (HUPC 2020 day3-K)

確かに、えでゅふぉのラス問にありそう! 問題へのリンク 問題概要 人の選手が距離 のレースを走る。 人目はデフォルトでは距離 1 走るのに 秒かかる。 スタートから距離が のところにアイテムがある。各アイテムは各選手に対して独立に、確率 で減速 (距離 …

AOJ 3184 Hokkaido High School (HUPC 2020 day3-M)

比較的簡単枠だとは思っていたけど、B よりも解かれたのはびっくり! 問題へのリンク 問題概要 北海道高校には 個の科目があり、それぞれ 1, 2, 3 の 3 段階で成績がつけられる。 各生徒の成績は長さ の文字列で表される 生徒 が生徒 の「上位互換」であると…

AOJ 3181 Proper Instructions (HUPC 2020 day3-J)

比較的素直な考察で解ける問題 問題へのリンク 問題概要 umgくんは 1 次元上の座標 0 にいます。今は時刻 0 です。時刻が 1 進むごとに、今いる座標より 1 大きい座標に移動するか、 1 小さい座標に移動するか、その座標にとどまるかという行動ができます。 …

AOJ 3176 Plane Graph (HUPC 2020 day3-E)

原案でした!僕は比較的アドホック寄りの問題を作る傾向があったかもだけど、これは典型な感じ。 問題へのリンク 問題概要 頂点数 、辺数 の連結な平面グラフが与えられます。ここで、各頂点の座標 も入力として与えられます。 どの 3 点も一直線上にはあり…

AOJ 3172 ?UPC (HUPC 2020 day3-A)

これはそんなにコーナーケースとかはなさそう 問題へのリンク 問題概要 個の文字列 が与えられます。各文字列に対して、 英大文字の部分だけを取り出して、この順に連結した文字列 を作り出し、それを 個連結します。そうして得られた文字列の末尾に "UPC" …

AOJ 3174 No Palindromes (HUPC 2020 day3-C)

これ楽しい! 問題へのリンク 問題概要 長さ の英小文字のみからなる文字列 が与えられます。 の文字を入れ替えることによって、次の条件を満たす文字列 を作ることができるかどうかを判定してください (可能ならば具体例を 1 つ挙げてください)。 のどの長…

AOJ 3180 GCDMST (HUPC 2020 day3-I)

中盤枠という感じで作られた 問題へのリンク 問題概要 の番号を振られた 個の頂点があります。 最初、これらを繋ぐ辺はありません。 あなたはいくつかの辺を追加してこのグラフを連結にしたいと思いました。 頂点 と を繋ぐ辺を追加するには のコストがかか…

AOJ 3183 Flipping a Path (HUPC 2020 day3-L)

こういう系すごく楽しいよね 問題へのリンク 問題概要 頂点数 、辺数 の重み付き有向単純グラフ が与えられる。 このグラフ上で次の条件を満たすパス (同じ頂点を二度通らないものに限る) が存在するかどうかを判定し、そのようなパスの重みの最小値を求めよ…

AOJ 3178 Katsusando (HUPC 2020 day3-G)

いわゆる区間分割する系の DP。こういう系は高速化を要求するタイプの問題が多いけど、今回は素直な二乗 DP で OK! 問題へのリンク 問題概要 直線上にカツが 個ある。 個目のカツは位置 にあり、その重さは である。これらのカツを、次のようにしてすべて回…

AOJ 3177 Painting (HUPC 2020 day3-F)

こういうの楽しいよね! 問題へのリンク 問題概要 個のマスが横一列に並んでいます。各マスは赤、青、黄、緑のいずれか 1 色で塗られている ("RBYG" からなる長さ の文字列 で与えられる)。 以下の操作を好きな順序で好きな回数だけ行えます。文字列 を作る…