はまやんはまやんはまやん

hamayanhamayan's blog

競技プログラミング

MostFrequentLastDigit [SRM747 Easy]

N要素の以下のルールを満たす配列を構築せよ 全ての要素が異なる 0~10^9の数から成る 10で割り切れる数はダメ 全ての2つの要素を取ってきて和をとったときの最下位の桁を集計したときに、dが最も多くなる(タイはダメ) n≦200, d≦9 解説 d=5のときを考えて…

大吉数列 (Array of Fortune) [DISCO presents ディスカバリーチャンネル コードコンテスト2019 本戦 B]

https://atcoder.jp/contests/ddcc2019-final/tasks/ddcc2019_final_b 解法 https://atcoder.jp/contests/ddcc2019-final/submissions/4045691構築系にはいくつか考え口がある。 まずは、最大ケースを考えてみる。 すると、降順に並べるのが、最大ケースであ…

DISCO! [DISCO presents ディスカバリーチャンネル コードコンテスト2019 本戦 D]

https://atcoder.jp/contests/ddcc2019-final/tasks/ddcc2019_final_d 前提知識 半環問題 解説 https://atcoder.jp/contests/ddcc2019-final/submissions/4045056これはやったことが無いと解くのは難しい。 半環問題というのがある。 (正直自分は半環という…

レース (Race) [DISCO presents ディスカバリーチャンネル コードコンテスト2019 本戦 A]

https://atcoder.jp/contests/ddcc2019-final/tasks/ddcc2019_final_a 解説 https://atcoder.jp/contests/ddcc2019-final/submissions/4044638「Sにおいて、- は必ず別の - と隣接して現れる」という奇妙な条件があるので、ここから考える。 この条件は「>->…

Exam and Wizard [KEYENCE Programming Contest 2019 / キーエンス プログラミング コンテスト 2019 C]

https://atcoder.jp/contests/keyence2019/tasks/keyence2019_c 解説 https://atcoder.jp/contests/keyence2019/submissions/4015448貪欲に構成していく。 最初はC[i]=B[i]とする。 この段階でCの和smBがsmAを上回っていれば、構築できないので、-1 次にd=sm…

KEYENCE String [KEYENCE Programming Contest 2019 / キーエンス プログラミング コンテスト 2019 B]

https://atcoder.jp/contests/keyence2019/tasks/keyence2019_b 解説 https://atcoder.jp/contests/keyence2019/submissions/3999565取り除く領域を全探索する。 c++であれば、文字列操作はsubstrを使うのがおすすめ。 空の連続部分文字列を取り除く操作が許…

Beginning [KEYENCE Programming Contest 2019 / キーエンス プログラミング コンテスト 2019 A]

https://atcoder.jp/contests/keyence2019/tasks/keyence2019_a 解説 https://atcoder.jp/contests/keyence2019/submissions/3998411並び替えて1974が作れる数字の列はソートしたときに1479となる数列である。 なので、ソートして見ていけばいい。 int N, A[…

