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

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

ABC/ARC-D

AtCoder ABC 120 D - Decayed Bridges (400 点)

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

AtCoder ABC 119 D - Lazy Faith (400 点)

二分探索で lower_bound とかきっちり無意識的に使いこなせるようになりたいのんな!!! 問題へのリンク 問題概要 一次元の世界を考える。 A 個の神社と、B 個の寺が並んでいる (各神社と各寺の位置情報が 1 つの整数値で与えられる)。 以下の Q 個のクエリ…

AtCoder ABC 073 D - joisino's travel (400 点)

Floyd-Warshall で前処理してどうのこうのする問題。特に ICPC 系などでよくある! 問題へのリンク 問題概要 頂点 辺の重み付き無向グラフが与えられる。このグラフ上で 個のチェックポイントをなす頂点集合が指定されている。好きなチェックポイントからス…

AtCoder ABC 070 D - Transit Tree Path (400 点)

一見、ツリー上のパスクエリ (オイラーツアーとかするやつ) な問題に見えるけど、そんなことはなかった 問題へのリンク 問題概要 頂点のツリー (辺に重み付き) が与えられる。ツリー上の 1 点 が与えられて、以下のクエリに 個答えよ: クエリ (): から を経…

AtCoder ABC 118 D - Match Matching (400 点)

文字列を値にもつ DP、ご無沙汰!!! 問題へのリンク 問題概要 本のマッチ棒を使ってできるだけ大きな数値を作りたい。 マッチ棒で 1, 2, 3, 4, 5, 6, 7, 8, 9 を作るのにそれぞれ 2, 5, 5, 4, 5, 6, 3, 7, 6 本のマッチ棒が必要である。 ただし各桁に用い…

AtCoder ABC 064 D - Insertion (400 点)

教育的典型題 問題へのリンク 問題概要 カッコ列が与えられる。カッコ列に最小個数の '(' と ')' を挿入して「整合のとれたカッコ列」にせよ。またそのようなものが複数通り考えられる場合には、辞書順最小のものを求めよ。 制約 考えたこと 超定番。 AtCode…

AtCoder ABC 061 D - Score Attack (400 点)

ちょっと注意が必要な Bellman-Ford 法の典型題。昔の AtCoder はこういうのもあったのか... 問題へのリンク 問題概要 頂点 辺の重み付き有向グラフが与えられる。頂点 1 から頂点 N への最長路の長さを求めよ。無限に大きくできる場合は "inf" と出力せよ。…

AtCoder ABC 057 D - Maximum Average Sets (400 点)

これは単に二項係数知っているかを問う感じ...? この頃と今とでは、多少問題傾向も違う気がする。 問題へのリンク 問題概要 個の数値が与えられる。このうち 個以上 個以下を選ぶときのその平均値の最大値を求めよ。 また最大を達成する選び方が何通りある…

AtCoder ABC 054 D - Mixing Experiment (400 点)

なんだろ 問題へのリンク 問題概要 個の薬品があって、それぞれ成分 A, B を グラムずつ含んでいる (すべて整数値)。 これらのうちのいくつかを選んで混ぜ合わせることで、成分 A, B の比がちょうど : となるようにしたい。 そのようなことが可能となる薬品…

AtCoder ABC 051 D - Candidates of No Shortest Paths (400 点) 〜 3 通りの解法 〜

「最短路として選ばれる可能性がないところを挙げる」というのは、それ自体、高難易度問題で部分的に必要になる考察だったりするね。 問題へのリンク より高難易度な問題の部分問題となる例として、 RUPC 2018 day3-F 最短距離を伸ばすえびちゃん がある。こ…

AtCoder ARC 076 D - Built? (500 点)

ゆかたゆたんと一緒に解いたん。 今後まだ解いてない様々な 500 点問題について何がポイントになっているのかをブログ書きながら明らかにして行きたい。500 点問題の苦手意識を克服するぞい。 問題へのリンク 問題概要 二次元平面上に 個の点が与えられる。…

AtCoder ABC 117 D - XXOR (400 点)

以下の典型思考で解けるけど、苦手意識...^^; XOR な問題は各桁ごとに見る の動ける範囲が 以下と指示されているときは、 を上位ビットから見ていったときに、それがどこまで と一致するかを考える (桁 DP でおなじみの考え方) 問題へのリンク 問題概要 個の…

AtCoder ARC 064 D - An Ordinary Game (500 点)

気づき系。。。 こういうのを一瞬で思いつける人になりたい。 問題へのリンク 問題概要 長さ の文字列 が与えられる。先手と後手とで交互に 文字列中の文字を一文字選んで消していく、ただし 両端は消せない その文字を消すことで「同じ文字が隣り合っている…

AtCoder ABC 112 D - Partition (400 点)

すごく教育的ないい問題な感じ 問題へのリンク 問題概要 整数 , が与えられる。 を満たす正の整数列 をすべて考えたときの、 の最大公約数の最大値を求めよ。 制約 考えたこと 候補を一気に絞る まず の最大公約数が必ず の約数になることがわかる。まずはこ…

AtCoder ARC 103 D - Robot Arms (600 点)

くやしい 問題へのリンク 問題概要 個の座標 () が与えられる。 今、40 本以下の正の整数 を用意して、それぞれについて (), (), (), () をうまく選択して加算することで、() をすべて作れ。できないときは -1 とせよ。 各 について共通の を用いなければな…

AtCoder ABC 110 D - Factorization (400 点)

素因数分解 & 重複組合せ を勉強できる、すごく教育的問題だった!!! 問題へのリンク 問題概要 (ABC 110 D) 整数 が与えられる。 を満たす整数の組 () が何通りあるか、1000000007 で割った余りで求めよ。 制約 解法 素因数分解っぽいテーマの問題。こうい…

