hogecoder

tsutaj 競技プログラミングの記録

数学

Advent Calendar Contest 2020 18 日目: 塗るめた

Advent Calendar Contest 2020 の 18 日目として、ecasdqina さん作の問題の tester を担当しました。tester 解は、writer 解と少しアプローチが異なっていたので紹介したいと思います。また、コンテスタントの提出を見て発見した、形式的べき級数を一切使用…

2018-2019 ACM-ICPC Pacific Northwest Regional Contest (Div. 1) B: Coprime Integers

この辺の (海外の ICPC 問題の) 記事書く人いなさそうなので書きます 問題概要 原文 (PDF): https://codeforces.com/gym/101982/attachments/download/7897/20182019-acmicpc-pacific-northwest-regional-contest-div-1-en.pdf 整数 が与えられる。 を満たす…

Educational Codeforces Round 18 E: Colored Balls

問題概要 原文 → Problem - E - Codeforces 色のボールがあり、 番目の色で塗られたボールは 個ある。 これらのボールを以下の条件を全て満たすように箱に入れる。 それぞれの箱について、箱の中にあるボールの色は 種類のみ 空箱が存在しない 箱に入ってい…

Codeforces AIM Tech Round 5 F: Make symmetrical

問題概要 原文 → Problem - F - Codeforces 以下のクエリを処理せよ。なお、以下で考慮する座標はすべて自然数座標である。 点集合に を追加する 点集合から を削除する 点 が与えられる。その時点の点集合について、原点 と を結んでできる直線に対して線対…

DDCC 2019 予選 D: チップ・ストーリー ~黄金編~

数学的な知見がいっぱいあったので備忘録です。 問題概要 日本語なので原文を参照してください → D: チップ・ストーリー ~黄金編~ - DISCO presents ディスカバリーチャンネル コードコンテスト2019 予選 | AtCoder 解説 この問題を解くには、いくつかの数…

TopCoder SRM 717 Div 2 Hard (Div1 Med): DerangementsStrikeBack

するめうめ tsutaj.hatenablog.com 問題概要 原文 → TopCoder Statistics - Problem Statement 長さ の順列 であって、先頭 要素について が成立するようなものの総数を求めよ。 解説 Div2 では制約が小さいため、以下のように解くことができます。 「先頭 …

TopCoder SRM 723 Div2 Hard: SimpleMazeEasy

するめうめ tsutaj.hatenablog.com 問題概要 原文 → TopCoder Statistics - Problem Statement の部屋が十字型に並んでいる。 (詳細は原文をご覧ください) すべての部屋と部屋の間の最短距離の総和を求めよ。 解説 ※ちゃんとした解説は kmjp さんのブログ に…

TopCoder SRM 724 Div1 Easy: OrAndSum

するめうめ tsutaj.hatenablog.com 問題概要 原文 → TopCoder Statistics - Problem Statement ともに長さが の数列 , が与えられる。以下の条件を満たす長さ の数列 が構成できるかを判定せよ。 解説 まず、任意の非負整数 に対して、 が成立します (これは…

TopCoder SRM 728 Div2 Hard: TrisomorphismEasy

するめうめ 問題概要 原文 → TopCoder Statistics - Problem Statement 頂点の有向グラフがあり、各頂点はそれぞれ から までの番号でラベル付けされている。 ある つの頂点を選び、ラベルをローテーションするという操作を何回か行い、元のグラフのラベリン…

AtCoder Regular Contest 079 D: Decrease (Contestant ver.)

どうやら自分の解法が想定解法と違うみたいなので、別解をブログに残しておきます。 問題概要 日本語なので原文参照 → D: Decrease (Contestant ver.) - AtCoder Regular Contest 079 | AtCoder 解説 まず、出力する数列の長さは に固定してしまいます。この…

AtCoder Beginner Contest 020 D: LCM Rush

もう 7 月かあ・・・。 問題概要 を求めよ。ただし は と の最小公倍数を指す。 制約: 解説 愚直にやるのは無理なので、数学をします。 まず、 なる関係があります。これを使って与式を変形すると が求めたいものになります。 ここで、 の取りうる値の数は …

AtCoder Regular Contest 009 C: 高橋君、24歳

問題概要 原文 → C: 高橋君、24歳 - AtCoder Regular Contest 009 | AtCoder 長さの順列を並び替えたとき、 (1-indexed)となる要素が個になる組み合わせは何通りか。1,777,777,777 (素数) で割った余りを出力せよ。 解説 まず、となる要素をどこにするかを決…