https://codeforces.com/contest/1142/problem/B長さNの順列Pと、長さMの数列Aがある。 数列Aの要素は[1,N]である。 これについて以下のクエリに答える。 A[L,R]の部分列でvalidな部分列が存在するなら1, 存在しないなら0を答える。 valid ⇔ 順列Pを0回以上…

https://codeforces.com/contest/1142/problem/A円状に頂点1から頂点nkまで並んでいる。 1, K+1, 2K+1, ...のようにN個のお店がある。 最初に頂点sと距離lを決める。 s, s+l, s+2l, ... のように距離lで頂点の数が増える方向に移動して、sに戻ってきたら操作…

https://atcoder.jp/contests/exawizards2019/tasks/exawizards2019_d 前提知識 動的計画法 解説 https://atcoder.jp/contests/exawizards2019/submissions/4770817 DPテクを組み合わせる。 「2. 選択するものを最初にソートしておくと、DPできたり、状態を…

https://atcoder.jp/contests/exawizards2019/tasks/exawizards2019_c 前提知識 二分探索 解説 https://atcoder.jp/contests/exawizards2019/submissions/4778445check(x) := x番目にあるゴーレムが全呪文を終えた後にある位置 これを作ってみると、 -1 -1 -…

https://atcoder.jp/contests/exawizards2019/tasks/exawizards2019_b 解説 https://atcoder.jp/contests/exawizards2019/submissions/4764937BとRの数を数えて、B＜RならYesと答える問題。 どんなふうに数えてもいいが、map＜char,int＞で数えている。 int …

https://atcoder.jp/contests/exawizards2019/tasks/exawizards2019_a 解説 https://atcoder.jp/contests/exawizards2019/submissions/4778304正三角形となるのは、全ての辺の長さが等しいときである。 なので、それを確かめればいい。 int A, B, C; //-----…

https://atcoder.jp/contests/abc122/tasks/abc122_d 前提知識 動的計画法 解説 https://atcoder.jp/contests/abc122/submissions/4712538条件を満たす文字列を良い文字列と呼ぶことにする。 dp[s] := 最後の3文字がsである良い文字列の組合せ 最初はdp["###…

https://atcoder.jp/contests/abc122/tasks/abc122_c 前提知識 https://www.hamayanhamayan.com/entry/2017/07/04/020117:titl=累積和 解説 https://atcoder.jp/contests/abc122/submissions/4712429最初の考察が一番むずかしいと思うが、本題よりもう少し簡…

https://atcoder.jp/contests/abc122/tasks/abc122_b 解説 https://atcoder.jp/contests/abc122/submissions/4702739Sの長さがとても短いので、Sの部分文字列すべてについて考えることができる。 部分文字列S[L...R]について、ACGT文字列であるかを判定する…

https://atcoder.jp/contests/abc122/tasks/abc122_a 解説 https://atcoder.jp/contests/abc122/submissions/4702647S[i]と対になるのがT[i]となるように定義しておく。 後は、S[i]=BであるときにT[i]を答えれば答えになる。 char B; string S = "ATCG", T =…

今回はオレオレ詐欺にあったので、啓発も兼ねて記事にします。 唐突なDM 2019/03/24の午前3時頃の話だ。 B'zのLiveDVDの4週目視聴がちょうど終わり、さあ寝るかという時間であった。 普段は全然使っていないDiscordにDMが入っているのに気がついた。 redcode…

https://yukicoder.me/problems/no/807 前提知識 ダイクストラ 解説 https://yukicoder.me/submissions/327912往復で1回だけ道のコストを0にできるということだが、双方向の無効グラフなので、 特に往復については考える必要はない。 重要なのは、「普通に頂…

https://yukicoder.me/problems/no/806 解説 https://yukicoder.me/submissions/327823わかってしまえば簡単な問題。 道を作るということなので、次数が3以上のものはどういう操作を行うにしても、辺を切る必要がある。 切った後は、どこにつなげるかはどう…

https://yukicoder.me/problems/no/805 解説 https://yukicoder.me/submissions/327804N≦5000なので、3つのうち2つを全探索できる。 i,jを決めると、kが一意に定まるので、i,j,kでUMGであれば、答えをインクリメントして数えていく。 int N; string S; //---…

https://yukicoder.me/problems/no/804 解説 https://yukicoder.me/submissions/327794制約が余り大きくないので、答えの候補を全探索できる。 野菜の個数を固定すると、肉の個数が分かるので、お肉の上限と合わせての個数上限を見て、実現できる野菜の個数…

