https://atcoder.jp/contests/abc116/tasks/abc116_c 解説 https://atcoder.jp/contests/abc116/submissions/4059474なるべく大きい区間から順にやっていけばいい。 操作を逆に考えて、大きい区間から減らしていく。 高さがあるもので隣り合っているものを連…

https://atcoder.jp/contests/abc116/tasks/abc116_b 解説 https://atcoder.jp/contests/abc116/submissions/4059362シミュレーションをしよう。 ある数が以前に出ていたかを判定するにはsetを使うといい。 以前に出たことある数が出たら、その番号を答える…

https://atcoder.jp/contests/abc116/tasks/abc116_a 解説 https://atcoder.jp/contests/abc116/submissions/4056750∠ABC=90°なので、斜辺でないのはABとBCになる。 なので、AB*BC/2が答え。 int ab, bc, ca; //-------------------------------------------…

https://community.topcoder.com/stat?c=problem_statement&pm=15288N要素の配列Aがある。 この配列からいくつかの要素を取り除いて、validな配列を作る。 validな数列の最大長と、それを作るために取り除く方法の組み合わせを求めよ。※validな配列 要素数が…

T個の皿（tokenだけど）と、P個の置き場所がある。 T個の皿をP個の置き場に一様な確率で順番に置いていく。 このとき、最も多く置かれている置き場所が複数ある（1位タイになっている）確率を求めよ。T, P≦50 前提知識 確率DP （自分の解法では微妙に違うか…

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

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

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

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

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…

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

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

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

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

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

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

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

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

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

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

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

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…

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

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の…

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

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

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

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

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