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

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

CodeforcesR1900

Codeforces Round #557 (Div. 1) B. Chladni Figure (R1900)

KMP 法で殴ったけど、愚直にやっても調和級数的計算量で間に合うね。 問題へのリンク 問題概要 円周上に等間隔に 個の点が打たれている。これらの点を端点とした 個の線分がある (下図のような感じ)。 これが回転対象性をもつかどうかを判定せよ (1 周未満の…

Codeforces Round #680 (Div. 1) B. Divide and Sum (R1900)

本番は「どのように に分けても絶対値和は等しい」ということに気づかず、ものすごくエグい二項係数計算を頑張って綺麗な表式を得た。 問題へのリンク 問題概要 長さが の数列 が与えられる。 数列を 個ずつのペア (順序の違いは考慮する) に分ける方法は 通…

Codeforces Round #615 (Div. 3) E. Obtain a Permutation (R1900)

こういうのをちゃんと解けるようになったのは成長! 問題へのリンク 問題概要 (意訳) 以下の 個のクエリに答えよ。 番目のクエリでは、数列 が与えられる。この数列に以下のいずれかの操作をほどこして、 となるようにしたい。その最小回数を求めよ。 を任意…

Codeforces Round #586 (Div. 1 + Div. 2) D. Alex and Julian (R1900)

すごく面白かった 問題へのリンク 問題概要 (表現改) 個の正の整数 が与えられる。これらから最小個数を取り除いて、以下の条件を満たすようにせよ。 残った整数から重複を許して奇数個選ぶどのような方法に対しても、選ばれた整数を 2 つに分けてそれぞれの…

Codeforces 500 DIV1 B. Chemical table (R1900)

確かに、ついこの間の ABC 131 F の類題だね 問題へのリンク 問題概要 のグリッドがあって、 マス分が黒く塗られている 長方形の三頂点状に並んだ黒マスの組を選んで、残りの頂点に相当する位置を黒く塗る (コスト 0) 黒くないマスを一つ選んで黒く塗る (コ…

Codeforces Global Round 2 E - Pavel and Triangles (R1900)

こういう貪欲は確実に抑えて行きたい 問題へのリンク 問題概要 長さが の線分がそれぞれ 本ずつある。 これらから三角形は最大で何個作れるか? 制約 考えたこと 面白そう!!!!! な量を扱う問題リストにまた 1 問加えられる!!!!! この手の問題では…

Codeforces #547 Div. 3 F - Same Sum Blocks (Hard) (R1900)

区間スケジューリングと聞いて 問題へのリンク 問題概要 要素からなる数列 が与えられる。以下の条件を満たす最大個数の区間を求めよ (どれか 1 つ復元せよ)。 どの 2 つの区間も交差しない どの区間についても含まれる値の総和が等しい 制約 考えたこと 区…