2019-02-11

JOI18/19本選参加記

モチベーションが尽きて、1ヶ月間ほぼ何もしていなかったので、春合宿は絶望だと思っていたけど、まあその通りになった。悲しいね。ミリシタも2500位割って悲しいね。2月上旬を華麗に無駄にしたね。

f:id:kakakakaneko:20190211203714p:plain — 1か月ほぼ何もしていない図

f:id:kakakakaneko:20190211204111j:plain — 2500位を割った図

1日目

午前

学校がありました。雪が積もると、庭園が大変美しくお化粧なさるので、つくばエクスプレス止まるのこわいな～、でも雪積もんねぇかな～、みたいな気持ちだった。下は1年前の写真。

f:id:kakakakaneko:20190211205358j:plain — きれい

f:id:kakakakaneko:20190211205518j:plain — イイ感じに撮れたとりくん

結局、強く降ったのは一瞬で残念。

お昼ごはん

何時に会場に着けばいいか知らなかったから、たんちゃんと悪商人についていくことにした。そしたら、けいだろうさんとBwambocosさんと昼飯を食べるそうだったので、お邪魔した。北千住のデニーズに入った。席が空いててよかった。僕と悪商人がハンバーグカレードリア、残り3人はカルボナーラ。優柔不断かつ頭が回っていなかったので、悪商人をカルボナーラ4人でハブるという選択肢が思いつかなかった、反省。

ばぁ pic.twitter.com/W0OhO6LOpb
— かねしゅん🐈 (@kakakakaneko) February 9, 2019

北千住～つくば

そこそこお腹を満たしたので、つくばに向かって出発。人生初つくばエクスプレス。速かった。ずっとミリシタをしていた気がする。こいつ何しに来てるんだ。

pic.twitter.com/VKC0NxZmCM
— かねしゅん🐈 (@kakakakaneko) February 9, 2019

つくばにつくば

つくばにつくばをして改札を出ると、スーツケースやらなんやらでかい荷物を持った人が何人かいたので、多分僕らと同じやろ、ということでついていくことに。尾行。下は尾行途中に写り込んできたけいだろうさん。

pic.twitter.com/mzg7aF7FOl
— かねしゅん🐈 (@kakakakaneko) February 9, 2019

少し歩いて、なんちゃらかんちゃらという会場に着いた。名前を忘れた。僕以外4人の集合写真を撮った。エスカレーターに乗っている方から白い目で見られていた気がする。

プラクティス～夜ごはん

pic.twitter.com/hE8BnmlQ37
— かねしゅん🐈 (@kakakakaneko) February 9, 2019

2時間5問で本選環境に慣れる。Geanyというやつが簡単だと聞いていたので使った。パソコンが苦手なので普段使わないやつだと大体険しい。2問目をちゃんと読まずにWAを出したらしい。漁師さんが前川みくさんを持ってきていたのを後ろから見て、すげーとなっていた。僕はカワウソを持ってこようとして、鞄に入らず断念した。でかいんだよな、お前な。

f:id:kakakakaneko:20190211214106j:plain — 7~8年前に買ったカワウソくん

その後講義があったような気がする。色んなところからまさかりが飛んでいるのが面白かった。

そんで立食パーティーがあった。写真撮り忘れ、反省。油ものが多くて、3皿とデザートでギブアップした。あと、飯の量に対して、絶望的に水分が足りていないと思う。これアンケートに書いておけばよかった、後悔。

独房入り

9時前に着いたので、各人が「みんなのプロコン」に参加するか風呂に入るか迷っていた。僕はミリシタを走る以外道がなかったので、風呂に入った。先輩が浴槽で泳いでいた。

pic.twitter.com/OslXx51NIZ
— かねしゅん🐈 (@kakakakaneko) February 9, 2019

暖房調節できないとか去年見たけど、最初から稼働していなかったし、割に部屋が暖かかったので、小窓をおーぺんしていた。ベッドメイキングはせず、毛布も被らずに寝たけど、凍死することはなかった。非常に快適。僕は普段布団で寝ているので、ベッドも新鮮で、独房なのは見た目だけだなぁと感じた。

夜

