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

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

旧ARC-D

AtCoder ARC 042 D - あまり (黄色)

離散対数の verify に 問題へのリンク 問題概要 4 つの整数 が与えられる。 は素数である。 整数 が の範囲を動くときの、 を で割ったあまりの最小値を求めよ。 制約 は素数 考えたこと まず、 を満たす最小の正の整数 を求める (これを位数と呼ぶ)。これは…

AtCoder ARC 028 D - 注文の多い高橋商店 (赤色)

戻す DP を履修して行く!!! 問題へのリンク 問題概要 個の正の整数 と正の整数 が与えられる。以下の 個のクエリに答えよ。 整数 が与えられる 以下の条件を満たす 0 以上の整数の組 () の個数を 1000000007 で割ったあまりを求めよ 制約 考えたこと この…

AtCoder ARC 007 D - 破れた宿題 (橙色)

一瞬激ヤバに見えるし、コーナーケースの数もえげつないけど、とりあえず最小の初項はすぐにわかると... 問題へのリンク 問題概要 等差数列があった。 等差数列を concat して得られる文字列から、先頭から何文字かと、末尾から何文字かを削除して得られた文…

AtCoder ARC 012 D - Don't worry. Be Together (赤色)

経路数に帰着して頑張って二項係数計算するところは面白かった! そのあとの任意 mod の二項係数処理は、今の AtCoder ではあまり出なさそうかな。 問題へのリンク 問題概要 個の座標 についての以下の値 を積算した値を で割ったあまりを求めよ。 原点から…

AtCoder ARC 038 D - 有向グラフと数 (赤色)

後退解析を用いる問題。queue に不慣れなので、急に queue を使えるように。 問題へのリンク 問題概要 頂点 辺の有向グラフが与えられる。各頂点 には値 X_v が割り振られている。先手と後手とで以下の対戦を行う スタート時には駒を頂点 1 に置く 各プレイ…

AtCoder ARC 004 D - 表現の自由 (黄色)

これがインフレ!?ABC 110 D - Factorization に瓜二つ 問題へのリンク 問題概要 整数 を 個の整数の積として表す方法が何通りあるかを、1000000007 で割ったあまりを求めよ。 制約 考えたこと ほとんど、ABC 110 D - Factorization と一緒。 だが、マイナ…

AtCoder ARC 039 D - 旅行会社高橋君 (橙色)

二重辺連結成分分解ライブラリを整えた。 問題へのリンク 問題概要 N 頂点, M 辺の無向単純グラフにおいて、以下の Q 個のクエリに答えよ。 A B C: A から出発して B に行くウォークと、B から出発して C に行くウォークの組のうち、辺を共有しないものがあ…

AtCoder ARC 008 D - タコヤキオイシクナール (橙色)

セグメントツリーの二項演算は、モノイドについて実現され、結合法則のみ満たしていれば交換法則が必要ないことをハッキリと映し出した問題を解きました。 セグメントツリーの二項演算に必要な要件について koba さんの記事がとても参考になります: データ構…