ゆらのふなびと

競プロ, Python, C++

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

AOJ-ICPC 400 Eleven Lover

問題

Eleven Lover | Aizu Online Judge

10進数表記の数sが与えられる

sの部分文字列のうち、11の倍数であるものの個数を答えよ

ただし、部分文字列のうち先頭が0でないもののみをカウントする

制約

|s| <= 80000

解法

「11の倍数 ⇔ D = (奇数桁目の和) - (偶数桁目の和) が11の倍数」を使う

i桁目までのDをD_iとすると、i桁目を末尾とする11の倍数の個数は、D_1, ..., D_{i-1}のうちD_iから引いて0(mod11)になるものの個数

O(|s|)

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2041828#1

KUPC2016京都オンサイトに参加しました

終了15分前にこの記事を書いています。

kupc2016.contest.atcoder.jp

A - バリケード / A Barricade

区間に含まれないものがいくつあるかカウントする。

gist.github.com

B - 作問委員会 / Problem Committee

たくさんあるやつから使えばいいのかなーと思いながら書いたら通った。

gist.github.com

C - クッキー☆増殖装置 / Cookie Breeding Machine

どうせ127作れるやろ~と思ったら作れたので投げた。Nの偶奇によって最後にDが余るかDのビットを反転させたものが分かれる。手で実験してたらわかった。

gist.github.com

D - 長い黒板 / Long Blackboard

各列ごとに全探索?して埋めていけばよい。実装にてこずった。

gist.github.com

E - 柵 / Fences

いけそうだなーと思って書いてたけど全然だめだった。他の部分点もわからず。

感想

あとでちゃんと書きます。