風呂を出てから、ずっとずっとずっと部屋でミリシタを続ける。これはある意味独房なのかもしれない。廊下はときたま誰かが騒いでいらして、面白かった。やが君6巻が素晴らしいみたいな話が外から聞こえてきた時が一番面白かった。6巻の後から電撃大王を買い始めたので、7巻やべぇことになるよ、とマウントを取りたい気持ちになる人間の屑。朝まで起きようか悩んだけど、体が持たないと思ったので1時前には寝た。パソコンで「リズと青い鳥」のサントラを流しながら寝た。音漏れてたらごめんなさい。翌日、電池が切れていた、充電をサボった罰、反省。

外からやが君6巻うんたらかんたらって聞こえてきて面白かった
— かねしゅん🐈 (@kakakakaneko) February 9, 2019

2日目

朝ごはん

もりもり食って元気を回復する。みそ汁のもやし、結構イケるなぁと思った。

おいしかった pic.twitter.com/jbWXb8U2ET
— かねしゅん🐈 (@kakakakaneko) February 9, 2019

本選競技

1問目誤読20分近くかけてしまった。ダメ。2問目、50点分のDPがすぐに浮かぶので書く。満点が浮かばない。えー。永遠にDPの高速化を考える。これがダメだった。3問目の自明部分点を取りに行く。WA。は？もうええわバーカ。4問目の自明bitDPを書く。8点。うれしー。2問目に舞い戻る。何も浮かばない。もうしーらね！ｗ。5問目の自明探索を書く。1ケースWA？？？？？？。ちょっと改善したら直って4点。しゅーりょー。

終わったら解析タイム。ボーダー高そー。わー。競プロやってない同級生に負けた。わー。先輩4問目通してる。えぇ。。。

昼ごはん

梅干しを　お久しぶりに　食べました　　　かねこ

お昼あげわすれ pic.twitter.com/FYDP4TBFwh
— かねしゅん🐈 (@kakakakaneko) February 10, 2019

同時に点数をもらいました。

だめ pic.twitter.com/8zDvl2eh86
— かねしゅん🐈 (@kakakakaneko) February 10, 2019

解説

3，4問目の解説で半寝でした。首を切ります。5問目が、集合の末尾になんちゃらかんちゃら～、の辺りから理解の範疇を超えていて、逆に面白かった。

家路

ミリシタを　続けるつくば　エクスプレス　　　かねこ
最後の5時間、人生で屈指の熱さのデッドヒートを繰り広げたけど負けた。下の嘆き、失礼ながら部分点を取らなかったことで春に落ちた人の嘆きに似ているなぁと思う。もっといろんな人と交流したかったと後悔したりしなかったり。

後10分あればセーフだった感があるのよもおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおお
— かねしゅん🐈 (@kakakakaneko) February 10, 2019

感想

なんだかんだ楽しかったし、来年はもう少し万全の状態で挑みたい。また熱が戻ってきたら、のほほんと頑張りたいと思います。（完）

2018-12-09

JOI2018/2019予選参加記

520点。そこそこ相性がよかったので楽だった（実装はボロボロでしたが）

1問目：ソーシャルゲーム
Cの制約見えてなくて1WA。何やってるんだ。

#include "bits/stdc++.h"

using namespace std;
using ll=long long;
using ull=unsigned long long;

typedef pair<int,int>Pi;
typedef pair<long long,long long>P;
typedef pair<long long,P>PP;
typedef pair<P,P>PPP;

const long long MOD=1e9+7;
const long long INF=5e18;
const int di[4]={1,0,-1,0};
const int dj[4]={0,1,0,-1};

#define fr first
#define sc second
#define pb push_back
#define eb emplace_back
#define ALL(x) (x).begin(),(x).end()


int a,b,c;

void input(){
	cin>>a>>b>>c;
	return;
}

void solve(){
	for(int i=1;i<=1000000;i++){
		if(i%7==0)c-=b;
		c-=a;
		if(c<=0){
			cout<<i<<endl;
			return;
		}
	}
	return;
}

int main(){
	input();
	solve();
	return 0;
}

2問目：すごろくと駒
1問目より楽...?

#include "bits/stdc++.h"

using namespace std;
using ll=long long;
using ull=unsigned long long;

typedef pair<int,int>Pi;
typedef pair<long long,long long>P;
typedef pair<long long,P>PP;
typedef pair<P,P>PPP;

const long long MOD=1e9+7;
const long long INF=5e18;
const int di[4]={1,0,-1,0};
const int dj[4]={0,1,0,-1};

