考えたこと どんなマスなら白から黒に変えられるか考える そのマスの右と下にkマスずつ余裕があれば白から黒にできる 各方向からn-k列は何であっても実現できそうなので残りのk列が実現できるか判定できればよさそう n-k列の方が埋まってたらk列の方が黒く塗…

問題ページ D: Driving on a Tree - square869120Contest #4 | AtCoder 全方位木DPに慣れるために解いた 考えたこと 頂点vからどこかの子に移動したら他の頂点vの子には絶対に到達しない d[i] = iを根とする部分木でiからスタートしたときの動く回数の期待値…

問題ページ E: 限界集落 - NJPC2017 | AtCoder うしさんのブログを見て前半2問で全方位木DPを学んだので解説を見ずに解いた 考えたこと 各頂点から最も遠い頂点までの距離を求めて全てDより大きければ到達不可能なので-1 d[i] = 頂点iを根とする部分木で頂点…

問題ページ Problem - D - Codeforces 考えたこと ax2+bx+c を x+k で割るみたいなので何個か実験すると何か規則がありそう コンテスト中はこの計算をミスってて別の規則を生み出してた（は？） 終わったあとに冷静になって計算すると a_1 + a_2x + a_3x^2 +…

問題ページ Problem - C - Codeforces 考えたこと 非減少列の判定が連続でなくてもいいことに気付かずに時間を溶かす 反転するのは1→2に移るところ～2→1に移るところ以外考えなくてよさそう [0,l) [l,r] (r,n-1] に分けると[l,r]に1から2に移るところがある…

問題ページ Problem - B - Codeforces 考えたこと loopが2個の8を18個並べた36個が上限に見える ループが2個の8とループが1個の4,6,9あたりを使って適当に並べればよさそう leading zeroにだけ気をつけて出すと通る AよりBの方が簡単ですが… #include <bits/stdc++.h> using</bits/stdc++.h>…

問題ページ Problem - A - Codeforces 考えたこと ソートして大きい方と小さい方だけ考えればよさそうな気がしたので投げるとpretest通る 順位表を見てると+10とかしてる人がいたので見返すとだめなパターンがある 場合分け面倒そうなのでO(nm)の全探索を書…

問題ページ Tiles are Colorful | Aizu Online Judge 考えたこと Aを消すために消さないといけない色から有向辺を貼ってトポソを考える 2パターンあるのをトポソでわけて判断するの無理そう 各色のタイルの位置を求めておいて消せるタイルを消すを繰り返せば…

考えたこと 部分文字列[l,r]が同じ文字になる確率を考える ?がなくて全部同じ文字→1 違う文字が混ざっている→0 ?がm個で他が全部同じ文字c→(cの確率)^m 全部?でm個→sum(p[i]^m) よくよく考えると各部分文字列について独立っぽい 全ての部分文字列について確…

考えたこと dp[i] = (i番目までで終わるパターン数) dp[i] = sum(dp[j]) (j<i, (j, i]が全員同じ国の条件を満たす) みたいな遷移をすればよさそう (j, i]が条件を満たすのは質問に答えた人がいない or 質問に答えた人が全員同じ人数でi-jと等しいとき dp[n-1] = 1 なら確定できるのでsufficient DP遷移で頭爆発して実装に手間取った、むずかしい #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<int> VI; type…</int></i,>

考えたこと 巡回置換を何回やったら1に戻ってくるか 長さNのとき周期1,2,…,Nで1にループする したがってxはlcm(1,2,…,N)になる x*y/gcd(x,y)を使ってlcmを求めようとするとMODでうまくいかない 1~Nを素因数分解してそれぞれの素因数について出現数のmaxを数…

考えたこと Sと同じ列、行のどこかに一つでも'#'があればそこに向かって永遠に動けばいいので-1 これ以外のときは最初の位置から進み続けて落ちないぎりぎりの回数各方向に移動するのが上限になるはず この移動方法で途中で落ちるような部分列はありえない #…

考えたこと 両端が同じ文字で間が偶数、両端が違う文字で間が奇数ならちゃんと埋めれば0にできて1パターンしかない これ以外の場合どうやっても+1は回避できない +1になるパターン数を求めて掛けていけばよさそう 実験したら(間の数+1)パターンになった MOD…

考えたこと 部分文字列を全列挙しようかと思ったけど制約的に不可能 部分文字列で共通なものを探せるとよさそう ---oo--oo-- (ooが共通) みたいな文字列があったら共通な部分文字列では7文字が最長 ロリハとか使って共通部分を探すのかと思ったけど愚直でも…