Andrew and Taxi [Codeforces Round #532 (Div. 2) E]

https://codeforces.com/contest/1100/problem/EN頂点、M辺の有向グラフがある。 辺には有向辺の向きを変えるのに必要なコストCがある。 任意本の辺の向きを変えて有向グラフをDAGにしたい(サイクルを無くしたい)。 必要なコストの最小値と、その時向きを…

Dasha and Chess [Codeforces Round #532 (Div. 2) D]

https://codeforces.com/contest/1100/problem/Dインタラクティブ問題。 999×999のマスでゲームをする。 プレイヤーは1つのキングを持っている。 キングは1ターンで周り8マスを動ける。 最初は(x,y)にいる。 プレイヤー先攻 相手は666個のルークを持ってる。…

NN and the Optical Illusion [Codeforces Round #532 (Div. 2) C]

https://codeforces.com/contest/1100/problem/C中心に半径rの円がある。 この円の周りに半径Rの円をN個敷き詰めたい。 半径Rを求めよ。N,R≦100 解説 https://codeforces.com/contest/1100/submission/48337940以下の説明では、内側の半径がR, 外側の半径がr…

Build a Contest [Codeforces Round #532 (Div. 2) B]

https://codeforces.com/contest/1100/problem/BN種類の問題がある。 ここで、M個の問題が順番に作問される。 N種類の問題が全て1個以上作られた場合に、N種類の問題を1つずつ使ってコンテストを開く。 コンテストを開くと問題が1つずつ減る。 M個の問題が作…

Roman and Browser [Codeforces Round #532 (Div. 2) A]

https://codeforces.com/contest/1100/problem/AN要素の配列Aがある。 ある数Kもある。 ここである数Bを定めて、BからK個飛ばしで到達できる要素以外の数、 つまり、B+iK(iは整数)の添字の要素以外の数の総和を求める。 この総和の絶対値の最大値は?K,N≦1…

Attack to a Tree [AISing Programming Contest 2019 / エイシング プログラミング コンテスト 2019 E]

https://atcoder.jp/contests/aising2019/tasks/aising2019_e 前提知識 二乗の木DP 解説 https://atcoder.jp/contests/aising2019/submissions/3989621二乗の木DPというものがあり、それを利用する。 dp[cu][cut] := 頂点cuを根とした部分木について辺の削除…

Nearest Card Game [AISing Programming Contest 2019 / エイシング プログラミング コンテスト 2019 D]

https://atcoder.jp/contests/aising2019/tasks/aising2019_d 解説 https://atcoder.jp/contests/aising2019/submissions/3994956T:高橋くんとA:青木くんがどう取るかを考えると、 ATATATAAATTT のようになる。 つまり、ATATAT部分とAAA部分とTTT部分である…

Alternating Path [AISing Programming Contest 2019 / エイシング プログラミング コンテスト 2019 C]

https://atcoder.jp/contests/aising2019/tasks/aising2019_c 解説 https://atcoder.jp/contests/aising2019/submissions/3985742問題の言い換えをする必要がある。 隣接していて、色が異なっているマスの間に辺を張ったときの連結成分を考えると、 その中の…

Contests [AISing Programming Contest 2019 / エイシング プログラミング コンテスト 2019 B]

https://atcoder.jp/contests/aising2019/tasks/aising2019_b 解説 https://atcoder.jp/contests/aising2019/submissions/3984416問題は1,2,3問目のどれか1つにしか使えない。 なので、1,2,3問目についてつける問題を数える。 あとは、その最小値が作れるコ…

Bulletin Board [AISing Programming Contest 2019 / エイシング プログラミング コンテスト 2019 A]

https://atcoder.jp/contests/aising2019/tasks/aising2019_a 解説 https://atcoder.jp/contests/aising2019/submissions/3983145横Nマスで連続してWマス分取る方法は(N-W+1)通りある。 同様に縦についても(N-H+1)通りあるので、(N-H+1)*(N-W+1)が答え。 int…

門松計画 [yukicoder No.783]

https://yukicoder.me/problems/no/783 前提知識 動的計画法 解説 https://yukicoder.me/submissions/309701dpで解く。 dp[len][prepre][pre][c] := 長さlenの門松列列であり2つ前の竹がprepreで1つ前の竹がpreであり、お金の残高がc円であるときの長さの総…

円周上の格子点の数え上げ [yukicoder No.781]

https://yukicoder.me/problems/no/781 解説 https://yukicoder.me/submissions/310016原点Oを中心とする、半径root(R)の円の式は x^2+y^2=Rとなる。 よって、格子点は x,yが整数でx^2+y^2=Rを満たす頂点である。 Rの最大値が10^7であるが、このときのx,yの…

オフ会 [yukicoder No.780]

https://yukicoder.me/problems/no/780 解説 https://yukicoder.me/submissions/309502場合分けして解く。 男の子はヤスオくん含めてA+1人いる。 よって、女子はその人数以上じゃないとヤスオくんは遊べない。 なので、A+1≦BならYES、そうでないならNO ペア…

Heisei [yukicoder No.779]

https://yukicoder.me/problems/no/779 解説 https://yukicoder.me/submissions/309481日付を前後関係を維持しながら数値に変換するエンコーダを書く。 f(y, m, d) := y年m月d日を数値に変換する あとは、それを使って大小比較する。 int Y, M, D; //-------…

Educational DP Contestの勧め

Educational DP Contest Educational DP Contest 典型的なDPの問題をまとめたコンテスト 自分の記事へのリンクまとめとして書く ネットを漁ると色々な人が問題・前提知識について解説を書いているので、問題に詰まった場合は適宜ぐぐるといい あと、前提知識…

Frog 3 [Educational DP Contest / DP まとめコンテスト Z]

https://atcoder.jp/contests/dp/tasks/dp_z 前提知識 CHTによるDP高速化 解説 https://atcoder.jp/contests/dp/submissions/3956069以下の解説の前にCHTについてわかっていないと以下は理解できない。 とりあえず、複数の1次関数にxを代入したときの最小値…

Grid 2 [Educational DP Contest / DP まとめコンテスト Y]

https://atcoder.jp/contests/dp/tasks/dp_y 前提知識 包除原理 解説 https://atcoder.jp/contests/dp/submissions/3956127同様の包除原理問題を見たことがあったから、包除原理で解くと分かったので、考察過程は無いです。 わかりやすさのために段階的に解…

Tower [Educational DP Contest / DP まとめコンテスト X]

https://atcoder.jp/contests/dp/tasks/dp_x 前提知識 動的計画法テク「選択するものを最初にソートしておくと、DPできたり、状態を同一化できたりする」 解説 https://atcoder.jp/contests/dp/submissions/3980762動的計画法で困るのが、順番が任意である場…

Intervals [Educational DP Contest / DP まとめコンテスト W]

https://atcoder.jp/contests/dp/tasks/dp_w 前提知識 データ構造によるDP更新最適化 区間add, 区間max遅延評価セグメントツリー 解説 https://atcoder.jp/contests/dp/submissions/3963076dp[r] := r文字目まで確定していてr文字目が1であり、それ以降は0で…

Subtree [Educational DP Contest / DP まとめコンテスト V]

https://atcoder.jp/contests/dp/tasks/dp_v 前提知識 全方位木DP 解説 https://atcoder.jp/contests/dp/submissions/3955506全方位木DPをする。 dfs1で0を根として普通に木DPをする。 次に、dfs1で作ったDPを改変しながら、dfs2で全ての頂点を根として答え…

Grouping [Educational DP Contest / DP まとめコンテスト U]

https://atcoder.jp/contests/dp/tasks/dp_u 前提知識 O(3^N)でのbitDP 解説 https://atcoder.jp/contests/dp/submissions/3949705制約からbitDP感がある。 dp[msk] := グループが決まったうさぎがmskである場合の点数の最大値 dp[msk]を確定させたいときに…

Permutation [Educational DP Contest / DP まとめコンテスト T]

https://atcoder.jp/contests/dp/tasks/dp_t 前提知識 BITによる更新最適化 解説 https://atcoder.jp/contests/dp/submissions/3980491正直自分で以下のDPを思いついてないので、思いつく過程は分からない。 色々な要素が絡む難しい問題なので、TLEするDPを…

Digit Sum [Educational DP Contest / DP まとめコンテスト S]

https://atcoder.jp/contests/dp/tasks/dp_s 前提知識 桁DP 解説 https://atcoder.jp/contests/dp/submissions/3949534桁DPをする。 dp[dgt][d][isless] := 上からdgt桁目まで確定していて、各桁の数字の総和modDがdで、K未満かどうかがisless(isless=1なら…