問題概要 01の値が入ったボード(H,W 解法 何はともあれ累積和を計算しておく。上端、下端、左端について全探索する。右端についても全探索したらさすがにTLEするので、右端については単調性を利用して二分探索すれば間に合う。上端と下端を全探索して左端と…

問題概要 N*N(N 解法 縦、横、斜め*2について独立に考える。例えば縦での衝突を考えるとき、列の違うクイーンはまったく関与しない。同じ列のクイーンを集めてソートしてやると、端のクイーンだけは1つのクイーンの範囲に含まれ、それ以外は2つのクイーンに…

問題概要 ノード数V( 解法 頂点を潰した後は木になるので距離は簡単に求められる。問題は環を潰す部分。次数1の頂点を見つけて減らしていけば残ったのが環になる。

問題概要 男がN(4 解法 もちろん男が何人選ばれるか全通り試せば(前処理を除いて)O(N)で解けるんだけど、なぜか本番中は別の解き方で解いた。選んだ男どもと女どもをそれぞれ番号でソートする。4人目の男と1人目の女がだれになるかを全通り試す。

問題概要 配列X(|X|=:N 解法 X[i]の値の分布を調べておくだけ。0は例外処理する。

問題概要 文字列が与えられる。全てが大文字、または先頭以外の全てが大文字なら大文字と小文字を入れ替えて出力する。 解法 愚直にチェックしても間に合う。1文字目は無視してよいことに気づけばちょっとだけコーディング量が減る。入力が1文字で小文字のと…

結果。 どの問題も方針は見えやすかったと思う。実装や読解に時間をとられはしたけどこれはまあ仕方がない。残り時間ギリギリで6問目を通したけど計算量が結構きわどかった。残り時間がもっと余裕あればカスタムテストで最大ケース試す所だけど。5問目は色々…