C-largeはソートされたリストに対してi番目の要素の検索と要素の削除が効率的に行えるデータ構造があればよい、一般的には赤黒木などの平衡二分木が必要になるんだけど今回の問題は挿入を考えなくてよいので単に子要素がどれだけあるかを保存した二分木をつ…

199位でRound 2に通過。 A 格子点上の点がn個与えられた時に重心が格子点にのるような異なる3点の取り方の数を出せという問題。とりあえずsmallに関してO(n^3)のコードを書いて通しておく。よくよく考えるとx,yに関しての3で割った余りのみ見ればいいことが…

通過の正式通知が来た、Round 1の時間に関しては最初は7/25-31まで選択肢があったが、集計の結果偏りがあったのか、土曜日の10:00と25:00、日曜の18:00の三つの中から二つの時間を選ぶことになっていた。各ラウンド上位840名がRound 2に進出できる。あと各ラ…

Rateが1969->2000で2000点台に 250 連結している部分はすべて完全グラフに直して、頂点が一個の部分に関しては最大連結成分のところに合わせればよい。 500 開始アドレスの候補となる位置は与えられるアドレスの部分かk個前で、高々100個程度なので100^3のDP…

3問中3問解いて、すべて通った。1問解けば通過なので何事もなければRound 1に進める。スコアボードをみると7000人弱が通過している、つぎのRound 1からRound 2には2520人進める。追記：各問題のプログラムを貼っておく A 次にでてくるのが一番遅いクエリを常…

Kleinberg and Tardos のAlgorithm Designが日本語版で出ている。価格は15000円。英語版もそれくらいするのでこれから買おうと思ってた方はこっちをかってもよいかも。

250 本質的には先頭からできるだけ重ねて連結するだけ、ただし連結するときにx_i 600 要約するとn,m 900 正解しているひとのコードを見ると非常にわかりやすい。要は一回の試行時にあるマスが塗られる確率がpならばK回の試行で塗られる確率は1-(1-p)^Kなので…

昨日、自分の数理輪講の発表が終わってひと段落したので一週間ほど実家に帰ります。

Javaの幾何ライブラリを使って解いてみた。多角形と線分の距離をもとめるというそのままの関数はなかったので自分で一から書くのに比べて、そんなには楽にならなかった。 import java.awt.geom.Line2D; import java.awt.geom.Point2D; import java.awt.geom.…

今年は観戦側。東大内のボーダーが6問になっていてびっくりしました。問題を見た感じだと今回はすべての問題ができるように作ってあったので6問解くチームはでるかなとは思っていたけど3チームもでるとは。 各問題に関する感想(A,Bはちゃんと読んでないので…

250 毎回ソートして、高さが高いものから使っていく。 500 ターゲットの点をルートとした木を考えたときに、リーフ以外の点に飴がk個置かれているという状態がokならばその点の飴を全部除いて、子供に2k+1個置いた状態もokなのでなるべく深い部分に飴が集中…