問題概要 長さL(スワップして回文になるようにしたい。必要なスワップの最小回数を求める問題。回文にできないのであれば指摘する。 解法 奇数回現れる文字が2個以上あれば不可。それ以外のときは、以下のような手順で最小コストの回文が得られる(未証明)。 …

問題概要 [1..K](K 解法 個数制限なしナップサックと同様にやればよい。最大ケースでは64bitでも足りないので多倍長が必要。

問題概要 パスカルの三角形風に数字が並んでいる。上から斜め下のどれかに移動できる。途中で拾った数の和を最大化する問題。 解法 典型的な動的計画法。色んな所で類題が出題されている。

問題概要 [0..9]の部分集合が与えられる。二つの集合に分けて適当に順序を変えて10進数の数字を作り差を最小化する問題。 解法 数が少ないので全探索が間に合う。桁数決め打ちで分けてnext_permutationくらいでも余裕。

問題概要 [1..N](N 解法 next_permutationで意外と早く見つかる。

問題概要 連結グラフが与えられる。ある点を中心とした距離の近いほうN個の平均長の最小値を求める問題。 解法 真面目に幅優先で求めて十分間に合う。

問題概要 n( 解法 平均値について二分探索する。

問題概要 N( 解法 大きい数にf(x)=sqrt(2*x)をたくさん作用させられるようにするため大きい方から貪欲に選べばよい。

問題概要 n( 解法 見るからに二分探索+2SAT風。

問題概要 N( 解法 平面走査でやるのはすぐに見えるけど、簡潔な実装方法を選べないと厳しい。Range Sum Queryで区間に足し込み、新たに線分を加えるときオーバーラップしているかどうか判定する方法でやった。走査線を左右、上下の4方向に動かせば全部検出で…

問題概要 頂点数n( 解法 既に通った頂点集合と今いる頂点を組にしてDPすればよい。ただし、適切なトポロジカル順序をつけるのが難しいのでベルマンフォードのように適当にn回回して緩和する。

問題概要 n( 解法 約数の個数については前処理で篩っぽく計算できる。どの子が取り除かれるかについてはBITで計算する(割と典型手法)。

問題概要 盤面サイズ250のライツアウトを解いて最短かつ辞書順最小の解を出現する。 解法 連立一次方程式。最短かつ辞書順最小が難しいが、問題文をよく読むとランク落ちしないと書いてあるので最小も何もなく解は一意に定まる。

問題概要 A,G,C,Tからなる長さL[i]( 解法 ICPC Asia Regionalなどでお馴染みのShortest Super String。他の文字列に包含される文字列を消去した上で巡回セールスマンっぽいのを解けばよい。面倒なのは辞書順最小の構成だけど、これは例によって前から順番に…

問題概要 頑張って問題文を読むと、奇数個の部分和になりうるかつ偶数個の部分和になり得ない値の個数を求める問題だと解釈できないこともない。 解法 計算量O(N*M)だけど定数が軽いのと多分テストケースが弱いのとで普通にDPやって通る。

問題概要 2次元ボード[0,2^31)*[0,2^31)がある。その内N( 解法 平面走査する。イベントラインは区間への加算をサポートするRMQで持っておけばよい。つまり、点(x,y)を追加するとき[y,y+H)に書かれている数値を足し込む。削除する時は負の値を足し込めばよい…

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

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

問題概要 今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>…

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

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

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

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

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

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

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

問題概要 s個のビーズで数珠を作る場合の数を求める問題。色はc色を自由に選べる。s*c 解法 ポリアなどで反転を考えない場合の答を出す。それから左右対称な場合の数以外についてだけ2で割ればよい。左右対称な場合の数を数え上げるのは簡単。

問題概要 maximum closure problemの最適解と、それを達成するために必要な最小頂点数を求める問題。 解法 よく知られているように、最小カットでsource側に分離される頂点が答。最小性の証明についてはよく理解できていない。

問題概要 色々書いてあるけど、要するにヒストグラムの中の最大長方形を求める問題。 解法 All nearest smaller valuesの応用。

問題概要 n( 解法 コインの価値が高い順にCを越えないよう貪欲に詰めていく。次に、価値が低い順にCをぎりぎり越えるように貪欲に詰めていけばよい。うまく行く理由としては、まず前半の価値が高い順に越えないよう貪欲に詰めるのは倍数列の制約から明らかと…