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

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

補集合を考える

第一回日本最強プログラマー学生選手権-予選- F - Candy Retribution (1000 点)

てんぷらたんのこれを思い出した!!! yukicoder.me 問題へのリンク 問題概要 要素からなる非負整数 であって 要素を大きい順に並べたとき、 番目と 番目とが等しい という条件を満たすものの個数を で割ったあまりを求めよ。 制約 考えたこと まず、 以上 …

AtCoder ABC 141 C - Attack Survival (300 点)

ちょっと視点を変える感じ。 「反対側とか補集合とか余事象とか考えてみると解ける」という感じの問題は、300 点あたりからよく出てくる 問題へのリンク 問題概要 人がいてそれぞれ ポイントずつもっている。 これから ラウンドのクイズがあって、 ラウンド…

AtCoder ABC 131 E - Friendships (500 点)

順位表メタ読みスキルも大事かもしれない。「たくさん通しているのだから、きっと単純な方法があるに違いない」という感じの 問題へのリンク 問題概要 頂点の連結な無向グラフのうち、その間の最短経路長が 2 となっているような二頂点の組がちょうど 組であ…

AtCoder ABC 125 D - Flipping Signs (400 点)

操作をいい感じに言い換える感じ 問題へのリンク 問題概要 個の要素 が与えられる。これに対し、以下の操作を好きなだけ行える。 隣り合う 2 要素をともに -1 倍する 操作後の数列の値の和として考えられる最大値を求めよ。 制約 考えたこと こういう「操作…

Tenka1 2019 D - Three Colors (600 点)

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

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

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

Mujin 2018 D - うほょじご (400 点)

いかにもよくわからない操作問題なので、難しいことは考えずに探索に走るべきな雰囲気 atcoder.jp 問題概要 正の整数 に対し、 で を 10 進表記してできる文字列を反転したものを 10 進表記に持つ整数を表す。 正の整数 が与えられる。 なる整数の組 であっ…

AtCoder AGC 032 B - Balanced Neighbors (700 点)

三角形、四角形、、、と順に作って行って、五角形の場合を作るのに苦労した!!! 問題へのリンク 問題概要 頂点番号が な単純無向であって、以下の条件を満たすものを 1 つ構築せよ: どの頂点についても、その頂点に隣接している頂点の番号の和が等しい 制…

全国統一プログラミング王決定戦 本選 E - Erasure (700 点)

700 点は絶対落とさないのん!!! 本番、DP と包除原理の二通りの方針が早期に見えて、「どちらかで詰まったらどちらかに立ち戻ろう」と思いながら DP に突き進んで見た。それでちゃんと通ってよかった。 問題へのリンク 問題概要 長さ の区間がある。 これ…

AtCoder ABC 117 C - Streamline (300 点)

ソートする問題。 問題へのリンク 問題概要 個のコマを数直線上に配置して、それぞれ移動させる。それによって、 個の地点 をすべて訪れるようにしたい。総移動距離の最小値を求めよ。 制約 考えたこと とりあえず、各コマについて、「行って、引き返して」…

AOJ 1393 Eulerian Flight Tour (ICPC アジア 2018 E)

面白い!!!!!!! 問題へのリンク 問題概要 頂点 辺の無向単純グラフが与えられる (連結とは限らない)。 このグラフに何本かの辺を付け加えることで「連結なオイラーグラフ」にすることができるかどうかを判定し、できるならば一例を示せ。ただし多重辺…

AtCoder ARC 099 E - Independence (700 点)

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