問題概要 1~nの和の平均値からm in [1..n]を引いた数をX/Yとする。n,mの組として考えられるものをすべて列挙する。なければ指摘。 解法 式変形すると、n * ( (n+1)/2 - X/Y ) = m となる。1

問題概要 平面上にN個の点があり、dist(p[i], p[i+1])が分かっている。dist(p[0], p[N-1])のとりうる最小値と最大値を求める問題。 解法 最大値は自明に和。最小値は存在しても必ず整数でもっとも長い辺をキャンセルするように作れば良い。

問題概要 最遠点対。 解法 O(N^2)で全探索間に合う。ちなみに凸包作ってキャリパー法でO(N*log N)。

結果。 3/4完。何がひどいって言語のバグで解けなかったのが辛い。D言語を諦めて安心と信頼のpythonで書き直したら通ったけど、残り時間がほとんどなくてD問題は諦めた。ちょっと見たときは、集合としての個数を数えるのだと思って難しそうだと思ってたけど…

問題概要 N( 解法 許容誤差が小さいのでモンテカルロでよい。許容誤差の2乗*定数回程度回せば失敗確率は十分小さくなるらしい。

問題概要 W*H(W,Hボトルネックを最大化する問題。 解法 答について二分探索する。こうすると、各マスにある時刻で入れるかどうかが簡単に判定できる。なお、答は十分小さい値をとりうるので、low=0.0なら到達不能、とすると間違える。

問題概要 文字を逆さにしたときの辞書式順序でソートする問題。

問題概要 数列の平均値を出力する問題。

結果。 D言語でやるかー、と思ってAやっていたら何故か合わずにあせった。A~EでなくA,B,C,D,Fになっていて、はーそーなんですかと思いつつ修正してAC。 Bは反転するだけだと思って実装するとコンパイルエラー。std.algorithmのreverseは返り値がvoidなのでre…

問題概要 コマンド列を短くする最適の置換を求める問題。 解法 割り当てを全通り試してDP。貪欲にやっても良いので適当にreplaceしてlength調べるだけでも多分大丈夫なはず。

問題概要 指定された日以降で、年が(月*日)で割りきれる最初の日付を求める問題。 解法 一日ずつ進める。1日でダメだったら次の月に行くとか、年をまたいだら無条件でOKとかいろいろあるけど、どうせ間に合うのだから余計なことはせず愚直にやってOK。

問題概要 うるう年かどうかの判定をする。 解法 DFA。

結果。 3/4完。D言語で連想配列の初期化がなぜかうまくいかなかった。あとDDTが^^使ったときにエラーだと怒ってきたりして困った。さらに提出してみたらコンパイルエラーで、エラーの詳細が見れずに絶望的な気分になった。clar出したら10分くらいで対応して…

問題概要 (sx,0)から(gx,N) (N 解法 愚直に可視グラフ作ってからDPするのはO(N^3)。少し工夫を加えるとO(N^2)まではすぐに落ちる。 想定解っぽいのは適宜メモ化しながら下から順に計算するらしい。 自分は左側と右側の壁で交互に凸包つくって、凸包の頂点は…

問題概要 一部が埋められた8クイーンがあるので残りを埋めて出力する問題。 解法 5!+枝刈りとかでもよいのだけど、以前書いたN-Queenソルバ(全生成)があるのでそれを使って8-Queenの盤面全部出して与えられたのと合致するかだけ調べた。

問題概要 幅優先探索で距離を求める問題。

問題概要 数字の列が与えられるので、出現回数の最大値と最小値を出力する。