#define fr first
#define sc second
#define pb push_back
#define eb emplace_back
#define ALL(x) (x).begin(),(x).end()


int n,m,a[1010],b[1010];

void input(){
	cin>>n;
	for(int i=0;i<n;i++)cin>>a[i];
	cin>>m;
	for(int i=0;i<m;i++)cin>>b[i];
	return;
}

void solve(){
	a[n]=2020;
	for(int i=0;i<m;i++){
		if(a[b[i]-1]+1==a[b[i]])continue;
		a[b[i]-1]++;
	}
	for(int i=0;i<n;i++){
		cout<<a[i]<<endl;
	}
	return;
}

int main(){
	input();
	solve();
	return 0;
}

3問目：マルバツスタンプ
適当な貪欲を書くと通る。(番兵の意味とは)

#include "bits/stdc++.h"

using namespace std;
using ll=long long;
using ull=unsigned long long;

typedef pair<int,int>Pi;
typedef pair<long long,long long>P;
typedef pair<long long,P>PP;
typedef pair<P,P>PPP;

const long long MOD=1e9+7;
const long long INF=5e18;
const int di[4]={1,0,-1,0};
const int dj[4]={0,1,0,-1};

#define fr first
#define sc second
#define pb push_back
#define eb emplace_back
#define ALL(x) (x).begin(),(x).end()


int n,ans;
bool flx,flo;
string s;

void input(){
	cin>>n>>s;
	s+='$';
	return;
}

void solve(){
	for(int i=0;i<n;i++){
		if(!flx&&s[i]=='X')flx=true;
		if(!flo&&s[i]=='O')flo=true;
		if(flx&&flo){
			flx=false;
			flo=false;
			ans++;
		}
	}
	cout<<ans<<endl;
	return;
}

int main(){
	input();
	solve();
	return 0;
}

4問目：日本沈没
島が分断されるか、消えるかを見て足し引きすればよし。座圧して、高さが低い順に島を見たときに、両隣りが沈んでいるか、まだ残っているか、否かで場合分けしていけばOK。

#include "bits/stdc++.h"

using namespace std;
using ll=long long;
using ull=unsigned long long;

typedef pair<int,int>Pi;
typedef pair<long long,long long>P;
typedef pair<long long,P>PP;
typedef pair<P,P>PPP;

const long long MOD=1e9+7;
const long long INF=5e18;
const int di[4]={1,0,-1,0};
const int dj[4]={0,1,0,-1};

#define fr first
#define sc second
#define pb push_back
#define eb emplace_back
#define ALL(x) (x).begin(),(x).end()


int n,a[100010],ans,cnt;
vector<int>v;
vector<int>it[100010];
bool deep[100010];

void input(){
	cin>>n;
	v.eb(0);
	for(int i=0;i<n;i++){
		cin>>a[i];
		deep[i]=true;
		v.eb(a[i]);
	}
	sort(ALL(v));
	v.erase(unique(ALL(v)),v.end());
	for(int i=0;i<n;i++){
		int num=lower_bound(ALL(v),a[i])-v.begin();
		it[num].eb(i);
	}
	return;
}

void solve(){
	for(int i=0;i<v.size();i++){
		for(int j=0;j<it[i].size();j++){
			int now=it[i][j];
			if(now==0){
				if(!deep[1])cnt--;
				deep[0]=false;
			}
			else if(now==n-1){
				if(!deep[n-2])cnt--;
				deep[n-1]=false;
			}
			else{
				if(deep[now-1]&&deep[now+1])cnt++,deep[now]=false;
				else if(!deep[now-1]&&!deep[now+1])cnt--,deep[now]=false;
				else deep[now]=false;
			}
		}
		ans=max(ans,cnt+1);
	}
	cout<<ans<<endl;
	return;
}

int main(){
	input();
	solve();
	return 0;
}

5問目：イルミネーション
i番目の木を飾った時、次に飾ることができる最も近い木へ遷移するDP。どこから飾れるかは、遅延セグ木を用いて求めた。どこにも属していない木は最後にまとめて足しました。
(セグ木は長いのでカットしてあります)

#include "bits/stdc++.h"

using namespace std;
using ll=long long;
using ull=unsigned long long;

typedef pair<int,int>Pi;
typedef pair<long long,long long>P;
typedef pair<long long,P>PP;
typedef pair<P,P>PPP;

