GCJ 2014 Round1

Round1Cで通過。
去年はRound1が通過できなかったのでよかった。参加記録だけ。

Round1A

寝坊して途中から。問題AからWA出してしまったため不参加(寝)。
問題Aは、解法が明らかに間違ってるのにその間違いに全然気づけなかった。。。
一つ固定してループ回す系。

問題B、Cは見てない。

Round1B

帰省中だったので、ノートパソコンで参加。
問題AとB-smallは解けたけど、1285位で通過ならず。

問題Aは、各単語を文字の数をカウントしておいて、一番少ない数から一番多い数までの中でどの数にすれば最小回数で一致させられるか求めて、すべての文字について足し合わせたものが答え。
問題B-smallは全探索。
問題C-smallは、next_permutationでたどるところを全列挙すればよいのに再帰で書いたらバグってしまった。。シンプルに書けない。

Round1C

問題AとB-smallを解いて、870位でギリギリ通過。
全体的に問題が難しく感じた(けど終わってみるとそうでもないかも・・・)。

問題Aは、スターンブロコット木かと思ったけど、実際に紙に書き出していくと、分母が2の累乗でなくてはならなく、分母Qを2で割っていってP/Qが1/2より大きくなるまでの個数をカウントすればよいことがわかる。(ビットで計算すればよかったらしい・・・)
問題B-smallは、全探索だけど、そのままやると結構やばいので、連続した文字をまとめたり、文字列の間に出現している文字が他でもでてきてたら0ですぐ終わる、とかで処理を軽減した。
B-largeは、文字についてグラフを作って数え上げればよいらしい。
問題Cはsmallも解けなかった。実際に領域を作ってみて、それを囲む石の数の最小値をやろうと思ったけどできてなかった。よくありそうな問題だし要復習しておきたい。