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

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

ARC-E

AtCoder ARC 074 E - RGB Sequence (800 点)

わかってる...!わかってるんだ!!!この問題が超ド典型だってことくらい!!!!!!!! でも典型だからって、そんなパッと解けるわけじゃない。すごく苦手なんだこういうの。。。 問題へのリンク 問題概要 マスを RGB の三色で塗り分ける 通りの方法のう…

AtCoder ARC 065 E - へんなコンパス / Manhattan Compass (900 点)

めるアイコン変換すると良さそうなのはすぐに思い至った。そこから繋げられずに editorial を見た。 問題へのリンク 問題概要 二次元平面上に 個の点がある。このうちの 2 点 が指定されている。その 2 点間のマンハッタン距離を とする。 この 点について「…

AtCoder ARC 094 E - Tozan and Gezan (700 点)

ある量を、一方は最大化したくて、他方は最小化したいというゲーム。これは ゲーム DP で解けるなら楽 ゲーム DP で解けるほど探索領域が小さくないなら、ある値 が存在して、以下を示す 先手は少なくとも 以上を達成できること 後手は少なくとも 以下を達成…

AtCoder ARC 101 E - Ribbons on Tree (900 点)

すごく典型的な「二乗の木 DP」!!!!! そして包除原理との組み合わせ。 問題へのリンク 問題概要 を偶数とする。 頂点の木が与えられる。 頂点を 組の 2 つペアにする方法のうち、各ペアを結ぶパスをすべて考えたときに全辺が被覆されるようなものの個数…

AtCoder ARC 062 E - AtCoDeerくんと立方体づくり / Building Cubes with AtCoDeer (900 点)

大変だった ^^; 問題へのリンク 問題概要 全部で 色の色がある。 下図のような 枚の正方形があって、それぞれ のラベルがついていて、各正方形の四隅にはいずれかの色が塗られている。 枚の中から 6 枚を選んで正方形を作る。ただしどの頂点についても、そこ…

diverta 2019 E - XOR Partitioning (800 点)

時間かかりすぎた。シンプルで面白い。 問題へのリンク 問題概要 要素からなる 0 以上の整数列 が与えられる。 これをいくつかの連続した部分列に分割する 通りの方法のうち、各連続区間の XOR 和が互いに等しくなるものが何通りあるか、1000000007 で割った…

Tenka1 2019 D - Three Colors (600 点)

見た目とても面白そう 問題へのリンク 問題概要 要素からなる数列 があたえられる。各要素を「赤」「緑」「青」の三色のいずれかに塗る方法のうち、各色の合計値を として三辺の長さが となるような三角形が存在するようなものを数え上げよ。998244353 で割…

Tenka1 2019 E - Polynomial Divisors (800 点)

最大公約数を求めるときに abs つけてれば通ってた。。。 なにこれ悔しすぎる。。。 問題へのリンク 問題概要 次の整数係数多項式 が与えられる。任意の整数 に対して が で割り切れるような素数 をすべて求めよ。 制約 考えたこと めっちゃ好き!!!!!!…

AtCoder ARC 096 E - Everything on It (900 点)

部分点がなければ CE 2 完でも赤パフォ出たのに... それはともかく、この手の包除で絶対に解けるという安定感をもって解けるようになりたい! 問題へのリンク 問題概要 ラーメンに 種類のトッピングを自由に組み合わせて乗せることができます。トッピングの…

AtCoder ARC 068 E - Snuke Line (700 点)

こういうのを得意になるぞー!!! でも AtCoder でこういうデータ構造をしっかり準備する必要がある系は珍しい気がする。 問題へのリンク 問題概要 個のマス () があって、マス上に 個の区間がある。 各 に対して、 と移動したときに何個の区間を踏むかを答…

AtCoder ARC 064 E - Cosmic Rays (600 点)

昔の AtCoder はこういうのもあったのか!!! 問題へのリンク 問題概要 二次元平面上に、 個の円がある。二次元平面上の点 から点 へと進むことを考える。秒速 1 だけ進む。 そのような方法のうち、円外の領域を進んでいる時間の最小値を求めよ。 制約 考え…

AtCoder ARC 103 E - Tr/ee (700 点)

取り急ぎ... 問題へのリンク 問題概要 N 頂点からなるツリーがあって、各辺で切ってできる連結成分のサイズとしてありうるものすべて集めたものが指定される。そのようなツリーを 1 つ構築せよ。存在しない場合は -1 とせよ 解法 とりあえず、 サイズ 1 は絶…

AtCoder ARC 081 E - Don't Be a Subsequence (600 点)

部分列 DP の考え方を試せる問題 問題へのリンク 問題概要 (ARC 081 E) 文字列 A が与えられる。 A の部分文字列とはならないような文字列 (英小文字のみ) のうち、最短の長さのものを求めよ。 複数考えられる場合にはそのうち辞書順最小のものを求めよ。 制…

AtCoder ARC 091 E - LISDL (700 点)

問題へのリンク 問題概要 1, 2, ..., N を並べ替えてできる列であって、以下の条件を満たすものがあるかどうか判定し、あればその例をひとつ構成せよ: 最長増加部分列の長さは A 最長減少部分列の長さは B 制約 1 <= N, A, B <= 3 × 105 解法 LIS and LDS と…

AtCoder ARC 102 E - Stop. Otherwise... (700 点)

いろんな解法がありそうなんな 問題へのリンク 問題概要 (ARC 102 E) 整数 が与えられる。各 に対して、 どの に対しても を満たす整数組 の個数を で割った余りを求めよ ( 面サイコロを 個振るという設定)。 制約 解法 1: 漸化式を立ててそれを展開 (本番で…

AtCoder ARC 100 E - Or Plus Max (700 点)

高速ゼータ変換の練習第二弾なん! 問題へのリンク 問題概要 長さ の整数列 があります。 を満たすすべての整数 について、以下の問題を解け: を < , を満たす整数とするとき、 の最大値を求めよ。 制約 考えたこと 個の要素を一斉に変換する何かをさせてい…

AtCoder ARC 099 E - Independence (700 点)

いわゆる本当に典型らしい典型ではあるけれども、「二部グラフ判定」と「ナップサック DP」とパートが 2 つあって重たいのん。こういうのを素早く通せるようになりたいん。 類題として AOJ 2370 RabbitWalking (二部グラフ判定からの部分和ナップサックが酷…

AtCoder ARC 067 E - Grouping (600 点)

slack 勉強会で 600 点の DP として話題になってやってみたん。 DP 自体は素朴だけど、計算量解析含めると 700 点でもいい気はするのんな。 Grouping 問題へのリンク 問題概要 (ARC 067 E) 人をグループ分けしたい。 人は互いに区別される。 どのグループの…

AtCoder ARC 097 E - Sorted and Sorted (600 点)

600 にしちゃムズイような。。。なん。。。 ARC 097 E Sorted and Sorted 問題概要 (白, 1), (白, 2), ..., (白, N), (黒, 1), (黒, 2), ..., (黒, N) の 2N 個の要素の順列が与えられる。「隣同士を swap する」を最小回数行うことで、「白」についても「黒…

AtCoder ARC 098 E - Range Minimum Queries (600 点)

ARC 098 E Range Minimum Queries 問題概要 長さ N の数列 A と整数 K が与えられる。 この配列に、以下の操作を Q 回行います。 長さ K の連続する部分列を 1 つ選ぶ。 そして、選んだ部分列に含まれる K 個の要素のうち最小のもの(複数ある場合はその中で…