const long long MOD=1e9+7;
const long long INF=5e18;
const int di[4]={1,0,-1,0};
const int dj[4]={0,1,0,-1};

#define fr first
#define sc second
#define pb push_back
#define eb emplace_back
#define ALL(x) (x).begin(),(x).end()

int n,m;
P p[200010];
vector<ll>v;
ll a[200010],dp[200010],ans;


void input(){
	cin>>n>>m;
	v.resize(n);
	for(int i=0;i<n;i++)cin>>a[i];
	for(int i=0;i<m;i++){
		cin>>p[i].sc>>p[i].fr;
		p[i].fr--,p[i].sc--;
	}
	sort(p,p+m);
	return;
}

void solve(){
	LazySegmentTree nex(v);
	for(int i=0;i<m;i++){
		nex.update(p[i].sc,p[i].fr+1,p[i].fr+1);
	}
	for(int i=0;i<n;i++){
		dp[i+1]=max(dp[i+1],dp[i]);
		if(nex.find(i,i+1)==0)continue;
		dp[nex.find(i,i+1)]=max(dp[nex.find(i,i+1)],dp[i]+a[i]);
		ans=max(ans,dp[nex.find(i,i+1)]);
		ans=max(dp[i+1],ans);
	}
	for(int i=0;i<n;i++){
		if(nex.find(i,i+1)==0)ans+=a[i];
	}
	cout<<ans<<endl;
	return;
}

int main(){
	input();
	solve();
	return 0;
}

6問目：座席
20点だけもらった。4進数にして残っている人数を管理し、前の人が誰かを持っておきながら配列を使いまわす（メモリがきつい）。同じ国の人の並べ方は最後に階乗をかければOK。100点は知りません。

#include "bits/stdc++.h"

using namespace std;
using ll=long long;
using ull=unsigned long long;

typedef pair<int,int>Pi;
typedef pair<long long,long long>P;
typedef pair<long long,P>PP;
typedef pair<P,P>PPP;

const long long MOD=1e9+7;
const long long INF=5e18;
const int di[4]={1,0,-1,0};
const int dj[4]={0,1,0,-1};

#define fr first
#define sc second
#define pb push_back
#define eb emplace_back
#define ALL(x) (x).begin(),(x).end()

int n,a[110];
int dp[2][1100000][11];
int sum,till,ans;
int fact[40];
vector<int>v[1100000];

void input(){
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>a[i];
		sum+=a[i];
	}
	return;
}

void solve(){
	if(n>10)return;
	fact[0]=1;
	for(int i=0;i<n;i++){
		till+=fact[i]*a[i];
		fact[i+1]=fact[i]*4;
	}
	for(int i=1;i<=till;i++){
		int c=i;
		while(true){
			v[i].eb(c%4);
			c/=4;
			if(c<4){
				v[i].eb(c);
				break;
			}
		}
	}
	for(int i=0;i<n;i++){
		dp[0][till-fact[i]][i]=1;
	}
	for(int i=1;i<sum;i++){
		for(int j=1;j<=till;j++){
			for(int k=0;k<n;k++){
				if(dp[(i-1+2)%2][j][k]==0)continue;
				for(int l=0;l<n;l++){
					if(k==l||k==l-1||k==l+1)continue;
					if(l>=v[j].size())continue;
					if(v[j][l]==0)continue;
					int s=j-fact[l];
					dp[i%2][s][l]+=dp[(i-1+2)%2][j][k];
					dp[i%2][s][l]%=10007;
				}
			}
		}
		for(int j=0;j<=till;j++){
			for(int k=0;k<n;k++){
				dp[(i-1+2)%2][j][k]=0;
			}
		}	
	}
	for(int i=0;i<n;i++){
		ans+=dp[(sum+1)%2][0][i];
		ans%=10007;
	}
	for(int i=0;i<n;i++){
		while(a[i]){
			ans*=a[i];
			a[i]--;
			ans%=10007;
		}
	}
	cout<<ans<<endl;
	return;
}

int main(){
	input();
	solve();
	return 0;
}

2018-10-14

AtCoder Grand Contest 028 B - Removing Blocks

B - Removing Blocks

一つのあまりのとり忘れで黄パフォを棒に振った。以下説明。

$i$ 番目を取り除くことで、 $j$ 番目が加算されるときのことを考えます。 $i$ 番目と $j$ 番目が連結であるための条件は、 $i$ から $j$ 番目の全てのブロックが残っていることです。

