School Regional Team Contest, Saratov, 2011

Code Forces で開催された 「School Regional Team Contest, Saratov, 2011」に参加してきました。
しょうもないミスでCまでしか解けていません。


Problem A
Elevator
Passed System Test
簡単という比喩ではなく本当にやるだけ。
School Contestなので、慣れない人たち向けのウォーミングアップ問題の意味合いで設けたのでしょう。


Problem B
Quiz League
Passed System Test
ランダム選択式クイズリーグの途中である。
全部でN問問題が存在し、既に幾つかの問題が解かれている。
今、問題が１〜N番目の中からランダムに選択されようとしているが、既に解かれてしまった問題が選択された場合、その次の問題を解くことになる。それも解かれていた場合、同じことを繰り返す。
N番目の次の問題は、１番目の問題とみなす。


K番目の問題が選ばれたとして、実際に解くことになるのは何番目の問題か。


１行目にN K、
２行目にはN個の０か１かの数字が入力されており、０であれば既に解かれている。


解法


やるだけ。

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

#include <string> #include <iostream> #include <algorithm> #include <queue> #include <map> #include <vector> #include <set> #include <cstring> #include <cstdio> #include <cstdlib> #include <fstream>   using namespace std;   #define REP(i,s,e) for(int i = s;i < e;i++) #define rep(i,e) REP(i,0,e) #define ll long long   int main(){     ifstream input("input.txt");     ofstream output("output.txt");     int yet[1000];     int n,m;     input >> n >> m;     rep(i,n) input >> yet[i];     for(int i = m-1;i < m+n;i++){         if(yet[i%n]){             output << (i)%n + 1 << endl;             return 0;         }     } }

Problem C
Winnie-the-Pooh and Honey
Passed System Test


問題文
ハチミツの入ったつぼがN個ある。
それぞれのつぼにはAi キログラムのハチミツが入っている。
プーさんは飢えており、つぼを取っては、そのつぼに入っているハチミツをKキロ食べる。
選んだつぼに入っているハチミツがKキロ未満の場合か、既にそのつぼから３Kキロ食べていた場合、そのつぼをピグレットに渡す。
この操作を、つぼをピグレットに全て渡すまで繰り返す。
ピグレットは合計で何キロのハチミツを得ることが出来るか？

解法
やるだけ。問題文には、実はハチミツの一番多く入っているつぼを常に食べると書いてあるのですが、これは解法には全く関係しないため、省略しました。

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35

#include <string> #include <iostream> #include <algorithm> #include <queue> #include <map> #include <vector> #include <set> #include <cstring> #include <cstdio> #include <cstdlib> #include <fstream>   using namespace std;   #define REP(i,s,e) for(int i = s;i < e;i++) #define rep(i,e) REP(i,0,e) #define ll long long #define INF 1 << 30   int main(){     ifstream input("input.txt");     ofstream output("output.txt");     int jars[100];     memset(jars, 50000, sizeof(jars));     int n,k;     int ans = 0;     input >> n >> k;     int limit = k * 3;     rep(i,n) input >> jars[i];     sort(jars, jars+99);     rep(i,n){         if(jars[i] < limit) ans += jars[i] % k; else ans += jars[i] - limit;     }     output << ans << endl; }

Problem D
Three sons
Wrong Answer on Pretest 3


n*m行列が与えられる。行列のij要素はそれぞれの領域におけるとうもろこしの収量を表す。
この畑を、互いに平行な２本の線を引くことで３つに分割し、それぞれの畑の収量がA,B,Cとなるように分割する方法は何通りあるか？なお、畑は斜めに斬ってはならず、それぞれの畑は最低でも１つの領域を持っていなければならないとする。


ソート関数のメモリ指定を間違えるというポカをやらかした挙句、それに気付かず、ロジック部分に問題があると思い込んで粗を探していました。
終了後に気付き、落ち込む。

解法はnext_permutationを使った至って単純な全探索でした。
データセットが非常に軽いため(最大でも50*50行列)、全探索でも何の問題もありません。


Rating 1446 → 1420 (-26)

少し落ちてしまいました。D問題が解けて入れば、少しはマシだったかもしれませんが、今更嘆いても仕方がありません。
精進あるのみですね。

CaBoCha on Ubuntu 11.04 with charset UTF-8

