問題概要 M(区間がある。[0, N)を被覆するのに最小いくつ必要か求める問題。 解法 最初に区間を左端でソートしておいて、dp[i][j] = {iまでで、区間[0, j)を被覆するのに最小いくつ必要か}とするとO(N^2*M)で解ける。 真面目にやればO(N*M)でも解ける。 また…

問題概要 N( 解法 愚直に実装する。

問題概要 長さ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デバッグの時間は減っているんだけどコーディングのスピードは全然速くならない。

問題概要 1次元のオセロで連結な初期状態が与えられるので以後最善を尽くした場合どちらが勝つか判定する問題。 解法 両端が同じになればその色が勝つ。両端が異なれば初手で両端を同じ色にできる先手が勝つ。

問題概要 配列Xがある。Xの要素のうち、[T-E, T+E]に倍数が含まれるようなものがあればそのインデックスを求める問題。 解法 modとかとらなくても倍数全部調べて自明な枝を刈ればよい。

結果。 8完+部分点で8位。無駄なWAはそんなに多くなくてよかった。今年もおもしろい問題が多くてさすがだと思ったし、去年に比べると全体的に難易度は上がっているにも関わらず参加者の正答数は全体的に増えているようで驚いた。 以下コンテストの流れ。 開…

問題概要 H*W(H,W 解法 sum_{i,j} X[i,j] * ( (x-i)^2 + (y-j)^2 ) = sum_{i} ( (sum_{j} X[i,j]) * (x-i)^2) + sum_{j} ( (sum_{i} X[i,j]) * (y-j)^2 )なのでxとyをそれぞれ独立に考えればよい。

問題概要 n*nの行列Aで、A[i,j] = 0 or 1、1のマスは互いに隣接しない、A[i,j] = A[i, n-j+1] = A[n-i+1, j]であるようなものを考える。1の個数がx個あるようなもののうちnが最小のものを答える問題。 解法 偶数だと稼げないので奇数だけ考える。このとき、…

結果。 久しぶりに0完だった。問題読んだのはAとCで、Aは場合分け地獄にハマってしまった。Cは細かいところまで詰めることができずに通すことができなかった。最近はちょっと前に比べてWA率がとても高いのでもう少し細部まで考えるようにしないといけない。