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

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

場合分け

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

今日の以下の類題 drken1215.hatenablog.com 解説はここに書いた。 qiita.com コード 形式的冪級数を用いてみた。 // // Formal Power Series (on runtime mod) // // verified: // Yosupo Judge // https://judge.yosupo.jp/problem/inv_of_formal_power_se…

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) …