Codechef Cook 101 Editorial
Codechef Cook 101 で自分が解いた部分までの解説です (Div2 の4問目、Div1の3問目まで)。
各問題にはテストケース数 の制約があるけど省略しています。
Camp Or Not
概要
競プロキャンプに向けて問題を解く。 問題を解くスケジュールは 日決まっていて、 日目に 問を解く予定である ()。
キャンプの選抜方法の候補は 個あり、各候補には締め切り と 必要問題数 が与えられている。 日目を含むその日までに 問以上解いていれば、キャンプに行くことができる。
スケジュール通りしたときに、各候補日についてキャンプに行けるかどうかを判定せよ。
解法
制約が小さいので愚直にやってもよいし、累積和を計算してもよい。
提出コード : Solution: 25750755 | CodeChef
Yalalovichik Numbers
概要
10進数で桁数が の数 が与えられる (, の各桁は0でない)。 この数を 回左に回した数を とする (例えば のとき、)。
このとき の順で結合した数を で割った余りを求めよ ( なら 123231312 が答え)。
解法
答えは
となる。10のベキの方は簡単に計算できるため が分かれば良い。
まず はそのまま計算できる。 次に については、 の先頭の桁を とすると という関係が成り立つので、 さえ分かれば と順に求めることができる。
今、 を順番に左に回しているので は の 桁目である。 は文字列として与えられているので はすぐに求められる。
提出コード : Solution: 25751450 | CodeChef
Yalalovichik Strings
概要
文字列 のすべての部分文字列(連続)の集合と のすべての部分列(連続とは限らない)の集合が一致するとき、 文字列 は Yalalovichik string であるという。
長さ の文字列 が与えられる ()。 の空でない部分文字列のうち Yalalovichik string であるものの個数を求めよ。
解法
どのような文字列が Yalalovichik string になるかを考える (以降、省略してY文字列と呼ぶ)。
まず1種類の文字が続く場合 (aaaaaa など) は明らかにY文字列になる。
そして文字列が2種類の連からなるとき (aaaabb など) もY文字列になる
(どのように部分列をとっても a*b*
の形になるため)。
逆に文字列が3種類以上の連からなるときはY文字列になることができない。 が と3つ以上の連からできているとする。 このとき部分列として を選ぶと、これは からどのように部分文字列を 選んでも一致させることができないからである。
このことからの部分文字列のうち
- aaa... のように1種類の文字からなる文字列
- a...ab...b のように2種類の連からなる文字列
のどちらかの形をした部分文字列の総数が答えになる。 重複を考慮して数えなければならないが、1 と 2 は独立に考えることができる。
(1) はアルファベット ごとに 中の の最長の長さ をもっておけば、 その総数は になる。
(2) は2種類のアルファベット とそれぞれの長さだけが重要になる。 そのためすべてのアルファベットの対ごとに、 中で取りうるすべての長さの組の集合 を計算する。 例えば aaabb と aabbb の2種類の部分文字列が に現れるとき、 となる。
を をこの順に少なくとも1つずつ使って作れる文字列の個数としよう。 上の例だと になる。
基本的には各 について の和を取ればよいが、これだと 重複を数えてしまうことがある (上の例だと ab, abb, aab, aabb の4種類)。 この問題は2次元平面上に点 がいくつか与えられ、各点ごとに点と原点を隅に持つ長方形を 描いたときの面積の総和を求めることと等価である。 これはそれぞれの点 をx座標でソートして、x座標が小さい方から順に点を見ていくことで計算できる。
異なる は独立に計算できるため、求める総数は である。
計算量はソートの部分が一番重くて である (アルファベットの個数は定数個なので)。
実装は を最初にランレングス符号化しておくと簡単になる (気がする)。
提出コード : Solution: 25753643 | CodeChef
Swag Subsets
概要
長さ の数列 と が与えられる。
集合 の空でない部分集合 について、その swagness を以下のように定める。
このとき をで割った余りを求めよ。
解法
簡単のために はすべて相異なるとする。
まず B を無視した問題 の総和を求めることを考える。 数列 の順序に意味はないのでソートして と仮定してもよい。
このとき となる は 個ある ( を取ればそれ以外は取っても取らなくても良いので)。 同様に となる のとり方は 通りある ( は取らず は取る、それ以外はどちらでもよい)。
これは となるまで同じように考えることができるので、答えは
である。
もとの問題も今の考え方と同じようにする。 まず のペアを をキーでソートして にする。 についてはソートされているとは限らない。
また、 の値だけでソートした列を とする。
となる のとり方は、 を取りそれ以外はどちらでもよいので 通りある。 また をすでに選んでいるので が成り立つ。 それらのうち
で場合分けする。
また を
となる数とする。
ある集合 について(1) が成り立つ条件は よりも右側にある数に対応する添字を取るときである。 を より右にあるものとして、 となる場合を考える。 これは より右にあるものは取らず、 (とすでに選んでいる )を選び、それ以外はどちらでもよい取り方になるので、 の選び方は 通りある。
つまり任意の について となる の取り方は 通りある。 よって (1)の場合の求める数は である。
(2) が起きるのは より右側はすべて取らず、左側はどちらでもよい取り方になるので、 通りある。よって求める数は となる。
以上から となるときの答えは (1), (2) を合わせて
である。
次に となる場合を計算したい。 これは の列から を削除してから、同じ方法で計算することができる。
以上より の計算方法は分かった。あとはこれを高速に計算できるように実装する必要がある。 数列 に対して、上で必要になる操作は
- 与えられた区間 について を求める (上の計算式と少し違うが、全体に を掛けて調整できるためok)
- 要素の削除
の2種類。しかし(2) の要素の削除を考えると面倒なので、 が0 となる部分は無視するように (1) の計算方法を下のように変える。これで(2)の処理も簡単になる。
- 与えられた区間 の のうち、非0 の要素を集めたものを として を求める
- にする。
(1)の計算は次のように言い換えられる。 要素 とし、その上の 演算 を で定める。 このとき(1)の計算は の第一成分と一致する。
この演算はモノイドになっている(単位元は ) のでセグメント木が使える。 この演算は を前計算することで で計算できるので、(1)は で計算することができる。
これを と順番に処理していけば良いので全体の計算量は である。
また、 はすべて相異なるとしていたが、上の計算方法では重複した要素があっても問題なく計算できる。
提出コード : Solution: 25832307 | CodeChef
CodeChef Cook100 Editorial
CodeChef Cook100で解いた問題の解説です(div2の4問目、div1の3問目まで)。
Truth and Dare
概要
集合が与えられる。 かつ のとき "yes"と、そうでないとき"no"と答えよ。
解法
set<int>
で集合を管理して愚直に部分集合になっているか調べる。
制約が小さいのでvector
でも十分。
ソースコード: Solution: 24027534 | CodeChef
英語がとても読みづらい(というか未だに詳細を理解していない)。
Beautiful Garland
概要
R,Gの2種類からなる文字列s () が与えられる。 このsは先頭と最後がつながった一つの輪と考える。 この輪に対して以下の操作が高々1回できる。
- 輪を2つの文字列s1, s2に分解する。 そしてs2を前後反転させてから再度s1とつなぐ。
この輪をRとGが交互に現れるようにできるか。
解法
まずRとGの数が同じでないとどうやっても交互にはできない。
次にRとGの数が同じときを考える。 この操作は同じ箇所に対して2回行うともとに戻ることがわかる。 そのためこの操作でsをRとGが交互になるようにできたならば、sはRとGが交互になっている文字列から操作を1回だけして作ることができる。逆も同じ。
そのため、 sをR, Gが交互になっている文字列から操作を1回だけして作ることができるか分かれば良い。
両端が同じ文字の位置で反転させると変化しない。そうでないなら部分文字列"RR", "GG"がちょうど一回ずつ現れる形になる。
以上からsの中のR,Gの数が同じであり、かつsがすでにRとGが交互になっている or 部分文字列"RR", "GG"がちょうど一回ずつ現れるときに"yes"、そうでないなら"no"である。
ソースコード: Solution: 24027634 | CodeChef
A-B Game
概要
A, Bの二人でゲームをする。このゲームは長さの一直線上に並んだマスの上で行われる。 各マスにはAのコマかBのコマが置かれているか何も置かれていないかのいずれかである。 プレイヤーAはAのコマを、プレイヤーBはBのコマを動かすことができる。動かすことができるのは駒があるマスから移動する先のマス までに何もないときに限る。つまり、すでに置かれているコマを飛び越すことはできない。
またコマごとに動かすことができる方向が事前に決まっており、マスの左端から順番に右方向、左方向、右方向、・・・である。 これはゲームの間変わることはない。
マスの初期状態が文字列sとして与えられ、ゲームはAの手番から始まる。このときAが勝つかBが勝つか答えよ。
解法
大体のゲーム問題はNimに帰着できるのでNimにならないか考える。
まずコマを動かすことができる方向が右・左と交互になり、またコマを飛び越えて動かすことはできないので、 コマを左から2個ずつのペアにするとそれぞれ個別の独立したゲームが複数あるとみなすことができる (ただし奇数個あるときは別に考える必要がある)。
例えばs="A..B.A....B.BB"のときは次の3つの独立したゲームとみなせる:A..B, A...B, BB
ここで1つのペアに着目する。ペアにある空きマスの個数をLとする。 個別のゲームには次の2種類のパターンがある。
- 両端が同じ文字のとき: これはNimではコマを動かすことができるプレイヤーだけが自由に取り除くことができる石の山とみなせる。石の個数はLである。
- 両端が違うとき: どちらのプレイヤーも自分のコマを動かすことで任意のについて空きマスが個である状態に持っていける。これはNimでは石の数がL個ある山と同じ性質をもち、Nimとみなせる。
これらからこのゲーム全体は次のようなゲームに言い換えられる:
プレイヤーA,Bのどちらも自由に取ることができる石山(普通のNim)、プレイヤーAだけが石を取り除ける山、プレイヤーBだけが石を取り除ける山の3種類があるNimの亜種
このゲームの戦略としては、普通のNimでゲームを行い、何もできない状態になったら 自分専用の山から石を1つずつ取り除くのが最善である。
普通のNimの石山はAが勝つならばA専用の1つの石、Bが勝つならば無とみなせるので、 A,B専用の石の山の数の大小のみでゲームの勝敗を決められる。
最後にコマの数が奇数のときは右端のコマ専用の石の山とみなせばよい(この処理をしていなくて1WA)。
ソースコード: Solution: 24042766 | CodeChef
Tree Unattractiveness
概要
頂点からなる木Tとのうちいずれかの数字が書かれた 個のマーカーがある。 これらのマーカーを各頂点にちょうど一つずつ置いていく。 頂点に置かれたマーカーの数字をとする。
このときあるマーカーの置き方に対してそのスコアは で定められる。 マーカーを適当においたときに得られるスコアの最小値を求めよ。
解答
ありうるスコアは0,1,2のいずれかであり、0かどうかはすぐ分かる (すべてのマーカーか同じときに限る)。 そのため1が作れるかどうかを判定すればいい。
スコアが1になるように置くためには、マーカー0と隣接するのは0か1、マーカー2と隣接するのは2か1でなければならない。また1は何と隣接しても良い。
このことから、木に置いた1のマーカーがある頂点で木を分断すると、分断されたあとの各連結成分に置かれるマーカーはすべて0か2になっていなければならない。
この性質から根を適当に決めて木dpができる。 パラメータは今の頂点に何を置いたか、部分木で0,1を使った個数となる (2を何個使ったかは部分木のサイズから計算できる)。 ただし愚直に"dp[頂点][置いたマーカー][0の数][1の数]=スコア1が作れる/作れない"というtrue/false としてしまうと計算量的に間に合わない。
ここから次元を減らすことを考える。上で説明したように1は何と隣接しても良いためできるだけ使わないほうが良いと 直観的に分かる。 そこでdp[頂点][置いたマーカー][0の数]="スコア1にするために必要な1のマーカーの個数の最小値"としても正しく計算できる。
このとき遷移は頂点の子をとしたとき
-
ただし、に対して
-
ただし、に対して
-
ただし、に対して
このdpの計算量は一見に見えるが、二乗の木dpの形なので(参考リンク: https://topcoder.g.hatena.ne.jp/iwiwi/20120428/1335635594) になる。
AtCoderのコンテストカレンダーを作った
この前AtCoderで非公式コンテストがあったけれども、メールはないし公式のカレンダーにも載ってなかったので 危うく出損ねるという事案があった。 非公式だししょうがないかなぁというのもあるけどやっぱりカレンダーは欲しいので自前で作った。
GitHub - okaduki/AtCoderAllContestCalendar
AtCoderのホームページの「予定されたコンテスト」にある項目を取ってきて突っ込んでるだけ。 いくつか問題点としては
- コンテスト名をキーにしている → 後から時間などが変わったりしても反映されない
- 終了時間は適当に設定している → ページには開始時刻しかないため
気になったらそのうち直す。
ABC020 D LCM Rush
問題
D: LCM Rush - AtCoder Beginner Contest 020 | AtCoder
が与えられるので を計算せよ。
解法
となるので後はの約数 ごとにとして
が計算できればいい。
式変形が何をしているかと最後の総和の計算は解説 Editorial - AtCoder Beginner Contest 020 | AtCoder にあるので省略。
Game Theory (HackerRank)
この記事は 解説 Advent Calendar 2017の24日目の記事です。
以下のコンテストの解説です。 www.hackerrank.com
はじめに
競プロ!!Advent Calendarのこの記事 (競プロにおけるNim、Grundy数とNimK - かっさのなにか)に 触発されて書きました(というか解いてないことを思い出した)。
以下ではNim, grundy数などの知識を前提としています。 全く知識がない、あるいは不安な方は上の記事を読んでから解く and/or 解説を読むことを推奨します。 またxorをで表します。 特に記述がなければ、先手(プレイヤー1)と後手(プレイヤー2)が交互に手を打つゲームとし、 どちらのプレイヤーが勝つか出力する問題と思ってください。
Game of Stones
概要
Programming Problems and Competitions :: HackerRank
山に石が個ある。 プレイヤーは山から個いずれかだけ取り除ける。 取り除くことができなくなったプレイヤーの負けである。
解法
メモ化再帰。
Tower Breakers
概要
Programming Problems and Competitions :: HackerRank
それぞれに石が個ある山が山ある。 プレイヤーは一つの山に石が個あるとき、個に減らすことができる。ただしはを割り切れなければならない。
解法
のときは明らかに後手勝ち。 とする。 が偶数ならば後手は先手と全く同じように操作ができるから後手勝ち。 が奇数ならば先手が最初につの山をにすれば、上と同じ戦略が取れるから先手勝ち。
A Chessboard Game
概要
Programming Problems and Competitions :: HackerRank
のチェス盤に石がつ置いてある。 プレイヤーはにある石つをの いずれかに移動させる。ただし盤面外に移動させることはできない。 手を打つことができなったプレイヤーの負けである。
解法
メモ化再帰。
Nim Game
普通のNimなので略。
Misère Nim
概要
Programming Problems and Competitions :: HackerRank
山のNimをする。ただし普通のNimと違うところは 最後に石を取った人が負け (手が打てなくなったプレイヤーが勝ち) という点である。
解法
まずすべての山が1個の石からなるケースを考える。 このときは山の数が偶数なら先手勝ち、奇数なら後手勝ちである。
それ以外のとき、を(普通のNimと同じように)すべての山の石の個数の xorをとったものしてのとき、かつそのときに限り、後手勝ちであることを示す。
今、先手番でとし、先手が手を打つことでこれがになったとする。
このとき、後手番ですべての山の石がとなることは無いことが分かる。 もしそうなったとすると、仮定から先手が選んだ山以外の石の数はすべてであり、 先手が選んだ山はもともと個より多くの石があったことが分かる。 しかしこのような状況はの下では明らかに起こりえない。
これより、後手番では少なくともつの山は個より多い石がある。 石が個より多い山がちょうどつあるときは、その山をかに減らすことで、 山の数が奇数となるようにすべての山をにする ことができるので後手が勝つ。 そのような山がつより多くあると、次の先手番ではすべての山が1個の石からなることはない。 従って通常のNimと同じようにしてとなるように後手は手を打つことができ、 帰納的に後手勝ちであることがわかる。
逆に先手番でとすると、上の後手番の議論をそのまま適用できるので先手勝ちである。
よってすべての山が個の石である場合を例外扱いすることで、普通のNimと同じように解ける。
解説だと全部のときだけ場合分けすればいいとしか書いてないし、 それが正しそうな理由もよく分からなかった。 自分は実験してなんとなく規則性を見つけて適当に投げた。 実験せずに気付けるかと言われると微妙。
Nimble Game
概要
Programming Problems and Competitions :: HackerRank
個の箱が一列に並んでいて、と番号が付いている。 各箱には石が個入っており、プレイヤーは番目の箱にある石つを箱に移すことができる。 先に手を打つことができなくなったプレイヤーの負けである。
解法
位置にある石はそれより小さいのどこへでも動かせる。 これはNimのつの山にある石の個数が個であるときの状況とちょうど対応している。 よって がなら後手勝ちである。
Poker Nim
概要
Programming Problems and Competitions :: HackerRank
山にそれぞれ個石がある。 プレイヤーは各ターンでつの山から個以上の石を取り除くか、あるいは追加することができる。 ただし、石を追加できる回数は各プレイヤー、各山に対して高々回までである(個数は任意)。 最後の石を取り除いたほうが勝ちである。
解法
石を追加しないNimと全く同じ結果になる。 つまり、のとき、かつそのときに限り、後手必勝となる。 のときは先手が石を取り除こうが追加しようが、後手は先手と同じことをすればNim和はになる。 また石の追加は高々回までしかできず、必ず有限回で終わるので後手必勝。
のときは適当に石を取り除いての状態に持っていけるので先手必勝である。
Tower Breakers, Revisited!
概要
Programming Problems and Competitions :: HackerRank
山にそれぞれ個石がある。 プレイヤーはつの山にある個の石をまで減らすことができる。ただしはの 約数でなければならない。 最後の石を取り除いたほうが勝ちである。
解法
山がつで個石があるとする。 このときのgrundy数がどうなるか考える。 のある約数のgrundy数をとすると、の任意の約数にも から遷移できるので、のgrundy数は少なくとも以上である。 これをのすべての約数にわたって考えればとなる。
よくよく考えるとこれはの重複を含めた素因数の個数(例えばなら)と一致することがわかる (素因数でを割ったものならどれでも最大になるため) ので、各のこれを調べて最後にそれらのNim和をとればよい。
Tower Breakers, Again!
概要
Programming Problems and Competitions :: HackerRank
山にそれぞれ個石がある。 プレイヤーはつの山にある個の石を、個の石からなる個の山に分けることができる。 ただしでなければならない。 最後の石を取り除いたほうが勝ちである。
解法
基本的につ前の問題と同じで重複を含めた素因数の個数がgrundy数となる。 ただしを素因数にもつときは一度だけしか数えない(のグランディ数がとなるから)。
Chessboard Game, Again!
概要
Programming Problems and Competitions :: HackerRank
のチェス盤にいくつか石が置いてある。 つのマスに石が複数置いてあっても良い。 プレイヤーはにある石つをの いずれかに移動させる。ただし盤面外に移動させることはできない。 手を打つことができなったプレイヤーの負けである。
解法
素直にgrundy数を計算すれば良い。 盤面がで、ありうる遷移が高々なので愚直に計算しても十分に間に合う。 位置から動かせる手についてが成り立つから、 が小さいものから順に計算することができる。
Digits Square Board
概要
Programming Problems and Competitions :: HackerRank
のマスに整数が書かれている。 プレイヤーは盤面の面積がより大きく、かつ素数でないような数字が少なくともつ書かれているとき、 盤面を水平方向か垂直方向につに分割することができる。 手を打つことができなくなったプレイヤーの負けである。
解法
素直にgrundy数を計算すれば良い。 でメモ化再帰する。 素数でないものが部分長方形に入っているかを累積和で前計算しておけば、盤面が分割できるかどうかはで判定できる。 上の状態があり、各状態からの分割方法はあるので、 全体でで計算できる。
Fun Game
概要
Programming Problems and Competitions :: HackerRank
長さのつの数列がある。 プレイヤーはから、プレイヤーはから交互に数字を選んでいく。 ただしがすでに選ばれていたらを選ぶことができず逆も同様。 なのでちょうど回の操作でゲームは終わる。
各プレイヤーが選んだ数の総和を計算し、大きい方が勝ち、同じなら引き分けである。
解法
この手のつの数列から片方を選ぶみたいな問題は適当な評価値を決めて、 大きい方から選んだりdpしたりすることが多い気がするのでそうする。
このゲームは次のようなゲームに置き換えられる。
- プレイヤーは初期点としてを持っている。
- 数列 がある。
- プレイヤーはから数字を一つ消すことができ、プレイヤーは選んだ数だけプレイヤーの点数を減らせる。
- 最後にプレイヤーの点数が正ならばプレイヤーの勝ち、なら引き分け、負ならプレイヤーの勝ち。
なのでを計算、ソートして、数字が大きいものから順番に消す、点数を減らすことを交互にすればよい。
Powers Game
概要
Programming Problems and Competitions :: HackerRank
文字列がある。 プレイヤーは交互にをかのどちらかにつずつ書き換える。 最後にすべてのが無くなったら数式を計算し、で割りきれたら後手勝ち、そうでなければ先手勝ち。
解法
だけを気にすればいいから、現れる数字は実質だけとみなせる。 また、なるものがあれば、お互いに打ち消すように手を指すことができる (片方がに書き換えたらもう片方はに変える)ので、奇数個あるものだけ着目すれば良い。
あとは のようにをbitとして使いメモ化再帰で解ける。 なのでから順番に前計算しておけば良い。
Deforestation
Programming Problems and Competitions :: HackerRank
既出。同じ問題がhttps://beta.atcoder.jp/contests/agc017/tasks/agc017_dにある。 ハッケンブッシュ(Hackenbush)というゲームがあってそれの特殊な形である。
Tower Breakers - The Final Battle
概要
Programming Problems and Competitions :: HackerRank
個の石がある。となるまでプレイヤーは以下の操作を交互にする。
- プレイヤーはとなるように自由に石を分割する。
- プレイヤーはこの中から番目の山を選び、としてゲームを続ける。このときコイン枚を得る。
プレイヤーはプレイヤーが得られるコインの枚数を最小化、プレイヤーは最大化しようとする。 このとき最終的に得られるコインの枚数はいくらか。
解法
小さいケースで実験するとがある程度大きくなっても答えは大きくならないと予想ができる。
そこでとする。 明らかには単調増加になるから、となるような最大のが求める答えである。 番目の山を選ぶとコインを払うことになるから、 となる。 でとなるから愚直に計算しても実行時間は十分間に合う。
Rubyで競技プログラミング
最近Ruby on Rails チュートリアル:実例を使って Rails を学ぼうを終えてRubyの練習がてら競プロの問題をいくつか解いてみたので、 入出力の方法とかのメモ。
他に関連しそうな記事:
入出力
基本的なこと
- getsで標準入力から1行文字列を受け取る
- 改行も入るので取り除くには
gets.chop
とかする
- 改行も入るので取り除くには
- 整数への変換は
to_i
、浮動小数はto_f
、文字列はto_s
str.split
で空白文字で分割a.join(sep)
で配列を区切り文字で連結した文字列を得る
よくあるパターン
- 1行に整数が空白区切りであるとき
x_1 x_2 ... x_n
# 入力 # 個々の変数にとるとき a,b,c = gets.split.map(&:to_i) # 配列としてとるとき xs = gets.split.map(&:to_i) # 出力 puts xs.join(' ')
- 複数行に整数があるとき
x_1 x_2 ... x_n
# 入力 xs = [] n.times { xs << gets.to_i } # 出力 xs.map { |x| puts x }
- 複数行に複数個数字があるとき
n_1 x_11 ... x_1(n_1) ... n_m x_m1 ... x_m(n_m)
ns = [] # [n_1, ..., n_m] xs = [] # [[x_11,...],...,[x_m1,...]] 3.times do line = gets.split.map(&:to_i) ns << line.shift xs << line end
配列
Array.new(n,z)
で長さn、初期値zの配列を作る- zを省略するとnilで初期化
- 連番がほしければ
(1..n).to_a
でもできる
- 二次元配列は
Array.new(n){ Array.new(m) }
で作る- 最初知らずにハマったので注意(参考: Rubyで二次元配列の初期化 - simanのブログ)
<<
で末尾に追加pop
で末尾から、shift
で先頭から取り出す
AOJ 2403 The Enemy of My Enemy is My Friend
概要
頂点数の単純無向グラフが与えられる。 また各頂点には値が割り当てられている。 このとき、頂点を含む独立集合のうち値の総和の最大値を求めよ。
制約:
解法
半分全列挙+高速ゼータ変換 (想定解法ではないらしい)。
頂点を半分に分けて、を含む側を、含まない側をとする。 に対して関数をと定めて、 を高速ゼータ変換で求める。
あとは側の独立集合を全列挙しての最大値を返せば良い。 計算量は。