考えたこと AtCoder Expressを思い出す x[i-1] から x[i] までの区間についてどこまで上げられるのかみたいなのを考える よくよく考えると前後それぞれから見ていけばいいだけ dp1[i] = (i以前の条件を満たす最大の高さ), dp2[i] = (i以後の条件を満たす最大…

問題ページ CS Academy 考えたこと 問題文の不等式を満たす範囲が何なのか (R,C)を左上で幅がLの下三角行列みたいな範囲になる クエリ先読みすると意味のあるクエリが少ないみたいなO(Q)の方をどうにかする改善ができるようには見えない 範囲加算の処理をO(L…

問題ページ CS Academy 概要 2次元座標上のN点(x, y)が与えられる。各点について3点(x,y)(0,0)(x,0)を結んでできる三角形の内部に他のN-1点のうち何個が含まれているか求めろ 2 <= N <= 10^5 1 <= x,y <= 10^5 xは全て異なる 原点と(x,y)を結んだ線上に他の…

問題ページ CS Academy 概要 0<=x<=N, 0<=y<=M の範囲の2次元座標で2点選んだ時の線分が通る格子点がちょうどK点となるような2点の組み合わせは何個あるか求めろ 1 <= N,M <= 50 1 < K <= 50 考えたこと 何か誤読してて20分くらい溶かす 気づくと2点全列挙で…

考えたこと ソートしていい 全ての区間[l,l+k-1]についてi番目に合わせて連続するk個の列にするのにかかる操作量を計算 全部愚直にやってもO(nk^2)で余裕 #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<int> VI; typedef vector<VI> VVI; typ</vi></int></bits/stdc++.h>…

区間[l,r]がいっぱいとんできて条件を満たすように区間を選ぶときの数の最大(最小)を求めるみたいなやつ とりあえず終点でソート 区間スケジューリング問題 Spaghetti Source - 区間スケジューリング 終点が早い区間から選んでいくのが最適解になることを示…

考えたこと 区間i,jが被っていれば頂点iと頂点jに辺を張ったグラフを考える グラフの任意の頂点について含まれているか集合のいずれかの頂点と隣り合っているような頂点集合Sが全員をカバーできるような配置になる この頂点集合のうち要素数が最小のものを構…

考えたこと ソートしてよさそう lを買う中で最も小さいお好み焼きとすると買える最大のお好み焼きのindexは単調性がある [l, r) を尺取みたいな感じでもとめていく 区間の要素数からその区間で買うときのパターン数は求まる lは必ず買うものとしてr-l-1要素…

問題ページ A - アナログ時計 考えたこと 重なるタイミングがどんなときかとりあえず列挙する 分針と秒針はxx:00:00、xx:01:01とxx:01:02の間、xx:02:02とxx:02:03の間… 時針と分針は00:00:00、01:05:00あたり… 時針と分針は明らかに面倒なのでコードを書い…

問題ページ E - Antennas on Tree 考えたこと 次数が大きい頂点にアンテナを置いても同じ距離の頂点が大量にできるだけなので次数が小さい頂点に置いた方がよさそう 次数が大きいウニみたいなグラフがあったときどうするか考える ウニの中央の頂点に置くのは…

問題ページ D - Forest 考えたこと グラフのつながれている形によってある頂点が使えなくなるといったことはないので形は関係なさそう 各連結成分についてa[i]の集合として考えられそう vectorをマージしていく感じに思えたのでマージテクを調べ始める 小さ…

問題ページ C - Vacant Seat 考えたこと 頂点数が奇数で円環状になっているグラフが2部グラフなわけはないので空席があるのはそれはそう クエリ回数が20回なのでlogオーダーの計算量しかありえなさそう 空席が絶対にある範囲をもって二分探索っぽいことをす…

問題ページ B - Two Arrays 考えたこと 考えるのはa[i]とb[i]の差だけでよい a[i] < b[i] だとすれば a[i]+2, b[i]+1とすれば差が1縮まるので周りの状況にかかわらず絶対に等しく出来る a[i] > b[i] のときは a[j]+2, b[i]+1 (a[j] < b[j]) とする必要がある…

考えたこと 素因数分解は試し割りでO(sqrt(N))なので愚直にやるのは間に合わない ヒントとして与えられた素因数でNを割っておいていい primes[i] = primes[i+1] ならば間に入る素因数はprime[i]で確定 O(primes[i+1]-primes[i])かけて全て試せば間に入る素因…

考えたこと 期待値と言われたので線形性を考えるとn回バスが到着するまでの時間の期待値は求まる気持ちになる 何回目のバスに乗ることになるかがわからないので上のが求まったとしてもよくわからない気がする i回目のバスでsに達しておらずi+1回目のバスでs…

問題ページ G - Coinage 考えたこと どちらか優先すべき文字列を連続して置いたあともう一方を連続して置くべきっぽいので優先すべき文字列を決定する sとtのうち辞書順で小さい方をできるだけ並べたあと残りを埋めればいい気持ちになって出すとWA s="bb", t…