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

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

操作を逆順に見る

エクサウィザーズ 2019 C - Snuke the Wizard (500 点)

頭の整理が大変!!! 問題へのリンク 問題概要 左から右に向かって 1 から N の番号がついた N 個のマスがあります。 各マスには文字が書かれており、マス i には文字 si が書かれています。また、各マスにははじめ 1 体のゴーレムがいます。 すぬけ君は Q …

AtCoder AGC 032 A - Limited Insertion (400 点)

好き!!!!!でも A 問題としてはかなり難しいね。 問題へのリンク 問題概要 数列 が空の状態から出発して以下の操作を 回行った結果が数列 と一致するようにできるかどうか判定せよ。 回目の操作においては 以上 以下の整数 を一つ選んで、数列の 番目に …

AOJ 3059 Shuffle 2 (RUPC 2019 day2-I)

与えられた操作を「わかりやすいものに読み替える」というのが本質な問題だと思う。AtCoder でもよく見られるタイプの 問題へのリンク 問題概要 の書かれた 枚のカードを順に並べたものに対し 左から偶数番目のみを順に取り出して並べたものを A 右から偶数…

AtCoder ABC 120 D - Decayed Bridges (400 点)

これまたすごく教育的な問題!!!!!!!!! UnionFind 木の基本的な使い方 (連結成分のサイズ獲得含む) クエリを先読みしておいて逆順に処理 (多くのクエリ先読み問題ではもっと変な順番で処理したりする) 差分のみ更新する考え方 といったあたりを学ぶ…

AtCoder AGC 008 B - Contiguous Repainting (400 点)

操作を逆順に見るとよいという、すごく良い例題!大好き!!! 問題へのリンク 問題概要 要素からなる数列 が与えられる。今、以下の操作を好きな回数だけ行う。 長さが の区間を選んで、区間全体を白く塗るか、黒く塗る 操作を行った後に黒く塗られたマスの…

全国統一プログラミング王決定戦 本選 D - Deforestation (500 点)

遅延評価セグメントツリーで殴った...速度重視ならそれでいい気もする 問題へのリンク 問題概要 本の竹があって、時刻 0 においてすべての竹の高さは 0 である。それぞれの竹は時刻が 1 経過するごとに高さが 1 増える。 竹を伐採するイベントが 回予定され…

AOJ 1391 Emergency Evacuation (ICPC アジア 2018 C)

結構好き!ソートすることが本質の問題としていい感じな気がする。 問題へのリンク 問題概要 下図のような「中央の通路とそこから横に伸びた乗り物に乗客がどこにいるかを表した地図」が与えられる。乗客は 人いる。各乗客は 1 秒かけて 1 マス移動できる。…

Codeforces Manthan Codefest 18 E - Trips (R2100)

こういうの苦手。。。 問題へのリンク 問題概要 整数 k と、N 頂点 0 辺のグラフが最初に与えられる。以下の M 個のクエリに答えよ。 a, b: 辺 (a, b) を追加する。この時点でグラフの各頂点を以下の条件を満たすように白黒に塗る「任意の黒い頂点は、隣接す…

AtCoder ARC 098 F - Donation (1000 点)

本番中に解きたかった... ARC 098 F Donation 問題概要 N 頂点 M 辺の連結な単純無向グラフがあります。 頂点 i には二つの整数 Ai, Bi が定められています。 このグラフ上で次のようなゲームをします。 初めに、W 円を持った状態で好きな頂点に立つ。 ただ…