hogecoder

つたじろう(Tsuta_J) 競技プログラミングの記録

数学

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 (素数) で割った余りを出力せよ。 解説 まず、となる要素をどこにするかを決…