GCJ09-QR の成績・ソース : AC-AC/AC-AC/AC-AC : 去年の記事にこじつける参加記
A問題見る
- 『ちょうどD種類の単語（各単語はちょうどL文字。文字はアルファベット小文字26種）があることが判明している古代文明があります。全部の単語は判明済みです。部分的に読み取れてる単語がN個あるので、それぞれ可能な復元方法は何パターンか数えてね』
- "(abc)d(ef)g" だったら、１文字目はaかbかc、２文字目はdで確定、３文字目はeかf、４文字目はgで確定
- 単純に掛け算すると6通りだけど、そこから単語になってないものを削ると何通りかを数える
- アルゴリズムコンテストの挑み方 (1) 「書く前に計算量を見積もろう」
- 解き方なんて一瞬も考えようともせずにまずは入力データのサイズを見ます
- Small: 1 ≤ L ≤ 10, 1 ≤ D ≤ 25, 1 ≤ N ≤ 10
- Large: 1 ≤ L ≤ 15, 1 ≤ D ≤ 5000, 1 ≤ N ≤ 500
- あと、文字の種類C≤26も効いてくるかも
- だいたいの自分の感覚からすると…
- 時間計算量 O(LDN) のアルゴリズムは、Largeの制限時間8分でも通る。
- だから、それよりも高速なアルゴリズム（O(LD)+O(LN)等）を考案する必要は全くない。これで十分。
- O(CLDN) は…C++ならなんとかなるかなあ。遅めの言語だと不安。しかしそんな嫌なケースはこないような気もする
- Largeは捨ててSmallだけ通るような計算量オーダは？ O(2^L ND) とかその辺か
- (※この概算をする際に頭にうかべる計算量の項の選出基準として
- データベース(D)とクエリ(N)みたいな関係の場合、何も考えずやるとO(DN)っぽくなるけど、インデックスを作る的なことをするとO(D+N)っぽくなる
- 個別データの長さ(L)みたいなのは、何も考えずやると O(2^L) っぽくなるけど、工夫するとO(L)っぽくなる。DやNに関して指数時間や、その他線形より大きいオーダになりそうな気配はあんまりない
- みたいなのが自分の脳内にあるような気がする）
- というわけで、O(LDN) くらいを目標にアルゴリズムを考える。
- 機械的に、foreach(未確定単語)foreach(既知の単語)マッチしたらcount++。
- と、こんなもんじゃないかな。それだと O(CLDN) か。まあいいや、それで。
- マッチしたかどうか判定はどうしよう。
- 先頭からループしてって1文字1文字L文字目まで比較すればいいんだけど、
- 括弧の関係をちゃんとparseするのがめんどくさい。だるい。
- ピコーン
- これ、'(' と ')' を '[' と ']' に置き換えたら正規表現じゃね？
- "[abc]d[ef]g" だったら、１文字目はaかbかc、２文字目はdで確定、３文字目はeかf、４文字目はgで確定
- 完 璧
var INPUT = readFile(arguments[0]).split("\n")
var [L,D,N] = INPUT[0].split(" ").map(Number)
var words = INPUT.slice(1, 1+D)
var cases = INPUT.slice(1+D, 1+D+N).map(toRegex)
var answers = cases.map(solve)
for(var C=0; C<answers.length; ++C)
print( "Case #"+(C+1)+": " + answers[C] )
function toRegex(s)
{ return RegExp("^"+s.replace(/\(/g,"[").replace(/\)/g,"]")+"$") }
function solve(pat)
{ return words.filter( function(w){return pat.test(w)} ).length }
- ということでできた。正規表現の実装がちゃんとしてればO(LDN + CLN)くらいじゃないでしょーか。
- Small のデータをダウンロード…なんかエラー出た。ちょっとバグってるからしばらく待てと運営からメッセージが来てる。
- 不安だから念のためC++でも書いておこう。
- あらためて Small ダウンロード → submit → 正解！
- Large ダウンロード → js版でも数秒で終わった。疑ってすみませんでした → C++版とも答え合ったし、submit
B問題開く
- 『H×Wマスの2次元の高さマップが与えられるので、雨が降ったらその雨がどのマスに溜まるかで分類・色分けしてください。』
- 自分の周囲４マスのうち、一番低い（かつ自分より低い）マスに流れる
- 同点の場合は、北、西、東、南の順に優先。要はy座標小さい順→同じならx座標小さい順
- 入力サイズは？
- Small : 1 ≤ H, W ≤ 10; 0 ≤ altitudes < 10.
- Large: 1 ≤ H, W ≤ 100; 0 ≤ altitudes < 10,000.
- 要は10000マス。高さの値の大きさが問題になることはたぶんないでしょう…大小比較するだけだし。
- 深く考えなくても、色塗りなら適当に塗ってれば O(HW) になるんじゃないかなー。これなら速度は十分すぎる。O((HW)^2)はギリギリな感じ。それより遅いとマズい。
gets.to_i.times do |c|
puts "Case ##{c+1}:"
h,w = gets.split(" ").map(&:to_i)
m = (0...h).map{ gets.split(" ").map(&:to_i) }
uf,sz = {},{}
(0...h).each{|y| (0...w).each{|x| uf[[y,x]]=[y,x] ; sz[[y,x]] = 1 }}
(0...h).each{|y| (0...w).each{|x|
low = [[y-1,x], [y,x-1], [y,x+1], [y+1,x]].
select{|yy,xx| 0<=yy && yy<h && 0<=xx && xx<w }.
select{|yy,xx| m[yy][xx] < m[y][x]}
if low.size > 0
a = [y,x]
b = low.min_by{|yy,xx| [m[yy][xx],yy,xx]}
a = uf[a] until uf[a]==a
b = uf[b] until uf[b]==b
if a != b
a,b = b,a if sz[a] > sz[b]
uf[a] = b
sz[b] += sz[a]
end
end
}}
cur = ?a - 1
cl = Hash.new{|cl,k| cl[k] = (cur+=1)}
ans = (0...h).map{|y| (0...w).map{|x|
a = [y,x]
a = uf[a] until uf[a]==a
cl[a]
}}
puts ans.map{|ss| ss.map(&:chr)*" "}
end
- やたら長くなってしまった…普通に溜め池になるマスまでたどって塗っていく方がよかったかもしれない。まあいいや。
- パス圧縮してないけどバランシングはしているので、計算量は O(HWlog(HW))なはず。
- download & submit & download & submit! 20秒くらいかかって焦った。ちょっと富豪的に書きすぎた
+--+--+--+
| | | |
+--+--+--+
| | | |
+--+--+--+
| | | |
+--+--+--+
のまま考えるんじゃなくて
○-○-○
| | |
○-○-○
| | |
○-○-○
というグラフを思い浮かべる、ということはやっているような気がしなくもないです。チェス盤のマス目は二部グラフ のようなアイデアを使うと鮮やかに解ける問題には結構行き当たるので。
C問題開く
- 『与えられた文章の中から "welcome to code jam" を何個取り出せるか、数えてね』
- サイズ
- Small: 文章の長さLは30文字まで
- Large: 文章の長さLは500文字まで
- O(2^L) はSmallでギリギリ。Largeだと私が死ぬまで計算機回しても通らない。絶対に、指数時間になるアルゴリズムを書いてはいけない。
- O(L)かO(L^2)、最悪でもO(L^3)で解かねばならぬ。
- 賢く解くには…グラフ…にしてみようにもどうしたらいいのかわからないなー。
- ここはもう一つの手段、アルゴリズムコンテストの挑み方 (2) 「問題をひとまわり小さくしてみる」
- 元の文章を text[0..L] とする。L を減らしてみよう。
- つまり A =「text[0..L-1] に "welcome to code jam" が何個あるか？」をまず求める。
- 求まったらなんか嬉しい？
- 最後の1文字が "m" じゃない場合、すごく嬉しい。だって、その値 A がそのまんま答えになる
- 最後の1文字が "m" だった場合、全体の答えは A + 「text[0..L-1]に"welcome to code ja"が何個あるか？」で求まる
- 「text[0..L-1]に"welcome to code ja"が何個あるか？」はどう求める？
- さらにLを小さく、「text[0..L-2]に"welcome to code ja"が何個あるか？」を求めて、
- text[0..L-1]の最後の文字が"a"じゃないならそのままそれが答え
- "a"なら、それに加えて「text[0..L-2]に"welcome to code j"が何個あるか？」も足す
- 要するに
- text[0..0] に "w" が何個、"we" が何個、…"welcome to code ja"が何個、"welcome to code jam"が何個あるか
- を求めれば
- text[0..1] に "w" が何個、"we" が何個、…"welcome to code ja"が何個、"welcome to code jam"が何個あるか
- が求まって、次に
- text[0..2] に "w" が何個、"we" が何個、…"welcome to code ja"が何個、"welcome to code jam"が何個あるか
- がわかって
- ...
- text[0..L] に "w" が何個、"we" が何個、…"welcome to code ja"が何個、"welcome to code jam"が何個あるか
- がわかる。これだ！計算量は O(L×"welcome to code jam".length)
import std.stdio;
import std.string;
import std.conv;
int solve( string input )
{
string target = "welcome to code jam";
int[] q = [1] ~ new int[target.length];
foreach(c; input) {
int[] q2 = q.dup;
foreach(i; 0..target.length)
if( c == target[i] )
q2[i+1] = (q[i+1] + q[i]) % 10000;
q = q2;
}
return q[target.length];
}
void main()
{
int N = to!(int)( stdin.readln.chop );
foreach(i; 0..N)
writefln("Case #%d: %04d", i+1, solve(stdin.readln.chop));
}
