読者です 読者をやめる 読者になる 読者になる

ゆらのふなびと

競プロ, Python, C++

AOJ-ICPC 400 インビジブル

問題

インビジブル | Aizu Online Judge

D: インビジブル - JAG Contest 2016 Domestic | AtCoder

解法

先手はスコアの最大化、後手は最小化を目指すのでミニマックス法で解ける。

先手, 後手のデッキでスタックにつまれている区間をそれぞれ[l0, r0), [l1, r1)とすると、状態として(l0, r0, l1, r1, 今どちらの手番か, スタックが空になってから何回パスが連続したか)を持つだけでよいというのがポイント。パスで得点が変化するときには相手が最後に置いた妨害カードより上にある自分の得点カードの和がわかればよいので、実装ではこれらも引数に入れると楽だった。

あとこれはインビジブルあるあるなんですけど、スタックが空になってないのにパスの回数を足して死んでいた。

http://acm-icpc.aitea.net/index.php?plugin=attach&refer=2016%2FPractice%2F%E6%A8%A1%E6%93%AC%E5%9B%BD%E5%86%85%E4%BA%88%E9%81%B8A%2F%E8%AC%9B%E8%A9%95&openfile=D.pdf

gist.github.com

AOJ-ICPC 300 Line Gimmick

問題

Line Gimmick | Aizu Online Judge

解法

実装しんどいなーと思いながら書いたら一発で通って最高↑↑な気持ちで解説を見たらすごい簡単で悲しくなったので書きます。

ある'>'(=R0)からスタートすると、向きが変わるのはR1より右側にある1つ目の'<'(=L1), R0より左側にある1つ目の'>'(=R1), R0より右側にある2つ目の'<'(=L2), ...という風に続きます。左から順にR0をすべて試すとすると、どこが最後の反射になるかをしゃくとり(?)っぽく更新していくことができます。詳しくはコードのようにやりました。

ところがしゃくとりっぽくやる必要はなくて、累積和だけわかればどこが最後の反射かわかります。

mayokoex.hatenablog.com

実は n - min(左端に連続する'<'の個数, 右端に連続する'>'の個数) でいいらしい。

http://acm-icpc.aitea.net/index.php?plugin=attach&refer=2015%2FPractice%2F%E6%A8%A1%E6%93%AC%E5%9C%B0%E5%8C%BA%E4%BA%88%E9%81%B8%2F%E8%AC%9B%E8%A9%95&openfile=D.pdf

AOJ-ICPC 300 ABC Gene(☆)

問題

ABC Gene | Aizu Online Judge

解法

操作を逆順に考える。ある文字列 t を1段階前の文字列sに戻すことを考えると、t の中にある任意の"ABC"は、sにおいては直前の置換で選んだ文字Xだったはずである。仮にsに"ABC"が含まれていれば、必ずXが"ABC"に置換されるのでsの中の"ABC"がそのまま t に残ることはない。また、Xを置換するという操作以外から"ABC"という文字列は生まれえない。

t に"ABC"以外の形で含まれる文字はXたりえない。先に述べたように、s中のXと t 中の"ABC"が1対1に対応するからである。

以上を踏まえてdfsしたら通った。

gist.github.com

AOJ-ICPC 450 Encryption System

問題

Encryption System | Aizu Online Judge

解法

入力の文字列を s, 暗号化前の文字列をtとする

任意のiについて、t_i = s_i or s_i + 1 の2通りしかないので 220 の全探索が間に合う

左から見ていくと、t_i = s_i としてよいのは i の前に少なくとも1つ s_i と同じ文字があるとき

t_i = s_i + 1 としてよいのは i の前に1つも s_i + 1 と同じ文字がないとき

よって、(i, 構成中の文字列, 既に使われた文字)を引数とする再帰が書ける

やざてんさんのブログで見て気づいたけど、dfsの末尾で文字列をvectorに入れていくと勝手に辞書順になって最高

yazaten.hatenablog.com

gist.github.com

AOJ-ICPC 400 Restrictive Filesystem

問題

Restrictive Filesystem | Aizu Online Judge

解法

setで頑張る。

計算量がやばそうだったけど意外とそうでもないらしい

最初は区間の(左端, 番号)だけでやろうとしていたけどそれだと隣り合う空の区間をマージしないといけない場合がでてきてつらかったので(左端, 右端, 番号)にした

gist.github.com

AOJ-ICPC 300 Mirror Cave

問題

Mirror Cave | Aizu Online Judge

解法

脳筋BFS

DFSで書いたらREしたのでスタックオーバーフロー?

縁を'#'で埋めると楽

「片方だけが先にゴールについたらダメ」を忘れて死んでいた

gist.github.com

AOJ-ICPC 400 お姫様の暗号解読

問題

Princess, a Cryptanalyst | Aizu Online Judge

N個の文字列が与えられる。これらすべてを部分文字列として含む最小長さの文字列を求めよ。ただし、最小長さの文字列が複数ある場合はそのうち辞書順最小のものを答えよ。

制約

1 <= N <= 10

各文字列 s_i の長さは10文字以下

文字列はアルファベット小文字からなる

解法

http://acm-icpc.aitea.net/index.php?plugin=attach&refer=2008%2FPractice%2F%E6%A8%A1%E6%93%AC%E5%9B%BD%E5%86%85%E4%BA%88%E9%81%B8%2F%E8%AC%9B%E8%A9%95&openfile=E.pdf

解説を見たら実は全探索でも間に合うらしいんですが、DPで解いたのでDP解法を紹介します。

以下、文字列長の最大値をLとおきます。

DPで解くことを考えたとき、困るのは連結するときのコストの計算です。S = w_1 w_2 ... w_m (w_iは単語)という文字列ができているとき、この右側に w_{m+1} をつなぐことを考えましょう。w_{m+1} のprefixが S のsuffixと共有する部分が w_m の範囲に限られればいいのですが、もっと前の単語まで伸びると毎回コストを計算してあげなければならず詰みそうです。ところが、もしそのような(直前の単語より前まで共有されるような)場合には w_m は w_{m+1} に完全に含まれていることになります。そこで前処理として、他の単語に完全に含まれるような単語を消しておきましょう。するとSに新しい単語をつなぐときのコストが直前に採用した単語と次に採用する単語のみからわかることになります。

単語を頂点とし、有向辺を各頂点間に両向きに張ったグラフGを考えます。辺 i->j のコストは s_i の後ろに s_j をつないだときに共有できる文字数とします。するとこの問題は、G上の最長ハミルトンパスを求める問題に帰着されました。あとはよくあるbitDPです。辞書順最小のものを求めたいので、実際にはdp配列に文字列そのものをもってやるといいみたいです。

以下のコードは頭がないので文字列長でDPしたあと経路復元して最小のものを求めています。

gist.github.com