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個の０か１かの数字が入力されており、０であれば既に解かれている。


解法


やるだけ。

#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キロ食べていた場合、そのつぼをピグレットに渡す。
この操作を、つぼをピグレットに全て渡すまで繰り返す。
ピグレットは合計で何キロのハチミツを得ることが出来るか？

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

#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問題が解けて入れば、少しはマシだったかもしれませんが、今更嘆いても仕方がありません。
精進あるのみですね。