AtCoder ABC 109 D - Make Them Even (400 点)

最初は「一度選んだマスを使えない」を完全に呼び飛ばしてしまった上に、それに気づいた後も「奇数マス同士をマッチングして、うまく経路を設定する」という方向の考察をしまくって、上手くいかずに迷走した... 問題へのリンク 問題概要 (ABC 109 D) 縦 行、…

AtCoder ARC 092 D - Two Sequences (500 点)

桁ごとに考えるしかなさそうなのはそれはそう... 問題へのリンク 問題概要 (ARC 092 D / ABC 090 D) 要素の数列 と が与えられる。 個の整数 の XOR 和を求めよ。 制約 < 解法 XOR 和と言われた時点で、各桁ごとにカウントしたい気持ちにはなる。 個の整数の…

AtCoder ARC 094 D - Worst Case (700 点)

最適性を失わずに解を変形していくことで、都合のいい解の形だけ考えればいいようにする系の問題。 問題へのリンク 問題概要 (ARC 094 D / ABC 093 D) 人の参加者が 2 回のプログラミングコンテストに参加しました。順位がつくのですが、同順位はないものと…

AtCoder ARC 101 D - Median of Medians (700 点)

今更前々回の ARC を見て、噂の 700-D Median of Medians を見てみたけど、これはJOI 2017 予選 F - L番目のK番目の数https://t.co/EEfPlJ18Tkとほぼ同じ問題な気がしたん。— けんちょん (@drken1215) 2018年9月6日 とは言え、完全に一緒ではなくて後半の議…

AtCoder ABC 106 D - AtCoder Express 2 (400 点)

いろんな方法が考えられそう。 せっかくなので、敢えて、N が大きくても OK な方法でやってみる。hama_du さんの記事を参照。 問題概要 (ABC 106 D) M 個の区間 [l_i, r_i] が与えられる。以下の Q 個のクエリに答えよ: 区間 [p, q] に完全に含まれる区間が…

AtCoder ARC 102 D - All Your Paths are Different Lengths (700 点)

好きだけど細かいところで時間とられるやつなん 問題へのリンク 問題概要 (ARC 102 D / ABC 108 D) 整数 L が与えられる。N 頂点 M 辺の重み付き有向グラフ (頂点番号は 1, 2, ..., N) であって N <= 20 M <= 60 任意の辺 (u, v) について u < v でなければ…

AtCoder ARC 100 D - Equal Cut (600 点)

かなり悩んだ 問題へのリンク 問題概要 (ARC 100 D / ABC 102 D) 長さ の整数列 を 3 箇所で切って、4 つの連続する数列に切り分ける。このとき、4 つの区間の値の和を とするとき、 の最小値を求めよ。 制約 考えたこと こういうの、 連続する区間が 4 個だ…

AtCoder ABC 105 D - Candy Distribution (400 点)

AGC 023 A - Zero-Sum Ranges とほぼ同じ問題なんな。ただし、バケットを愚直に確保すると 109 サイズになってしまうので map とか連想配列が必要になるのん。 問題へのリンク 問題概要 (ABC 105 D) 個の整数 の連続する部分区間のうち、その総和が の倍数と…

AtCoder ABC 104 D - We Love ABC (400 点)

これ好きなん!!! 400 点問題が問題分読んで 5 秒以内に方針立ったのは珍しいので、成長かもなん。 そして、DEGwer さんや chokudai さんが「DP は割とコーディングしながら細部詰めてる」と言っていたので、それを実践してみて、確かに良さそうかもなん。…

AtCoder ABC 099 D - Good Grid (400 点)

「前処理」を学べる問題なんな。 問題へのリンク 問題概要 (ABC 099 D) 色が全部で 色ある。 × の盤面がそれぞれ 色のいずれかに塗られている。今この盤面の色を塗り替えて マス () について % 3 の値によって色を類別された状態 (その値が同じマスは同じ色…

AtCoder ABC 103 D - Islands War (400 点)

問題へのリンク 実は、こないだの RUPC 2018 で出てたん (最後の部分のみほぼ同じ) AOJ 2873 - 検閲により置換 見た目は区間スケジューリング問題とは違うけど、実は区間スケジューリング問題なのん (こういうの双対問題と言ったりするん)。双対性の知識がま…

AtCoder ABC 098 D - Xor Sum 2 (500 点)

こんなしゃくとり法もあるのんな。面白いん。 ABC 098 D Xor Sum 2 問題概要 長さ の正の整数列 が与えられる。整数列の連続する部分列のうち、「xor 和と加算和とが等しい」という条件を満たすものを数え上げよ。 制約 数値例 1) 答え: 5 (2), (2, 5), (5),…

AtCoder ARC 099 D - Snuke Numbers (500 点)

完全に冷静さを欠いたし、ハマったん。。。 ARC 099 D - Snuke Numbers 問題概要 (ARC 099 D / ABC 101 D) 正の整数 N に対してその 10 進法での桁の和を f(N) で表す。今、正の整数 N がすぬけ数であるとは、任意の N より大きい正の整数 M に対して f(N) /…

AtCoder ABC 100 D - Patisserie ABC (400 点)

ABC 100 D - Patisserie ABC 問題概要 整数 3 つ組 (xi, yi, zi) が N 個与えられる。 このうちの M 個選んで、 (x の選んだ M 個の総和の絶対値) + (y の選んだ M 個の総和の絶対値) + (z の選んだ M 個の総和の絶対値) が最大になるようにせよ。 制約 1 <=…