Pの競プロ記

競技プログラミングに関することを書きます。

ABC

ABC #020 D : LCM Rush

概要2つの正整数a,bの最小公倍数をLCM(a,b)とする。2つの正整数N,Kが与えられるので、を10^9+7で割った余りを求めよ。 100点解法:1≦N≦10^9, 1≦K≦100 101点解法:1≦N,K≦10^9 http://abc020.contest.atcoder.jp/tasks/abc020_d

ABC #018 C 菱型カウント

概要※問題文の内容を少し変更しています。RxCのグリッドがあり、各マスにはoまたはxの印がついている。そこに、「あるマスからユークリッド距離でK-1以内のマスの印を全て変えることのできるスタンプ」を1回押すことができる。例えばK=2のときは、 □■□ ■■■ …

ABC #015 D 高橋くんの苦悩

概要幅がA[i]で重要度がB[i]のスクリーンショットがN枚ある。幅の合計がW以内に収まるようにK枚まで選ぶことができる。 そのときの重要度の合計を最大化する問題。http://abc015.contest.atcoder.jp/tasks/abc015_4解法動的計画法で解くことができる。DPは以…

ABC #014 D 閉路

概要 問題文はこちら http://abc014.contest.atcoder.jp/tasks/abc014_4n個のノードとn-1本のエッジからなる無向グラフがある。 そこに1本エッジを増やして閉路を作った時の閉路の長さを求めよ。・n ・クエリがたくさん解法 エッジを張る2頂点間の距離が分…

ABC #014 C AtColor

概要 問題文はこちら http://abc014.contest.atcoder.jp/tasks/abc014_30から1,000,000までの濃さの絵の具がある。 n人いて、それぞれ「a≦x≦b を満たす濃さ x の絵の具ならば購入する」と言っている。 最も購入される濃さの絵の具を買う人数を求めよ。n 解法…

ABC #012 B 入浴時間

概要 問題文はこちら http://abc012.contest.atcoder.jp/tasks/abc012_2解法 やるだけ。printfのフォーマット指定を復習したかったのでメモ。 http://www.k-cube.co.jp/wakaba/server/format.html表示桁数は、.で決める。 また、リーディングゼロの指定もで…

ABC #011 D 大ジャンプ

概要 問題文はこちら http://abc011.contest.atcoder.jp/tasks/abc011_4解法 本番で解けなかったやつ、2パターンのやり方で解き直した。まず共通する前処理として、どう頑張っても目的地に辿りつけない場合はそこで終了。 そして上下左右同じ距離を進むので…

ABC #011 C 123引き算

ABC

概要 問題文はこちら http://abc011.contest.atcoder.jp/tasks/abc011_3解法 貪欲法やメモ化再帰などで解くことができる。貪欲法で解いたほうがシンプルかと思われる。 NGな値を避けつつ各試行でなるべく大きな値を引いていくようにしていけばよい。メモ化再…