次に、これらのブロックを取り除く順番を考えます。 $i$ から $j$ 番目のブロックのうち、 $i$ 番目は一番最初に取り除かれなければならず、その他は $i$ 番目のブロックが取り除かれた後であれば、いつ取り除いても構いません。

ここで、 $i-j+1$ 個のブロックを全て'x'とおくと、求めたい通り数は、

「 $N$ 個のブロックを1列に並べるとき、先頭の'x'に $i$ 番目のブロックをあてはめ、その他の'x'に残りをあてはめて並べるときの場合の数」

になります。これを求めるのは簡単で、

$\frac{N!\times abs(i-j)!}{(abs(i-j)+1)!}$

という式になります（文字を並べて、その中に特定の部分文字列が存在する場合の数っぽいもの）。簡単にすると、

$\frac{N!}{abs(i-j)+1}$

という式になります。この値については、逆元を用いて $10^{9}+7$ で割った余りを求めることができます。

後はこの通り数の計算を各ブロックについて行います。 $abs(i-j)+1$ の遷移を $N=4$ を例にして見てみると、

j=1 : 1 2 3 4
j=2 : 2 1 2 3
j=3 : 3 2 1 2
j=4 : 4 3 2 1

という感じにスライドして動いています。つまり、一番最初の和だけ求めて、後は両端だけ見ればいいです。 $O(N)$ 。自分のコードをちゃんと読もうという教訓。

Submission #3401530 - AtCoder Grand Contest 028

#include "bits/stdc++.h"

using namespace std;
using ll = long long;

const long long MOD = 1e9 + 7;

// mod m での a の逆元
ll modinv(ll a, ll m) {
	ll b = m, u = 1, v = 0;
	while (b) {
		ll t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}

ll n, ans, sum, a[100010];
ll fact = 1, ifact[100010], invcul[100010];

int main() {
	cin >> n;
	for (int i = 0;i < n;i++)cin >> a[i];
	for (ll i = 2;i <= n;i++) {
		fact *= i;//階乗を求める
		fact %= MOD;
	}
	for (int i = 0;i < n;i++) {
		ifact[i + 1] = modinv(i + 1, MOD);
		invcul[i + 1] = fact * ifact[i + 1] % MOD;
		sum += invcul[i + 1];
		sum %= MOD;//ここを忘れていた。切腹。
	}
	ans += sum * a[0] % MOD;
	for (int i = 1;i < n;i++) {
		sum -= invcul[n - i + 1];
		sum += MOD;
		sum += invcul[i + 1];
		sum %= MOD;
		ans += sum * a[i] % MOD;
		ans %= MOD;
	}
	cout << ans << endl;
	return 0;
}

2018-09-15

PCK2018予選参加記

かねこです。ほんとにただの参加記です。

結果は8完0WAでした><(8を落とした)

13:32:02　「摂氏華氏」AC。緊張で問題が読めない。

13:35:42　「赤とんぼ」AC。abs使えるか知らんかったから丁寧にやった。

13:47:51　「熱中症対策」AC。ケーキが？？？？だったので飛ばした。

13:49:50　「ケーキパーティー」AC。相方が自分が友達に含まれてないことに気づいてくれて助かった。

14:18:09　「デュ―ドニー数」AC。意味不明だったので相方に丸投げ。6,7,8問目辺りを読んでいた。

14:33:59　「ワープ装置」AC。DPだねー、ってなって、差分だけ見ればええやん、で終わった。相方に6問目を投げる。

14:58:51　「ボゾソート」AC。相方の解法聞いて、ちょっと変えて通した。こういうのきらい。

15:31:27　「直線状の点」AC。凸包とか全く関係ないこと考えてたけど、スムーズに閃けて良かった。

15:41:21　「タクシー」WA。相方が解法を出してくれたが、コーナーに気づけず、こっからずっとWAで死。ここで終わることができれば本選だった（悔しい）。

今後の課題は、実装問に弱いのをどうにかする（えでゅふぉに出て修行したい）ことと、焦らずゆっくり例外を探すことですかね...。後、WAの表示が「不正解」しかないと思って、「タクシー」がTLEしてると思ってしまったのも痛かった。蟻本からscanfの書式見つけて喜んだの、うちぐらいだと思います。

何にせよ、来年は本選目指してしっかり頑張ります。JOIも頑張ります。