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

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

場合分け

AtCoder AGC 015 A - A+...+B Problem (200 点)

確かに 200 点かもしれないけど、AGC-A は時々こういう注意力系が出るね。 問題へのリンク 問題概要 個の整数であって、最小が 、最大が であるようなものについて、その総和として考えられる値が何通りあるかを求めよ。 制約 考えたこと この手の問題で重要…

AtCoder AGC 014 D - Black and White Tree (900 点)

最高に好きな問題 問題へのリンク 問題概要 頂点数 のツリー上でゲームを行う。高橋君は残った頂点から 1 つ選んで白く塗る。青木君は残った頂点から 1 つ選んで黒く塗る。 この操作をすべての頂点に色が塗られるまで繰り返したとき、黒く塗られたすべての頂…

Chokudai SpeedRun 002 H - あまり β (400 点)

発想一発ゲー!!!楽しい 問題へのリンク 問題概要 個の以下の問題に答えてください。 整数 を割った余りと整数 を割った余りが等しくなるような正整数のうち最大のものを求めよ 制約 考えたこと だったら、任意の整数が条件を満たすので、-1。それはそう …

AtCoder AGC 008 C - Tetromino Tiling (600 点)

ペアリングを頑張る問題として高難易度なすごく楽しい問題。 結構注意力がいる。割とやばいケースがある。 問題へのリンク 問題概要 下記のテトロミノの個数がそれぞれあたえられる。これらを回転は OK で反転は NG で組み合わせて の長方形を作りたい。作れ…

みんなのプロコン 2019 C - When I hit my pocket... (400 点)

こういう O(1) なペアリングを頑張る系の問題が本当に苦手。。。 問題へのリンク 問題概要 すぬけ君は最初、ビスケットを 1 枚持っており、日本円は持っていません。 すぬけ君は、以下の操作を好きな順に合計ちょうど K 回行います。 持っているビスケットを…

diverta 2019 E - XOR Partitioning (800 点)

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

Tenka1 2019 F - Banned X (800 点)

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

Tenka1 2019 D - Three Colors (600 点)

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

AOJ 2213 多項式の解の個数 (UTPC 2010 J)

今日の以下の類題 drken1215.hatenablog.com 解説はここに書いた。 qiita.com

Tenka1 2019 E - Polynomial Divisors (800 点)

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

AtCoder AGC 002 E - Candy Piles (1400 点)

やった!自力で解けたー!!! メチャクチャ楽しい問題だった。 問題へのリンク 問題概要 キャンディの山が 個あって、それぞれ 個のキャンディが積まれている。先手と後手が交互に キャンディが 1 個以上あるすべての山について、1 個ずつキャンディを取る …

AtCoder AGC 032 C - Three Circuits (800 点)

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

AtCoder AGC 004 A - Divide a Cuboid (200 点)

割と難しい気がする。数学センスが少し必要な感じ 問題へのリンク 問題概要 のブロックが の直方体状に並んでいます。 高橋君は各ブロックを赤色または青色で塗ろうとしています。 このとき、次の条件が成り立つようにします。 赤いブロックも青いブロックも…

AtCoder AGC 002 A - Range Product (200 点)

注意力系。現在の AGC ではあまり見ない系な気もする。 問題へのリンク 問題概要 整数 が与えられる。 すべての積が正か負か 0 かを判定せよ。 制約 考えたこと こういうのは場合分けを丁寧にやろう!!! まず、 のケースがわかりやすく になる。 そう思っ…

AtCoder AGC 032 B - Balanced Neighbors (700 点)

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

TCO 2013 Round 2A Med TheMagicMatrix

mod. p での連立一次方程式の練習などに!!! 問題へのリンク 問題概要 × のマス目があり、そのうちの マスについては既に 以上 以下の数値が入れられている。残りの マスに 以上 以下の数値を入れる方法のうち どの行の和と、どの列の和をとっても、その一…

AOJ 3045 Painting (ACPC 2018 day2 G)

コンテスト本番、つたじぇーが頑張って通してくれた!!! 問題へのリンク 問題概要 長さ の数列 が与えられる。初期状態では の要素は全て 0 である。加えて、 個の整数のペア()が与えられる。各ペアに対し以下の操作を行い、最終的な数列 を出力せよ。 各 …

AtCoder AGC 003 D - Anticube (1100 点)

とくらちゃん・シンヤカトー・てんぷらたんたちと気合いで解いた。 問題へのリンク 問題概要 個の正の整数 が与えられる。この中から最大個数の要素を取り出して どの 2 つをとってもその積が立方数とはならない という条件を満たすようにせよ。 制約 解法 …

AOJ 2894 01 文字列と窓 (AUPC 2018 day3 F)

丁寧に考えれば解ける感じ 問題へのリンク 問題概要 0 と 1 のみかならなる長さ N のビット列 S, T が与えられる。S に以下の操作を好きな回数だけ行って T にするのに必要な最小回数を求めよ。 (というクエリが Q 回投げられる) S の最も右にある 1 を含む…

AtCoder AGC 008 A - Simple Calculator (300 点)

もれなく正確に解くための考え方とかが問われる感じ。 問題へのリンク 問題概要 (AGC 008 A) 整数 が与えられる。 に以下のいずれかの操作を最小回数行って に一致させよ: を 1 増やす を にする 解法 最適解は 最初に反転する (かしないか) 「1 増やす」を…

AtCoder ARC 094 D - Worst Case (700 点)

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

AtCoder AGC 026 E - Synchronized Subsequence (1600 点)

こういうのちゃんと解き切れるようになりたい... なんだろ、「'a' と 'b' の個数が等しくなるような区間ごとに分割する」という発想がちゃんと出て来るようにするためには、どういう流れの考察をすればよいのだろう... 問題へのリンク 問題概要 (AGC 026 E) …