構文解析器CabochaをUbuntuに実行する際、詰まった点がそこそこあったので、メモしておく。
特に後半に関してはWebでエラーログを検索しても情報がほとんど無かったため、手探り感があった。
Cabochaのインストールそのものについては、他にたくさんのBlogが存在しているので、それについては省く。
このブログに辿り着いた人は多分、

param.cpp(70) [ifs] no such file or directory: /etc/cabocharc

こういうログか、あるいは

morph.cpp(108) [charset() == decode_charset(dinfo->charset)] Incompatible charset: MeCab charset is UTF-8, Your charset is EUCJP-WIN

こういうログで困っているのだろう、と推測する。
まず前者であるが、これはもうエラーログ通り /etc/cabocharc が存在していないことがエラーの原因だ。

sudo find / -name cabocharc

としてやると、おそらく、

/usr/local/etc/cabocharc

というものが見つかる筈だ。
これを

 /etc/cabocharc

にコピーしてやればよい。
次に後者である。
これは、 charset-file.txt に書いてある文字コードと、cabocha の文字コードが一致していないことによって生じている。

sudo find / -name charaset-file.txt

としてやり、セッティングファイルを探す。
いくつか出てくるかもしれないし、一つかもしれない。
それは色々な場合があるので分からないが、そのうちの一つがUTF-8になっていることを確認し(無ければ編集し)する。
次に、先ほどコピーしてやったcabocharcを開く。
コメントアウトされた charaset-filr = PATH という行が見つかる筈だ。
コメントアウトを解除し、先ほどUTF-8と書いてあったファイルへのPATHを記入し、保存してやる。
これで、問題なく動くようになるはずだ。

GCJJ

GCJJに行ってきた。
起きたのが17：50ぐらい。
とりあえず軽くメシ食って、始めたのが18：20分ちょい前ぐらいだったか。

時間がヤバ過ぎたので正解率の高いCを選択。

正の整数Nを、0以上の整数であるa と b を使い

a + b = N

と表す。
f(x)を、xを二進数で表した場合の１の数とし、

f(a) + f(b) = k

のkが最大になる場合のkの値を求めよ。

という問題。
例えば、９ならば、

f(9) + f(0) = 2
f(8) + f(1) = 3
f(7) + f(2) = 4
f(6) + f(3) = 4
f(5) + f(4) = 3

と、それぞれなるので、正解は4となる。

初めは愚直に探索していくのかなと思ったが、largeの制約が N < 10^18だったため、どう考えてもそれでは間に合わない。
二進数ならではの考え方がある。
ビット単位で考えてやると、 10 < 2^4であるから、最大でも4*18 = 72より少ない計算量で達成出来る。

a + b の形になっているので、二進数の特質が大いに生かせそうだ。

暫く考えていたところ、0がキーになっていることが分かった。
11100100111のような場合、右から考えてやって、最初に0が出るまでの1は、aかbどちらかの該当ビットだけに1を設定してやることによってしか表現出来ないが、それ以降の1は、aとbの両方の該当ビット一つ下に１を設定してやることで表現出来そうだ。
これを拡張して、1001001のように0が続いている場合、a = 0111111, b = 0001010 のように表現できることが分かる。

これを実装したのが以下

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44

#include <algorithm> #include <iostream> #include <map> #include <numeric> #include <set> #include <sstream> #include <string> #include <vector> #include <stack> #include <queue> #include <cmath> #include <time.h> using namespace std;   #define REP(i,s,e) for (int i = int(s); i != int(e); i++) #define rep(i,e) REP(i,0,e) #define foreach(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++) #define ISEQ(c) (c).begin(), (c).end() #define ll long long #define INF 1<<30       int main(){  unsigned ll n;  int testCase,bits_after_zero,bits_before_zero,num_zero;  scanf("%d", &testCase);  rep(i,testCase)  {   bits_after_zero = 0; bits_before_zero = 0; num_zero = 0;   scanf("%lld", &n);   do{    if(n & 1) bits_before_zero++; else{     n >>= 1;     break;    }   }while( (n >>= 1) > 0);   do{    if(!(n > 0)) break;    if(n & 1) bits_after_zero++; else num_zero++;   }while( ( n >>= 1 ) > 0);   printf("Case #%d: %d\n", i+1, bits_after_zero * 2 + bits_before_zero + num_zero);  } }

残りの問題は後でまた解く