POJ-3685 : Matrix

問題概要 N*N(N 解法 「小さい方からM番目がx」は「x以下の個数がM個以上となるような最小のx」と読み替えられるのでこれで二分探索する。で、x以下の個数を効率的に数え上げたい。iを[1..N]で動かし、各行について個数を求める。このとき、iを固定するとjの…

POJ-3293 : Rectilinear polygon

問題概要 2次元格子点上にN( 解法 平面走査する。x座標を動かしながらy座標に点を追加したり、既に追加されていれば削除したりするようにする。この際に単純であるかどうかをチェックするのを忘れないこと。

POJ-3134, AOJ-1271 : Power Calculus

問題概要 今1を持っている。今持っているものから重複ありで二つ選んで(a,bとする)、新たにa+bまたはa-bを得る(ただしa-b>0に限る)。X( 解法 基本アイデアは反復深化。 #include <cstdio> #include <cstring> #include <algorithm> using namespace std; int X; int ANSWER; bool exists[1</algorithm></cstring></cstdio>…

POJ-3532 : Resistance

問題概要 ノード数N( 解法 物理の問題。ノード1の電位を1、ノードN-1の電圧を0に固定する。このとき、各頂点の電位を変数にとると、ノード1と連結なノード2~N-2の間でキルヒホッフの第一法則が成り立つのでこれで連立一次方程式を立てることができる。これを…

POJ-2114 : Boatherds

問題概要 頂点数V( 解法 前処理として重心分解して各重心ごとに部分木の距離を計算しておく。後は各クエリ毎に、部分木の距離配列からしゃくとりっぽくxを探せばよい。

ZOJ Monthly, September 2012 - J : Sleeper's Schedule

問題概要 N(区間がある(区間の座標 解法 dp[t][i] = {時刻tに、i時間連続で起きているときのスコアの最大値} とするとO( (N+MAX_X)*(T+L) )で解ける。

ZOJ Monthly, September 2012 - K : Letty's Math Class

問題概要 単純な文法に従う式が与えられる。評価せよ。 解法 pythonでevalするとオーバーフローも構文解析も気にせずかけてとても良い。

ZOJ Monthly, September 2012

結果。 前回に続いてICPC現役組とチーム参加して7/11完。前回に比べて順位的にはそこそこだったけど、内容的には解ける問題を確実に通しただけ、という気がしなくもない。もちろんそれはとても大事なことなのだけれど。

POJ-3155 : Hard Life

問題概要 無向グラフが与えられる。辺数/頂点数が最大となる部分グラフを求める問題。 解法 fura君に教えてもらった。各辺、頂点に対応する頂点を持つグラフを構成する。このとき、ある辺をとると対応する頂点を必ず選ぶ必要があり、すなわちmaximum closure…

September Cook-Off 2012 COALSCAM : Coal Scam

問題概要 辺が与えられる。辺にはコストとAまたはBの属性がある。全域木をつくって、Bに属するコストを最大化し、そのなかで全コストの和を最小化したい。それぞれの値を求める問題。 解法 ただの最小全域木。

September Cook-Off 2012 RRECIPE : Recipe Reconstruction

問題概要 ?の混じった文字列が与えられる。回文になるように?にアルファベットを埋める方法が何通りあるか求める問題。 解法 対応する2箇所を比べる。

September Cook-Off 2012 CARVANS : Carvans

問題概要 長さN( 解法 前から順に最小値を覚えておく。

September Cook-Off 2012 PPERM : Prime Permutations

問題概要 長さNの置換pがprime permutationであるとは各iについて最初のi個の数字の中でp[i]がX番目(X=1or素数)に小さいようなものを言う。各iについて長さiのprime permutationがいくつあるか求める問題。 解法 p(i)をi以下の素数の個数とする。今、ans[i+1…

September Cook-Off 2012 PTOSS : Pizza Tossing

問題概要 長さN,M( 解法 末尾がn文字一致している状態から必要な個数の期待値をE[n]とする。failure linkを用いて連立一次方程式を立式できる。このとき、各iについてE[i]=P[i]+Q[i]*E[0]とおくことによってE[N]=P[N]+Q[N]*E[0]までDPで計算できる。あとはE[…

September Cook-Off 2012

結果。 4/5完。接続不良でペナルティにほとんど意味が無い。SPOJ使う限りこうなるのは避けられない気がする。

Codeforces Round #140 (Div. 1) D : The table

問題概要 H*W(H,W 解法 行or列の和が負になっているところを見つけてはフリップを繰り返す。フリップの度に全体の和は増加するのでこの手順は高々2*10^6回程度で終了する。ただし最大性についてはまだ理解できていない。そんな直感に反しているわけではない…

Codeforces Round #140 (Div. 1) C : Anniversary

問題概要 フィボナッチ数列の第L~R項までの中から異なるK個を選んでGCDをとる。GCDのとりうる最大値を求める問題。0 解法 まず、gcd(F[i],F[j])=F[gcd(i,j)]が成り立つ。したがって、[L,R]内に倍数をK個以上含むような最大のTについてF[T]が答となる。 [L,R]…

Codeforces Round #140 (Div. 1) B : Naughty Stone Piles

問題概要 山がN( 解法 問題をほどくと、K分木の頂点に番号を降って(深さ*値)の和を最小化する問題だと読み替えられる。こう読み替えるともう解けたも同然で、自明に貪欲が最適となる。

Codeforces Round #140 (Div. 1) A : Flying Saucer Segments

問題概要 N(ハノイの塔で、3つある柱のうち隣接する柱にのみ移動することができる。最小手順を求める問題。 解法 f(n+1) = 3*f(n) + 2なので、これを解いてf(n)=3^n - 1

Codeforces Round #140 (Div. 1)

結果。 2/5完。Bで、「これは間違えようがないだろう」と思っていたのに5WAも出してしまった。これに尽きる。残り時間で取り組んでいたCはAC率の低い難問だった。

POJ-3526, AOJ-1284 : The Teacher’s Side of Math

問題概要 t = a^(1/m) + b^(1/n) (a,bは異なる素数,n*m多項式で、次数最小で最高次の係数が1になるようなものを求める問題。そのような解が存在することが知られている。 解法 問題文にヒントが書いてあって答はn*m次の多項式になると決め打ちして良さげ。最…

POJ-3532, AOJ-1281 : The Morning after Halloween

問題概要 H*W(H,W 解法 ゴールが一つ+遷移が双方向なので両側探索でも解けそうだったけどA*でやった。推定値はそれぞれのゴールへの距離の最大値とする。このときそれぞれが最も対応するゴールに近かったらそのまま終了判定してよい。

JOI Open Contest 2012 : Jumps

問題概要 2次元格子上にN( 解法 x座標でソートしてからx座標最小の1点を中心に角度でソートする。このとき、全てが同一直線上にならんでいるときは解なし。それ以外のときは角度が小さい順に拾っていけばよい。角度が同じ複数の点については距離の遠いところ…

JOI Open Contest 2012

結果。 20+100+28の148点。部分点が細かく付いたコンテストってどの時点で満点解法諦めるか結構迷う。

Codeforces Round #139 (Div. 2) D : Snake

問題概要 H*W(H,W 解法 状態数が少ない(15*15*4^8で抑えられる。頭の位置+前からの差分)のでBFSで間に合う。これで十分なんだけどBBでも解ける。ゴールから各マスへの距離を事前にBFSで計算しておき推定値にする。これだけだとTLEするけど、スネークの頭が他…

Codeforces Round #139 (Div. 2) C : Barcode

問題概要 H*W(H,W 解法 列を全部0or1にするコストを前計算しておく。後は今見ている列と今の列の色と直前の連続する長さを状態にとって簡単なDPに落ちる。W

Codeforces Round #139 (Div. 2) B : Well-known Numbers

問題概要 十分長い0の後に1がある。これから、直前k( 解法 sを作るには貪欲でやってよい。まずsを越えるまで数を列挙し、後は大きいものから選べるだけ選んでいく。また、部分和が2以上でないといけない制約があるのでそのときは0を利用する。

Codeforces Round #139 (Div. 2) A : Dice Tower

問題概要 サイコロ(2種類ある)のタワーがある。見えている2面とてっぺんの面が与えられるので矛盾がないか判定する問題。 解法 てっぺんの数とその7の補数が側面で見えたらダメ。見えている2面の和が7になったらダメ。

Codeforces Round #139 (Div. 2)

結果。 3/5完。最後の一問は仕方がないとして、Cで無駄なWAを出したのはよくない。DのWAは、惜しかったといえば惜しかったのだけど状態数が少ないという事実に気づけなかったのは不味い。しかも最近似たような問題解いたばかりなのに。

Codeforces Round #138 (Div. 1) C : Partial Sums

問題概要 数列Aに対して、f(A)[i] = sum_{j 解法 ひっくり返して考えると上三角Toeplitz行列なので、巡回行列と同じように行列を圧縮して持つことができる。よって積がO(N^2)で計算できるので後はバイナリ法で累乗を計算すればよい。