JOI2015本選オンラインに参加した

こんばんは.chigichanです.
テストシーズンはしなきゃいけないことが全くはかどらないですね.

ということで,後輩たちが参加していたJOI本選のオンラインに参加しました.

といっても気づいたのが,

JOIのopencontestの存在に気づいたぞ

— 生きる価値が見いだせない (@chigichan24) February 8, 2015

の15分くらい前で,1問目をささっと読み始めました.

読んだ感じだと,今までの本選1問目の傾向と少し違うかなという感想でした.

普段は,強実装 or 数学 という印象でしたが,累積和だったので多少驚きました.

という感じで15分くらいで書いて,提出~(^_-)-☆

ん?

ん?

提出したけどレスが全く返ってこない

— 生きる価値が見いだせない (@chigichan24) February 8, 2015

5分くらい待ちました.

50/100 WA

え?

しかし,TLEではないのでなんでやねんという感じに...

10分後くらいに気づいた.

ansの値はintを超えると....

訂正して提出~(^_-)-☆

f5押しまくって待機してたら....

503

504

(;_;

鯖落ちかよ....

そして,

時は過ぎ,

ジャッジの結果を知るのに1時間半かかるの流石に萎えますよ

— 生きる価値が見いだせない (@chigichan24) February 8, 2015

終了45分前くらい...

その後2,3は問題を読んで,

2はメモ化再帰で書くと楽そう.
3はdijkstraがんばれ♥がんばれ♥って感じという感想.

結果:1完

JOIは良問多くて良いですね~
後輩は一人春の可能性があるので彼が通ってるといいな~

コード

#include <bits/stdc++.h>
using namespace std;
const int dx[]={0,1,0,-1,1,-1,-1,1};
const int dy[]={-1,0,1,0,1,1,-1,-1};
const int INF = 1<<30;
const double EPS = 1e-15;
#define PB push_back
#define mk make_pair
#define fi first
#define se second
#define ll long long
#define reps(i,j,k) for(int i = (j); i < (k); i++)
#define rep(i,j) reps(i,0,j)
#define MOD 1000000007
typedef pair<ll,ll> Pii;
typedef pair<Pii,Pii> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
vector < Pii > data;
ll D[100001];
ll IC[100001];
Pii cost[100001];
vector < Pii > imos;
int main(){
    int N,M;
    scanf("%d%d",&N,&M);
    rep(i,M){
        scanf("%lld",&D[i]);
        D[i]--;
    }
    rep(i,N-1){
        ll a,b,c;
        scanf("%lld%lld%lld",&a,&b,&c);
        cost[i] = Pii(a,b);
        IC[i] = c;
    }
    rep(i,M-1){
        ll a = min(D[i],D[i+1]);
        ll b = max(D[i],D[i+1]);
        imos.PB(Pii(a,1));
        imos.PB(Pii(b,-1));
    }
    sort(imos.begin(),imos.end());
    ll prev = -1;
    ll sum = 0;
    ll ans = 0;
    rep(i,imos.size()){
        if(prev != imos[i].fi){
            if(prev == -1){
                prev = imos[i].fi;
            }
            else{
                ll index = prev;
                while(index < imos[i].fi){
                    ans += min(cost[index].fi*sum,cost[index].se*sum+IC[index]);
                    index++;
                }
                prev = imos[i].fi;
            }
        }
        sum += imos[i].se;
    }

    printf("%lld\n",ans);
    return 0;
}

相変わらずコードが汚い...

テスト勉強しなきゃ....

競技趣味グラミングと作問のすすめ

この記事はICT Advent Calendar 2014の21日目の記事として書いています.

はじめまして!からお久しぶりです!という人まで,こんにちはchigichanです.

軽く自己紹介をすると,
Kurume-NCT3年で今年はJOI夏季セミナー,高専プロコン自由部門に参加していました.
性別は間違えられることが多いです(Twitterのbioを見るとわかるぞ).

それと

なっちゃんの方向を向いて土下座するの今日から毎日の日課にする.

— 妖怪害悪こぼし (@chigichan24) December 10, 2014

こんな感じでなっ様を崇拝しています.

ということで,今年は記事の題の通り,

"競技趣味グラミングと作問のすすめ"

という内容で記事を書こうかと思います.
かなり,私の独断と偏見で書いているさらにはネタとしての
部分がかなり多いのでそこら辺は各自で判断してください.

1.競技趣味グラミングとは

私が勝手に作った言葉です.
意味としては,競技プログラミングを趣味として楽しくやる人のことです.
なぜこんな言葉をわざわざ用いる必要があるかと言うと,

@chigichan24 プロ

— やよいがかわいすぎてつらい (@Div9851) December 10, 2014

こういう風に唐突にプロと言う風潮がなぜかJOI界隈から生まれているわけです.
そしてさらに,それの返答としては

"趣味"

という言葉が使われることが知られています.

しかし,このプロに対する趣味という言葉には謙遜の意味合いしかないと私は思います.
つまり,この掛け合いをしている時点で競技プログラミング能力が非常に長けているんだと私は解釈しています.

また,初心者などと超上級者が発言していたりして本当に初心者である私がつらい＞＜となることもしばしばあります.

そんな　怖い＞＜　競技プログラミング界隈に興味はあっても近づけない.
という私のような人間が少なくとも一定数いると思います.

そこで,自分はただ趣味として競技プログラミングをしているだけなのでと言い張るときにこの

"競技趣味グラミング"

という言葉が使えるのではないかと思います.
趣味じゃなくてガチでやりたいと思えば趣味のところをプロにするだけであら不思議

"競技プログラミング"

になってまさに趣味からプロになるじゃないですか!!!

ということでみなさん.唐突に"プロ"と言われたら"趣味"と答えては負けです.
"趣味グラミング"をやっているだけと主張しましょう.

2.私と競技趣味グラミング

私は競技ができるできないに関係なくとても好きです.よく,

問題を考えてもわからない.

上位陣との差が激しすぎてつらい

などの意見を耳にすることがありますが,私は全然そう思ったことはありません.
出来なくても,おもしろいし自分のペースでやっていけばいいと思っています.

本当に趣味であることは私の様々なrating*1*2やsolve数*3が物語っています.

だからこそ言いたい,出来なくても興味があるならばやらなきゃ損であると.

確かに,いきなり才能が開花して息をするように問題をとければそれはそれはうれしいでしょう.
けれども,私みたいにできない人(私はかなりできない部類の人間だが)はゆっくり考えればいいんです.
本当の意味の趣味としてやっていけばいいんです.
レートが落ちたら次に取り戻せばいいんです.

と思います.大事なのは好きでい続けることかなぁと.

そりゃあもちろんある大会に出ると決めたならそれに向かって頑張る必要はあるしそこでの結果は大事です.
ただ,そこでの結果が散々だったからといって学ぶことをやめるのはどうなのかなと.

3.作問のすすめ

私は3年生になって作問をする機会がかなり増えました.理由としては,

・部にジャッジシステムが導入されそこでコンテストが開けること.
・そのコンテストシステムで自分のコンテストを1.5ヶ月に1回ほどのペースで行っていること.
・後輩のJOI対策のため.

などだと思います.

たいした問題は作れません.けれども面白いです.
いろんなコンテストがありますが,AtcoderやKCSの問題文ってとても面白いですよね.
そういうのをまねながら部員に楽しく解いてもらおうと頑張ってます.

さらに,自分の苦手なアルゴリズムや,知らなかったアルゴリズムなどを勉強する機会
にもなっていいことだらけです!!

ぜひみなさんも,作問してみましょう!!!

部のジャッジシステムに投稿した問題の一部

まとめ

だらだらといろんなことを書いてきましたが,結局は

競技プログラミングは楽しいＯ(≧∇≦)Ｏ

ということをいいたかっただけです.

そして,競技プログラミングを通してたくさんの人とかかわりたいなと思います.
来年度の高専プロコンやその他多くのコンテストで皆さんと会えるように精進しますので,
どこかで会う機会があったらぜひ声をかけてください.

とっても長文になってしまってごめんなさい:P

ちなみに,今日のアドベントカレンダーは私のほかに,期待の大型新人 @wing3196 君と沖縄の @Greeeenapple さんです.
ぜひそちらもご覧になってはいかがでしょうか?

明日は,沖縄の @rin_neko19 さんです.

それでは,よいクリスマスと冬休みを~

*1:http://community.topcoder.com/tc?module=MemberProfile&cr=23301803

*2:http://codeforces.com/profile/chigichan24

*3:http://judge.u-aizu.ac.jp/onlinejudge/user.jsp?id=kachan

JOI2015予選の問題を解いてみた

こんにちは,chigichanです.

実際にコンテストの行われていた時間に参加したわけではないですが,解いてみました.
2時間半くらいであきらめました.

結果は520点でした.

今年は難化すると思ってたらめっちゃ易化してたのでびっくりです.
特に3問目がもはややるだけとなっていたので...

template

#include <bits/stdc++.h>
using namespace std;
const int dx[]={1,0,-1,0,1,-1,-1,1};
const int dy[]={0,1,0,-1,1,1,-1,-1};
const int INF = 1<<30;
const int EPS = 1e-8;
#define PB push_back
#define mk make_pair
#define fi first
#define se second
#define ll long long
#define reps(i,j,k) for(int i = (j); i < (k); i++)
#define rep(i,j) reps(i,0,j)
#define MOD 1000000007
typedef pair<int,int> Pii;
typedef vector<int> vi;
typedef vector<vi> vvi;

1問目

minとるだけ

int main(){
	int A,B,C,D,P;
	cin >> A >> B >> C >> D >> P;
	int X = P*A;
	int Y = B;
	if(P > C){
		int Z = P-C;
		Y += Z*D;
	}
	cout << min(X,Y) << "\n";		
	return 0;
}

2問目

問題文の通りにシミュレート

int target[128];
int score[128];
int main(){
	int N;
	int M;
	cin >> N >> M;
	rep(i,M){
		cin >> target[i];
	}
	rep(i,M){
		int miss = 0;
		rep(j,N){
			int tmp;
			cin >> tmp;
			if(tmp == target[i]){
				score[j]++;
			}
			else miss++;
		}
		score[target[i]-1]+=miss;
	}
	rep(i,N){
		cout << score[i] << "\n";
	}
	return 0;
}

3問目

言われた通りに書くだけ.
自分の直前の'c'の位置を持つと引くだけになる.

string stage[128];
int main(){
	int H,W;
	cin >> H >> W;
	rep(i,H){
		int bef = -1;
		cin >> stage[i];
		rep(j,W){
			if(stage[i][j] == 'c'){
				printf("0");
				bef = j;
			}
			else{
				if(bef == -1){
					printf("-1");
				}
				else{
					printf("%d",j-bef);
				}
			}
			printf("%c",j == W-1?'\n':' ');
		}
	}
	return 0;
}

4問目

i番目の町にj日目に来た時の疲労の最小値みたいな感じでdp
再帰でかくとチョー楽

int N,M;
int distnce[1024];
int weather[1024];
int memo[1024][1024];
int solve(int index,int day){
	if(day == M){
		if(index == N)return 0;
		return INF;
	}
	if(memo[index][day])return memo[index][day];
	int ans = INF;
	ans = min(solve(index,day+1),solve(index+1,day+1)+weather[day]*distnce[index]);
	return memo[index][day] = ans;
}
int main(){
	cin >> N >> M;
	rep(i,N){
		cin >> distnce[i];
	}
	rep(i,M){
		cin >> weather[i];
	}
	printf("%d\n",solve(0,0));
	return 0;
}

5問目

はじめ,パッとした解法浮かばなかったので,シミュレートしたら1個だけ通った.
そのあと考えたら(x,y)にくる波が来た回数をメモっておいて,それが城の耐久度分きたらそこに,
波を生成すればいい.
BFSの要素にx,yに加えて,何回目の波かを持っておけば勝ち.

char stage[1024][1024];
class data{
public:
	int y;
	int x;
	int cnt;
	data(){}
	data(int _y,int _x,int _cnt){
		y = _y;
		x = _x;
		cnt = _cnt;
	}
};
int memo[1024][1024];
int main(){
	int H,W;
	cin >> H >> W;
	queue < data > Q; 
	rep(i,H){
		cin >> stage[i];
		rep(j,W){
			if(stage[i][j] == '.'){
				Q.push(data(i,j,0));
			}
		}
	}
	int ans = 0;
	while(!Q.empty()){
		data d = Q.front();Q.pop();
		rep(i,8){
			int ny = d.y + dy[i];
			int nx = d.x + dx[i];
			if(ny < 0 || ny > H-1 || nx < 0 || nx > W-1)continue;
			memo[ny][nx]++;
			if(memo[ny][nx]==stage[ny][nx]-'0'){
				Q.push(data(ny,nx,d.cnt+1));
				ans = max(ans,d.cnt+1);
			}
		}
	}
	printf("%d\n",ans);
	return 0;
}

6問目

わからん.
全探索だと3^Nが生えてくる.
1部分点取れるコード.

半分全列挙でやるといいらしいが今日はもう眠いのでまた今度.

typedef pair<ll,ll> Pll;
int N;
ll D;

vector < Pll > data;
ll solve(int dep,Pll Anna,Pll Bruno){
	if(dep == N){
		if(abs(Anna.fi - Bruno.fi) <= D)return Bruno.se-Anna.se;
		return -INF;
	}
	ll ans = -INF;
	
	ans = max(ans,solve(dep+1,mk(Anna.fi+data[dep].fi,Anna.se+data[dep].se),Bruno));
	ans = max(ans,solve(dep+1,Anna,mk(Bruno.fi+data[dep].fi,Bruno.se+data[dep].se)));
	ans = max(ans,solve(dep+1,Anna,Bruno));
	return ans;
}
int main(){
	cin >> N >> D;
	rep(i,N){
		ll x,y;
		cin >> x >> y;
		data.PB(mk(x,y));
	}
	printf("%lld\n",solve(0,mk(0,0),mk(0,0)));	
	return 0;
}

後輩は4人くらい通りそうな勢いらしい.
個人的にボーダーは380かなと言う感じ.

それでは.