スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

August Cook-Off 2012

昔解いた問題を整理するついでに、さぼってブログに書いてなかった回のもちゃんと書くことにした。

Tags プログラミング CodeChef

結果

5 問中 4 問解いて 23 位。
全問が yes/no を答えさせる問題だった。

問題

CHEFPASS. Codechef Password Recovery
52 個の頂点があり、二つの辺集合 A, B が与えられる。
A の辺はすべて選び、B の辺は好きなものだけ選んでいい。
選んだ辺集合が閉路の和になるようにできるか?

1 ≦ テストケース数 ≦ 100
1 ≦ |A|, |B| ≦ 1000

LEBINARY. Asmany Number Verification
長さ n の asmany string とは、01 の列であって "00", "11" が部分文字列として含まれる個数が等しいもののこと。
n 番目の asmany number とは長さ n の asmany string の個数。
与えられる数 N が asmany number かどうかを判定せよ。

1 ≦ テストケース数 ≦ 100
1 ≦ N の桁数 ≦ 1000

NOCODING. Code Crazy Minions
アルファベット小文字を一文字だけ格納できるバッファがある。
三つの命令をくり返して所望を文字列 S を出力したい。
必要な命令回数が 11・|S| 以下なら YES、そうでないなら NO と答えよ。

命令は
LOAD : バッファに好きな文字をロードする
INCREMENT : バッファをインクリメントする ( 'z' は 'a' になる )
PRINT : バッファの文字を出力する

1 ≦ テストケース数 ≦ 100
1 ≦ |S| ≦ 1000

UNFRIEND. Rebuilding Byteland
単純連結無向グラフで、辺は
- ふつうの辺
- 辺の両端の頂点をマージしていい
のいずれかの属性を持っている。
好きなだけマージして二部グラフにできるか?

1 ≦ テストケース数 ≦ 100
2 ≦ |V| ≦ 50
1 ≦ |E| ≦ 200
1 ≦ マージできる辺の数 ≦ |E|

YNOUTPUT. Forced Output
T 個のテストケースが与えられる。
各テストケースは T 個の YES or NO からなる。

YES or NO を T 行出力せよ。
出力の i 行目が YES のとき、T 行の出力はテストケース i と完全に一致していないといけない。
出力の i 行目が NO のとき、T 行の出力はテストケース i と少なくとも一箇所異なっていないといけない。
ちょうど一つの解が存在することが保証されている。

1 ≦ T ≦ 100

解答

CHEFPASS
辺集合として A だけを選んだグラフを A、
辺集合として B だけを選んだグラフを B と同じ記号で書くことにする。

コンテスト中は試行錯誤して
「B で推移閉包をとった後、B の頂点を A の奇数次数のものに制限したグラフを考えて、連結成分のサイズがすべて偶数であればよい」
という判定方法を考え、Accepted をもらった。なぜこの考えに至ったのかは忘れた。

Editorial の想定解はシンプルでもっとよいので記録しておく。

まず前提として、グラフが閉路の和で書けることと、すべての頂点の次数が偶数であることは同値。知らなかったら "Eulerian graph" とかで検索しましょう。
A の奇数次数の頂点全体を V とする。
|V| が偶数であって、V のすべての頂点が B の辺を使ってペアリングできればよい。
実は、このペアリングが存在することと、B の各連結成分に V の頂点が偶数個含まれることが同値!!!
理由を簡単に書くと、まず辺を共有してもいい |V|/2 個のパスを作って、その後で適当に対称差をとると辺の共有が解消されるから。

http://www.codechef.com/viewsolution/1272289

LEBINARY
小さいケースを全探索すると簡単に規則性が見つかる。
多倍長が必要だったので Java で書いた。
大きい mod での値を見てもまぁ大丈夫なので C++ でもよかった。

http://www.codechef.com/viewsolution/1270440

NOCODING
書かれている通りに実装するだけ。

http://www.codechef.com/viewsolution/1269302

UNFRIEND
Editorial を参考にして解いた。

tester 解の概略を書いておく。
ふつうの辺のみからなるグラフが二部であることが必要十分。
必要であることは、"二部グラフである iff 奇数長の閉路がない" からわかる。
十分であることは、二彩色したあと同色の頂点のみをマージすると、すべての辺を考慮したグラフもちゃんと二部になっていることからわかる。


setter 解はもっと高級。
"二部グラフである iff 奇数長の閉路がない" を再び用いる。
サイクル基底を取り出して O(n) 個くらいの閉路について調べればよい。
( 偶数長閉路どうしの対称差は偶数個の辺からなるからこれでよい。)
これは、マージできる辺を使うかどうかを 0-1 変数で表せば、GF(2) 上の連立線形方程式が解をもつかどうかの判定問題になる。


サイクル基底が使える問題に遭ったのはこれで二問目。

http://www.codechef.com/viewsolution/1288170

YNOUTPUT
読みにくいけど、オリジナリティあふれるおもしろい問題。
解法自体は単純で、単に、どのテストケースと一致するか、またはどれとも一致しないかをすべて調べればいい。
どれとも一致しないケースを忘れて 2WA をもらった。

http://www.codechef.com/viewsolution/1269422
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

Author : fura2
数学・コンピュータを中心に、考えたこと・やったことを書いていきます。

誤植等を含め、間違いはご指摘いただければ幸いです。

FC2カウンター
検索フォーム
最新記事
最新コメント
最新トラックバック
月別アーカイブ
リンク
RSSリンクの表示
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。