結果。 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で解ける。というの…

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

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

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

問題概要 W*H(黒か黒->白になっているものをいう。 解法 除原理で重複を排除する。 左が白で右が黒で白の個数が行番号について単調非減少であるようなものは簡単にできて、同様のものが4つ計算できる。その部分は簡単なDP。 で、重複を排除する。全部白や全…

問題概要 数列Xがある。一つだけ-1が入っていてそれ以外は非負整数が入っている。今、0がたくさんつまったスタックがある。-1を適当な非負整数に置き換える。数列を先頭から見ていったとき、0ならトップの二つを和で置き換え、それ以外ならその値を直接プッ…

問題概要 W*H( 考えたこと 30か。さすがに半分全列挙はないし5~6乗でもいいよ、ということなんだろう。 最も愚直に(累積和使う程度はやるけど)やるとn^8か。係数小さいとは言えこれは無理。 二つの矩形を選ぶのはもう少し分離したいしできそうだなあ。 どこ…

問題概要 赤、青、緑のボールがそれぞれR,G,B( 考えたこと (少し問題の解釈を間違えてサンプルが合わずに混乱していた) ボールの置き方に自由度がほとんどないことは分かる。 とりあえず1個の三角形を作るのに各色がそれぞれいくつ必要か求めよう。 N^2だか…

結果。 久しぶりに2完。撃墜でも稼げて2度目の5位。撃墜云々は運だとしても、確実に通せるように十分チェックできていたのでよかった。システムテスト待ちの間の安心感が違う。mediumはバグ生みにくい方向で書けたのでよい。easyがちょっと場合分け多めにな…

問題概要 最短路を求める問題。200でよいと思う。

問題概要 文字列Sが与えられる。隣接する文字を高々M回までswapできるとき、連続する同じ文字の長さの最大値を求める問題。 解法 最長なswap後の文字列を考えると、どれか一文字は動いていないと思ってよい。そうでないものも作れるが、固定した場合よりもよ…

結果。 またeasyを落とした。forループの向きが逆という自分にはよくあるミスなんだけど、どうやったら防げるんだ…。ループを見る度に向きを意識するのはちょっとコストが高すぎるし、何かもう脳みそのスタック容量不足とかそういうレベルでダメダメな気分に…

問題概要 サイコロを振ったら出た目の数だけ飴がもらえる。飴をC( 考えたこと DP臭。 まだよく分かっていない。

問題概要 f(X)=A~X~B~X~Cとなる関数Xがある。A,B,C,Xは空でない文字列である。f(X)=S(|S| 解法 どこで分離するかで全探索する。もちろんXの箇所は長さが同じになるように考えるのだけど、定数小さいからO(N^5)ですむし、if文一個付け加えるだけでO(N^4)に落…

問題概要 長さN(B[j]になっている(i,j)の組の個数をn*n/2になるべく近づける問題。 考えたこととか 確率？とはいえ全体の個数が小さいので数え上げ問題に帰着できそう。 既に確定してるのでA[i]>B[j]になっている個数を決めたら、後は0になっているのを調整…

問題概要 正整数列Xが与えられる。Xの各要素を[max(1, X[i]-T), X[i]+T]に含まれる数で置き換えることができる。Xを狭義単調増加にするにはTは最低どれだけあればよいか求める問題。 考えたこととか 見るからに二分探索。 整数の二分探索は最近復習していて…

結果。 INFが小さ過ぎるという頭の悪い理由でmedium落とした。以前からINF=1デバッグの時間は減っているんだけどコーディングのスピードは全然速くならない。

問題概要＝解法 幅優先探索で距離K以下のマスの個数を求める問題。 簡単に感じられたけど、Div 2の正解者はかなり少なかった。

問題概要 H*W(H,W 考えたこと これもオーバーフローに注意しないと…。 何はともあれ区間決めたときの和を計算しよう。左上のマスをX[h,w]、高さA、幅Bとすると、A*B*( (2*h+A-1)*W+(2*w+B-1)) = 2*Sとなる。 これでAやBが2*Sの約数となることが分かるけど、…

問題概要 hypot(w, x-y)の期待値を求める。xは[1,X]から一様に、yは[1,Y]から一様に選ばれる。X,Y 考えたこと とりあえずオーバーフローが撃墜ケースになることは分かる。 何はともあれ全探索だ。xとyを全部回すのはO(X*Y)だし、(x-y)^2もO(X*Y)だから残念な…

結果。 1完のみ。しかも遅い。部屋運に恵まれたおかげで被害は最小限に抑えられたものの、こんな安定感のない戦い方をしているようではいけません。 500は計算量の見積りがダメダメだった。方針はそんなに悪くなかったのだけど…。

問題概要 整数N( 考えたこととか ???桁数少ないし、3^n*nが枝刈り込みで間に合うような気がする。え、250よりはるかに簡単では。 考え直して見るけど、どうやってもこれで行けそうにしか見えない。 もう少し詳しく。3^n*nはn=15で3*10^8くらいだから危ないけ…

問題概要 X[n]は次のように定義される無限の長さの数列である。 X[n][0] = n X[n][i+1] = X[n][i] is even ? X[n][i] / 2 : X[n][i] - 1 数Kが与えられる。Kを含むようなnで、A 考えたこととか こういうのは逆から考えるのが典型。 Kが偶数の時Kの前はK+1か2…

結果。 0完で赤陥落。250は完全に分からなかったので仕方ない向きもあるけど、500はつまらないミスだった。しかし、その詰まらないミスが生まれた＆検出できなかったのは実装の方針が悪かったせい。100行越えてればそりゃミスも出るしデバッグも困難を極める…

問題概要 L*H(L,H 考えたこととか 2000だしO(N^2)かなあ、setとかの重いlogはくっつけないようにしないと。 dpで考えてみるとdp[k段目][x座標][これまでに使った個数]でこれだけでO(N^3)なので無理げ。 dpでなく、線を決めて考えると…？ 傾きの候補はO(N^2)…

問題概要 アルファベットの先頭n( 考えたこととか 辞書順最小の何かを構成する問題なのでいつものパターンで行けるか？ 先頭からみていって、yes/noを返す判定関数を作れさえすれば良い。nが小さいので計算量は無視してよかろう。 えっと、今考えてる文字よ…

結果。 1完でとても悔しい。というのも500で固定長配列使わずにvector使ったせいでMLE(RE)したから。しかしこの失敗の本質は解答仕上げるまで時間書けすぎたせいで見直しする時間がなかったことにあるので、やはり速度が本当に必要な段階に入っているのだろ…