https://yukicoder.me/problems/no/801 前提知識 動的計画法更新最適化（累積和, imos） 解法 https://yukicoder.me/submissions/325930dp[k][floor] := k回移動後にfloor回にいる組合せ でDPしよう。 dp[k][???]からdp[k+1][???]を高速に更新することを考え…

https://yukicoder.me/problems/no/800 解説 https://yukicoder.me/submissions/325337まずはz,wを全列挙しよう。 z,wがわかっていれば、d = w^2 + D - z^2とおくと、 x^2 + y^2 = d を満たすx,yの組が分かれば、それを答えに足せばいいと分かる。 よって、z…

https://yukicoder.me/problems/no/799 解説 https://yukicoder.me/submissions/325296「全通り-被ってしまった場合」で答えを出す。 全通りは、(B-A+1)*(D-C+1)である。 被ってしまった場合は、同じ数がでてきた場合になるので、[A,B]と[C,D]が重なっている…

https://atcoder.jp/contests/agc031/tasks/agc031_b 前提知識 動的計画法更新最適化（累積和） 解説 https://atcoder.jp/contests/agc031/submissions/4597345まず、もともとの数列で同じ色の石が連続していても数え上げには影響が無いので、圧縮しておく。…

https://atcoder.jp/contests/agc031/tasks/agc031_c 解法 https://atcoder.jp/contests/agc031/submissions/4606271！！注意！！もっとスマートな解法があります！！まず、"NO"となるのは、AとBで立っているビット数のパリティが一致しているとき。 まずパ…

https://yukicoder.me/problems/no/798 前提知識 DPテク2「選択するものを最初にソートしておくと、DPできたり、状態を同一化できたりする」 解説 https://yukicoder.me/submissions/323864買うか買わないかという問題なので、ナップサック系DP感があるので…

https://yukicoder.me/problems/no/797 解説 https://yukicoder.me/submissions/323248二項定数を使って解く。 パスカルの三角形っぽかったので、N=4くらいで実験したら、二項定数だったので、それで通した。 a[i]*aCb(N-1,i)の総和を取って答えとする（iは0…

https://yukicoder.me/problems/no/796 解説 https://yukicoder.me/submissions/3232233つの条件を見たときに、一番制約が厳しいのが最後の条件である。 なるべく小さい数の方が良いので、その方向で考える。 全部1にして、1つだけ3にすれば、下2つの制約は…

https://yukicoder.me/problems/no/795 解説 https://yukicoder.me/submissions/323204制約をよく見てみると、M=10Nとある。 つまり、100円玉の総額と、10円玉の総額は等しいことになる。 よって、asdf1君は全部100円で、asdf2君は全部10円で受け取れば同じ…

https://onlinejudge.u-aizu.ac.jp/services/room.html#RitsCamp19Day3/problems/C 前提知識 素因数分解 解説 https://onlinejudge.u-aizu.ac.jp/services/review.html#RitsCamp19Day3/3419470実験しながら考察すると 最小回数は、素因数を1つだけ削った数だ…

https://onlinejudge.u-aizu.ac.jp/services/room.html#RitsCamp19Day3/problems/B 解説 https://onlinejudge.u-aizu.ac.jp/services/review.html#RitsCamp19Day3/3419433貪欲に構築していこう。 )を入れる前に(の数が足りない場合は、その分入れる。 足りて…

https://onlinejudge.u-aizu.ac.jp/services/room.html#RitsCamp19Day3/problems/A 解説 https://onlinejudge.u-aizu.ac.jp/services/review.html#RitsCamp19Day3/3419402尺取法っぽくやっていこう。 順番に見ていって、一緒ならand,orどっちもにも入れて、…

https://onlinejudge.u-aizu.ac.jp/beta/room.html#RitsCamp19Day2/problems/G 前提知識 Grundy数 解説 https://onlinejudge.u-aizu.ac.jp/beta/review.html#RitsCamp19Day2/3419060Grundy数が分からない場合は、そちらを先に勉強しよう。 逆にそれがわかっ…

https://onlinejudge.u-aizu.ac.jp/beta/room.html#RitsCamp19Day2/problems/E 前提知識 ダイクストラ 解説 https://onlinejudge.u-aizu.ac.jp/beta/review.html#RitsCamp19Day2/3419049ダイクストラで解く。 dis[y][x] := (x,y)へ到達するための最小コスト …

https://onlinejudge.u-aizu.ac.jp/beta/room.html#RitsCamp19Day2/problems/C 解説 https://onlinejudge.u-aizu.ac.jp/beta/review.html#RitsCamp19Day2/3419010方針としては、答えとしてあり得る盤面を全列挙する。 盤面は全部で9!通りなので、これは列挙…