@morio_progの精進日記

解いた競プロの問題をつらつらと。(AtCoder: morio__)

【codeFlyer】C - 徒歩圏内

問題概要 N個の都市がそれぞれ座標X_iにある. 2つの都市間の距離がD以下であれば徒歩で, そうでなければ電車で移動する. このとき, 3つの都市の組(i, j, k)であり, 以下の条件を満たすものの個数を求めよ. i < j < k 都市iと都市j, 都市jと都市kを徒歩で移動…

【ABC041】D - 徒競走

問題概要 匹のうさぎがいる. 人の観客から, うさぎがうさぎよりも先にゴールしたという情報を得た. これら全ての情報に合致する着順が何通りあるかを求めよ. 制約 考察 bitDPをする. dp[何匹見たか][状態]としたとき, 各うさぎがすでにゴールしたかをbitの状…

【ABC115】D - Christmas

問題概要 レベルLのバーガーを以下のように定義する. レベル0のバーガーは, 'P'. レベルLのバーガー(L>=1)は, 'B' + (レベルL-1のバーガー) + 'P' + (レベルL-1のバーガー) + 'B'. このとき, レベルNのバーガーの下からX層までに'P'は何個あるか求めよ. 制約…

【ARC071】E - TrBBnsformBBtion

問題概要 'A', 'B'のみからなる文字列S, Tが与えられる. Sの部分文字列sについて, 以下の4つの操作を好きなだけ行ってよいとき, Tの部分文字列tに変換することは出来るかという判定クエリにq個答えなさい. 'A'を'BB'にする. 'B'を'AA'にする. 'AAA'を消す. '…

【ABC114】D - 756

問題概要 N!の約数のうち, 約数をちょうど75個持つものの個数を求めよ. 制約 1 <= N <= 100 考察 約数が75個ある整数を素因数分解したときどうなるか考えてみると, a2 * b4 * c4 a2 * b24 a4 * b14 a74 の4通り. とりあえずN!の素因数がそれぞれ何個ずつある…

【ABC114】C - 755

問題概要 1以上N以下の整数のうち, '7', '5', '3'が1回ずつ現れ, なおかつそれら以外の数字が現れないものの個数を求めよ. 制約 1 <= N < 109 考察 bit全探索的なノリで数えるみたい. とりあえず3進法で書いてみたけど, 頭の0に対応するのめんどくさそうだっ…

【Tenka1 Programmer Contest】D - Crossing

問題概要 の部分集合の組について, 以下の条件を満たすものがあれば構築せよ. [条件1] のうちどの整数も, のうちちょうど2つに含まれる. [条件2] のうちどの2つの集合をとっても, その共通成分はちょうど1つである. 制約 考察 とりあえず, について考えてみ…

【Tenka1 Programmer Contest】C - Align

問題概要 の個の整数を好きな順番に並べたとき, 隣り合う要素の差の合計の最大値を求めよ. 制約 考察 とりあえず個の整数をソートする. 最小の数字と最大の数字は隣同士であってほしいお気持ちになったので, 一旦そこを並べる. 次は最小の方に2番目に大きい…

【ABC048】D - An Ordinary Game

問題概要 操作後に同一の文字が隣り合わないように, 両端以外からお互いに1文字ずつ取り除いていく. このような操作を行うことが出来なくなった方が負けとなる. 先手と後手のどっちが勝つかを出力せよ. 制約 の中に同一の文字が隣り合う箇所はない 考察 操作…

【ARC064】E - Cosmic Rays

問題概要 座標全体に宇宙線が降り注いでいる. 座標上に中心,半径の個のバリアがあり, バリア内では宇宙線から逃れられる. このとき, からまで移動したときの, 宇宙線に晒される距離の最小値を求めよ. 制約 考察 まず, バリア間を移動する際の最短距離を考え…

【Educational Codeforces】D - Bicolorings【Round 51】

問題概要 2列n行のマス目を白黒に塗り分ける。塗り分けた後、区画がk個できるような塗り分け方の数を求めよ。結果はかなり大きい数になるため、998244353で割ったあまりを出力せよ。 制約 1 <= n <= 1000 1 <= k <= 2n 考察 ぱっと見DPっぽいのでDPをする。 …

【ABC103】D - Islands War

問題概要 東西に一列に並ぶN個の島と、それをつなぐN-1個の橋がある。 a_iとb_iの間を行き来できないようにしろ、という要望がM個寄せられた。 取り除かなければならない橋の本数の最小値を求めよ。 制約 2 <= N <= 105 1 <= M <= 105 1 <= a_i < b_i <= N …

【Summer Festival Contest 2018】E - 石積み (Pyramid Piling)

問題概要 https://beta.atcoder.jp/contests/summerfes2018-div2/tasks/summerfes2018_e 制約 2 <= N <= 105 考察 2次元のやつを眺めてたら三角数の並びしてたから、n次元に拡張されたものあるやろっておもったらほんとにあった n次元三角数の式をこねくり回…

【CODE FESTIVAL 2015】D - 壊れた電車【予選A】

問題概要 それぞれX_i両目の車両にいるM人の整備士が、N両編成の電車をすべて点検し終えるのに最短で何分かかるか求めよ。但し、点検には時間はかからないが、隣の車両に移動するのには1分かかるものとする。 制約 1 <= N <= 109 1 <= M <= 105 M <= N 1 <= …

【ABC043D】アンバランス / Unbalanced【ARC059B】

問題概要 文字列sの中に、過半数が同じ文字となる2文字以上の部分文字列t(アンバランスな部分文字列)は存在するか判定せよ。tが存在するならその区間を、しないなら-1 -1を出力せよ。 制約 2<=|s|<=105 sは小文字のアルファベットのみからなる。 考察 tは2文…