(o_o)

ブログ。

AOJ2574 Magical Switches

問題概要
3行3N+1列のマップがあり，同じアルファベットについて，大文字と小文字の一方は全て壁であり，もう一方は通れる床である．左から右まで通れるようにしたいとき，壁にする大文字を全て出力せよ．解が複数あればどれか1つを出力せよ．解がない場合は -1 を出力せよ．

解法
愚直にやると 2^26 * 3 * N なので厳しい．3-SAT に変換して解く．条件が 2^3*N 項くらいになるので，計算量が O(3^8N) くらいになるが，適当に枝刈りすれば通る．オススメの枝刈りは，
・a or b or c の条件を見る際，既に前提として a or b or c が確定しているときは分岐しなくてよい
・a or b or c の条件を a or (not a and b) or (not a and not b c) に変換する
一応入力列をいい感じにソートしたりしたが，効果があったかどうかは知らない．

続きを読む

AOJ1353 Sweet War

問題概要
1つのチョコボールのスタックを使って2人ゲームを行う．
それぞれのチョコボールに栄養価r_iと美味しさs_iが定められており，
2人は食べたチョコボールの美味しさを最大化したいと考えている．

2人にはそれぞれ体力値が定められており，それぞれ初期値はA,Bである．
交互に以下の行動のうちのいずれかを行う．
パス：チョコボールを食べない．体力が1減る．残り体力が0のときはパスできない．
食べる：スタックの一番上のチョコボールを食べる．体力がr_i上がる．
スタックが空になったときゲーム終了である．

双方が最適な行動をとった場合，それぞれが食べる美味しさの和を求めよ．

解法
反射的に思いつくのは
dp[i][j] = 体力差がjあるときに，i番目のチョコ以降で付けられる点差の最大値
みたいな感じのDPだけど，これだと　O(N^2 * (A+B)) でダメ．
そこで，これを
dp[i][j] = i番目のチョコ以降で j 点差以上つけるのに必要な体力差の最小値
みたいな感じに変形する．蟻本にもあるテクだよね．

パスする場合と食べる場合の2通りの行動パターンがある．
ここで，r_i >= 0 であるから，自分の方が体力差が1以上強い場合はパスすることで相手に手番を渡せて，
そうでないときはパスが効かないことがちょっと考えたらわかる．
食べる場合がちょっと複雑で，相手にとってj点差あるときは体力差が dp(i,j) あれば相手が勝ってしまうから，
体力差が dp(i,j)+1 あれば相手は高々 j-1 点差しかつけられないよね・・・みたいな感じで適宜 +1 や -1 を補った DP 式を書かなきゃいけない．そこらへんは実装に依りそう．

DPは苦手．っていうか再帰が苦手や

続きを読む

AOJ2539 Counting 1's

問題概要
略

解法
とにかく入力ケース数が多い．呑気に二分探索なんてしてたらTLEする・・・
k_1 を見ると B-A が3通りに絞れる．B-A が決まれば，k_n から順に見ていけば，(A,B) の組み合わせは高々1通りに絞れることがわかる．

続きを読む

AOJ2455 Sun and Moon

問題概要
sum_i (P_i * x^O_i) = 0 かつ sum_i (P_i * O_i * x^(O_i - 1) = 0 となるような最小の正整数 x を求めよ

解法
最小次数の係数の約数が解の候補となるので，それで全部試す．O(√(NP)) だけど，AOJ鯖は速いので間に合う．
これって f(x) = f'(x) = 0 となるような x，つまりは f(x) の重解を求める問題だし，もっともらしい解法もあるかもしれない．

続きを読む

AOJ2557 Iyasugigappa

問題概要
カエルとカッパとイタチがカードゲームをしている

このゲームでは，ギロチンカード1枚，貴族カード12枚，アクションカード6枚を使う．貴族カードとアクションカードの表には，それぞれ整数値が書かれている．まず，ゲームを始める前に，プレイヤーはテーブル上に一列に12枚の貴族カードを伏せて，その右にギロチンカードを置き，それぞれのプレイヤーには2枚のアクションカードが配られる．この問題では，全てのカードをオープンにして，完全情報ゲームにするものとする．

ゲーム中，カエル，カッパ．イタチの順にターンが回ってくる．ターンはアクションフェーズと処刑フェーズに分かれており，その順に行われる．

アクションフェーズでは，持っているアクションカードを1枚使うことができる(使わなくてもよい)．値yが書かれたアクションカードを使うとき，ギロチンカードの前の貴族カードから数えてy番目(1-based)の貴族カードをギロチンカードの直前に移動する．このとき，少なくともy枚の貴族カードが場になければならない．もし場の貴族カードがy枚以下なら，アクションカードの効果は無効になる．使ったアクションカードは手札から取り除かれる．

処刑フェーズでは，ギロチンの直前にある貴族カードが取り除かれ，プレイヤーはその貴族カードに書かれている値の勝利点を得る．

ゲームの終了条件は全ての貴族カードが場からなくなることである．

それぞれのプレイヤーは以下の戦略に従って行動する．
・それぞれのプレイヤーは自分の最終的なスコアが最大化されるような戦略に従って行動すると仮定される．
・カエルとイタチは実際にその戦略に従った行動をする．
・しかし，カッパはカエルの最終的なスコアが最小化されるように行動する．
・カエルとイタチは，カッパも自分の最終的なスコアが最大化されるように行動していると思っているし，カッパもそのことを知っている．
・適した行動が複数存在する場合，そのターン終了後の自分のアクションカードの合計値が多くなるように動く．

それぞれのプレイヤーの最終的なスコアを求めよ

解法
カエルとイタチ，カッパについての再帰関数を書く．メモ化は必要ない．再帰関数の返り値は (最善を想定したときの最終的な結果, 次の1手) としておく，カエルとイタチの関数については容易に書ける．カッパの関数については，カエルとイタチの関数を使ってシミュレーションさせる感じの再帰関数にする． 結構頭がこんがらがってややこしい．

続きを読む