問題概要 テンプレートを用いて複数のオーバーロードされた関数があるので、関数を実際に呼び出すとき何通りインスタンス化される可能性があるか求める問題。 解法 mapでがりがり実装する。

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

問題概要 サッカーのグループリーグを抜けるのに要求されるスコアを求める問題。 解法 これまでの結果から得点に大差はつかないことが分かっているので、スコアについて適当な範囲で全探索する。基本的には実装ゲー。

問題概要 平均値を求める問題。

問題概要 原点のまわりを衛星が角速度Vp/rで等速円運動している。ロケットと衛星の初期位置が与えられる。ロケットは速度V(>Vp)で移動できる。原点から半径R以内に入らないようにして衛星までたどり着くには最小どれだけの時間が必要か求める問題。 解法 V>V…

問題概要 高さn( 解法 幅優先探索するだけでよい。

問題概要 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は計算量の見積りがダメダメだった。方針はそんなに悪くなかったのだけど…。

これまではJavaScriptとかでやってたけどRの方が綺麗なのでRで書くことにした。とりあえず、手動で手を加えやすくしたいので中間ファイルを噛ませることにする。プログラム中で次のようなファイルを吐く。 TEXT -10 0 S POINT 5.7924 8.15157 COLOR BLUE CIR…

問題概要 N*M(N,M 解法 各(x, y)について、それより左側にある最小の空きマスと、それより右側にある最小の空きマスを計算しておく。各クエリに対しては、xについて全探索すれば計算量O(K*M)で目的地を見つけられる。また、データの更新は目的地のx座標を持…

結果。 3/5完。難しめの問題に挑んでいたけどなぜかTLEがかなり厳しい問題で落ちた。結果やさしい問題解くのが遅れて順位はひどかった。

問題概要 H*W(H 解法 男の数、女の数、値、負の値の個数について累積和を計算しておく。そうすると矩形を決定すればO(1)で判定できて嬉しい。後はyhighとylowを全探索してx方向にしゃくとりすれば全体の計算量O(H^2*W)で間に合う。

問題概要 ノード数V( 解法 まずWFしておく。その後はビットDP。 dp[v][bit] = {これまでに尋ねたノードがbitで今いるのがvであるような最小の時刻} を全部計算して最後にdp[goal][bit]

問題概要 s!をK進数で書いたとき末尾に0がいくつあるか求める問題。s 解法 Kを素因数分解してその素因数がs!にいくつ含まれるか求める。例えばK=8のときなんかは2でs!がいくつ割りきれるか求め、それを3で割ったものが0の個数になる。K=24とかだったらそれと…

結果。 uwiさんとshindanninさんでチーム参加して6位。自分は比較的易しめな問題を3問通したけど、ちょっとWAが多いのと、最後に難しめの問題を通せなかったのが反省点。

問題概要 f(x)=k*x+b(1≦k, b 解法 fが狭義単調増加であることから、f^n(1)≦f^a(t)はf^(n-a)(1)≦tと同値。したがってf^(n-a)(1)≦tを満たす最大のn-aを求めればよい。ただしaは非負。

結果。 2/5完。いつものことながら、正確に実装しきれない。AはHackされたおかげでミスに気付いたけどこれはかなり必然的なミスだった。こういうの落とすのは良くない。

問題概要 方程式 A + B*x = C (mod 2^k)を満たす最小のxを求める問題。解がなければ指摘する。

問題概要 10*10マスの中にカエルがいる。カエルは周囲のある12箇所に移動できる。訪ねるべき3*3の範囲がいくつか与えられるので、それをすべて順番に訪ねることができるか判定する問題。 解法 簡単なDP。

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

問題概要 2次元グリッドの格子点上に点がいくつかある。4点選んで軸に平行な長方形をつくり、内部に点がないようにしたい。面積の最大値を求める問題。 解法 長方形の2点の選び方を全探索する。内部に点があるかどうかは累積和を計算しておけばO(1)で判定で…

問題概要 重み付き無向グラフで2点間の最短路を求める。ただし最短路は4か7の倍数でなければならない。 解法 (ノード、今の時刻%28)を組にしてDijkstraする。

問題概要 パスカルの三角形を下っていくときの経路上の和の最大値を求める問題。 解法 DP。同じ問題がPOJなどいろんなところにある。

問題概要 平面上に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( 考えたこととか ???桁数少ないし、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行越えてればそりゃミスも出るしデバッグも困難を極める…