結果。 1完+再提出と結果はよくなかった。でもmediumは面白い問題だと思えたので気分はそんなに悪くない。easyの再提出は配列を[50][1024]でとっていたつもりが[1024][50]になっていたというもの。もったいない。撃墜フェーズでも落ちるの見つけたけど撃墜ケ…

問題概要 n( 解法 ソースコード中に書いたコメントの焼き直し。 minStr[i] = {digits[0:i]の順序を入れ替えて作ることのできる最小の文字} geq[i][j] = {digits[0:i]の順序を入れ替えて作ることのできるlowerBound[j:j+i]以上の文字で最小のもの} ge[i][j] =…

問題概要 50頂点の無向グラフがある。0から始まる単純とは限らないパスをとり、各頂点に設定された値のxorをとった値の最大値を求める問題。値 考えたことなど XOR回廊を思い出すが値が小さい。そういうのを抜きにしても、間違ってもSRMのeasyでそんな深いと…

問題概要 N(>abs(i-j)だけ減少させる。全ての人についてresi[i]を非正になるようにしたい。最小何人を選ぶ必要があるか求める問題。無理なら指摘する。 解法 影響力は500以下なので、左右8までの部分にだけ影響を受けるので2^17のビットDPで解ける。というの…

問題概要 s個のビーズで数珠を作る場合の数を求める問題。色はc色を自由に選べる。s*c 解法 ポリアなどで反転を考えない場合の答を出す。それから左右対称な場合の数以外についてだけ2で割ればよい。左右対称な場合の数を数え上げるのは簡単。

問題概要 サイズM( 解法 末尾の文字を状態にして行列累乗でDPする。

問題概要 長さN( 解法 Aを降順にソートして、BからA[i]+B[j]>=Xなる最小のjを求める。しゃくとりっぽくやってもよいけど、どうせソートでO(N*log N)なので二分探索でよい。

問題概要 長さN( 解法 A,Bの各要素をそれぞれ素因数分解してどちらに分配するか求める。このとき、適当に分配すると長さ10^5以下などを満たさなくなる可能性があるので、元の数列を修正するような形で行う。素因数分解は素数表を作っておいて高速に行う。

問題概要 H*W(H,W i行目とj行目をスワップする。 i列目とj列目をスワップする。 i行j列の要素を出力する。 解法 実際に全ての要素を置換せずにindexの示す先だけをスワップすればよい。

問題概要 長さN( k番目の要素を末尾に追加する。 先頭の要素を消す。 を何回繰り返したら全てが同じ要素になるか求める問題。同じにならないなら指摘する。 解法 dequeを使ってシミュレーションする。収束するとしたら高々Nくらいなのでその程度回して無理な…

結果。 5/5完。全体的に易しめなセットだった。

問題概要 maximum closure problemの最適解と、それを達成するために必要な最小頂点数を求める問題。 解法 よく知られているように、最小カットでsource側に分離される頂点が答。最小性の証明についてはよく理解できていない。

問題概要 色々書いてあるけど、要するにヒストグラムの中の最大長方形を求める問題。 解法 All nearest smaller valuesの応用。

初項1、公比r、項数nの等比級数1+r+r^2+...+r^(n-1)を効率的に求めたい。 何も工夫せずにやると def f(r,n): ans = 0 b = 1 for i in xrange(n): ans += b b *= r return ans でO(n)となる。 よく知られている公式を用いると次のようにも書ける。 def f(r,n)…

問題概要 n( 解法 コインの価値が高い順にCを越えないよう貪欲に詰めていく。次に、価値が低い順にCをぎりぎり越えるように貪欲に詰めていけばよい。うまく行く理由としては、まず前半の価値が高い順に越えないよう貪欲に詰めるのは倍数列の制約から明らかと…

問題概要 4*n+1で表される数をH-numberという。1*hでしか表せないH-numberをH-prime numberという。二つのH-prime numberの積で表されるH-numberをH-semi-prime numberという。[1..k](k 解法 篩をかける。計算量が読みにくいけどやってみると余裕で間に合う。

問題概要 長さN( 解法 xorとってbitcountが1なら辺を張る。後は二部マッチングの分だけ減らすことができる。

問題概要 正整数n(区間[l,r]を全て列挙する問題。 解法 しゃくとり法。

問題概要 数字からなる部分列が与えられる。長さ1~4の部分列でdigit rootが9になるものの個数を求める問題。 解法 digit rootが9となることは各桁の和が9の倍数かつ0でないことと同値。なので、長さと和を9で割った余りを状態としてDPすればO(N*5*9)位で求め…

問題概要 長さNの配列がある。最初はX[i]=iである。区間に定数を足し込む操作を繰り返した後、最大値と最小値の差を出力する問題。 解法 いもす法で処理できるけど、真面目にやるとTLEする。なので適当に座標圧縮する。

問題概要 数列Xがある。数列を置換してY[i]=max(X[i+1],X[i])の和が最小になるようにしたい。そのような置換のうち辞書順最小のものを求める問題。 考えたこととか (やたら早い提出者がたくさんいるのを確認した上でオープン) 辞書順最小というと例の方法だ…

問題概要 赤のブロックと青のブロックがそれぞれいくつかある。それぞれ高さが決まっている。ブロックを積み上げるときは異なる色のブロックを交互に積まなければならない。異なる高さの塔が何種類作れるか求める問題。 考えたこととか (問題誤読したまま書…

結果。 1完。medium割と典型解法が使える問題だったんだけど、ちょっと考えて無理そうだと思って棄却してしまった。全然無理じゃなかった。 撃墜時は間違った考えのまま正しい解法に突撃しまくっていた。 順位に関してはやっぱり1完だと早解きで勝てるわけが…

問題概要 H*W(H,W 解法 各マスについて列の状態を保持しながらビットdpする。 時間 30分かかった。遅い。入力の0と1を間違えてしかも2回も間違えた。入力読み込んだ時点で自分に分かりやすいようフリップしとくべきだった。