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

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

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

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

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

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

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

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

問題概要 長さ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[…

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

問題概要 文字列S,T(長さ 解法 Sの各文字について、その文字は部分列Tのk番目になれる、の最大のkを計算しておく。ついでに、後ろから見たものも計算しておく。後は前から見たときと後ろから見たときでその文字を含む部分列=Tが存在するかどうかが判定できる…

問題概要 丸括弧と角括弧の列(L 解法 丸括弧と角括弧をそれぞれスタックに積んでいく。途中で括弧が足りなくなったり、対応してないものに当たったりしたら全部クリアすればよい。

結果。 遅い1完でひどい出来な回だった。しかし普通に実力不足な気もする。Cの方が簡単だったにも関わらず読まずにBに飛び込んだのも問題だった。とはいえ結局は実力不足。

問題概要 頂点数V( 解法 最初は最大流だから全域最小カットだとおもったけど違う。メンガーの定理より、求めるものは最小点カットが3以上かどうかだが、普段使っている最小カットは最小辺カットで、これは最小点カットではない。最小点カットが2以上であるか…

問題概要 15パズル風に空きマスに数字を移動させるゲームがある(ルールの詳細は略)。クリアできるのであれば最短手数を求める。無理なら指摘する。 解法 幅優先探索で間に合うらしい。状態の合流があるとはいえ意外。 以下の自分の実装では盤面をcharで圧縮…