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

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

AtCoder800点

第一回日本最強プログラマー学生選手権-予選- E - Card Collector (800 点)

マトロイドだ!!!!!!! 問題へのリンク 問題概要 のボード上の 個のコマがあってそれぞれ重みがつけられている。同じマスに複数のコマが置かれていることもある。 今、各行から 1 個以下のコマを取り去る。次に各列から 1 個以下のコマを取り去る。 最…

AtCoder ARC 074 E - RGB Sequence (800 点)

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

diverta 2019_2 E - Balanced Piles (800 点)

最初は絶望感がヤバイタイプの問題。とても解ける問題には見えない。でも落ち着くと解ける。 こういう問題を作れるのはすごい。 問題へのリンク 問題概要 個のマスに積み木を重ねていく。最初はどのマスも 0 段である。以下の操作を繰り返して、最終的にすべ…

diverta 2019 E - XOR Partitioning (800 点)

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

AtCoder AGC 033 C - Removing Coins (800 点)

これ大好き!!! 問題へのリンク 問題概要 頂点のツリーが与えられる。 初期状態ではすべての頂点に 1 枚ずつコインが乗っている。先手と後手が交互に コインが 1 枚以上乗っている頂点を 1 つ選び、その頂点のコインを取り除き その頂点以外の全頂点につい…

Tenka1 2019 F - Banned X (800 点)

かなり時間かかった 問題へのリンク 問題概要 のみからなる長さ の数列であって、どの連続する部分列に対してもその総和が にならないようなものの個数を 998244353 で割ったあまりを求めよ。 制約 考えたこと 最初は包除原理かな...と思ったけど、どうにも…

Tenka1 2019 E - Polynomial Divisors (800 点)

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

AtCoder AGC 032 C - Three Circuits (800 点)

見るからにコーナーケースが怖い... atcoder.jp 問題概要 頂点 本の辺からなる単純かつ連結な無向グラフが与えられます。 全ての辺をちょうど一回ずつ使って つのサーキットを作ることが可能かどうかを判定してください。 制約 考えたこと 輪っかを 3 つ作る…

AtCoder AGC 031 C - Differ by 1 Bit (800 点)

証明はできるし、その証明に基づいた構成を数学的に与えることまではできるけど、それを実装に落とすのがすごく大変な問題。。。 問題へのリンク 問題概要 整数 が与えられます。 の順列 であって、 次の条件をすべて満たすものが存在するかどうか判定してく…

みんなのプロコン 2019 E - Odd Subrectangles (800 点)

すごく面白そうだし、これ考えたかった 問題へのリンク 問題概要 × の binary 行列 が与えられる。 行集合の部分集合 通り 列集合の部分集合 通り の組であって、 の各要素のうち、行と列がともに該当する部分集合に含まれるようなものの総和が奇数となって…

みんなのプロコン 2018 決勝 B - 経路が色々 (800 点)

解説は三進法でやってたけど、二進法でもできた 問題へのリンク 問題概要 次をすべて満たすようなマス目を構成せよ。 マス目の各マスは白か黒で塗られている マス目の縦横の長さをそれぞれ N,M としたとき、N,M は 1 以上 100 以下である 一番左上のマスから…

AtCoder AGC 029 D - Grid game (800 点)

これは。。。C より先に確実にこれをとったのはよかった 問題へのリンク 問題概要 (意訳) H × W の二次元グリッドがあって、各マスは通路か壁である。壁は N 個ある。最初は (1, 1) に駒がある。 毎ターン (x, y) にある駒は (x + 1, y) に進める、ここで (x…

AtCoder AGC 008 D - K-th K (800 点)

実装は手こずったものの、それなりに自信のある Greedy を提出できて一発 AC できてよかった 問題へのリンク 問題概要 1 〜 の値を 個ずつもつ長さ の数列であって、 各 について、 番目の値が 個目の である という条件を満たすものを 1 つ構築せよ。条件を…

AtCoder AGC 004 D - Teleporter (800 点)

こういう系の問題、なかなか提出が怖くなるやつ。こういうのは背水の陣状態じゃないと躊躇してしまいそう... 問題へのリンク 問題概要 頂点数 、辺数 の有向グラフが与えられる。 どの頂点から出る辺数も 1 どの頂点から出発しても必ずノード 1 (root) にた…

CODE FESTIVAL 2018 qual A E - オレンジとみかん (800 点)

解き切りたかった 問題へのリンク 問題概要 オレンジが 個、みかんが 個ある。これを 人で分け合う ( が の倍数であることは保証される)。 それぞれの人 について、オレンジとみかんそれぞれ 1 個あたりの満足度が で与えられる。 うまく分けて、各人の満足…

SoundHound 2018 本戦 C - Not Too Close (800 点)

好き系。本番解きに行ったけど、もっとサクッと通せればよかった。 問題へのリンク 問題概要 頂点の無向グラフ (頂点の番号は 1 〜 ) であって、以下の条件をすべて満たすものの個数を 1000000007 で割ったあまりを求めよ。 頂点 1 と 2 との間の最短距離が …

2018 codeFlyer 本選 F - 配信パズル (800 点)

本番中なんとか解けたけど、すごくグチャグチャしたん。 問題へのリンク 問題概要 すぬけ君は、 日間にわたって、毎日次のようなパズルを解こうとしている。 すぬけ君の持っている端末に、縦 行、横 列からなる格子状の盤面が毎日配信されてくる。それぞれの…

AtCoder AGC 025 D - Choosing Points (800 点)

二部グラフ解法頭いいと思ったものの、整数論的考察で通したのでその報告を。TL 見た限りだと、kirika さんと同じ解法っぽいですがかなり少数派っぽいです (ただし、自分はイデアルという概念を意識できてはいなかったです...)。 d1=2^k * u (u は奇数) とす…