JOI本選参加記 - ド素人のメモ帳

JOI予選を４完＋部分点でAランク取れたのでJOI本選に行って来ました。
JOI本選通ってしまったということでそれまでの期間、意識高い顧問からの課題をこなす日々を過ごした。
一応自分でもAOJのVolume 5は全部解こうと目標立ててたのに結局４問ほど残ってしまう意識の低さで当日を迎えてしまった。

2/9(土)

集合時間が12時くらいなので9時ぐらいまでゆっくり睡眠をとり、11時半くらいに家を出る。
新幹線では昼食を食べ、同じ学校の@public_sateが横で爆睡してる中蟻本を読みながら意識高いふりをしながら東京へ向かった。

去年の本選では0完太陽が生えたので今年は絶望しないように明治神宮でお祈り。
おみくじには、「糸を解こうとして間違って糸口を見失うと、もつれもつれて、ついには解きほぐす方法を失う」みたいなこと書かれてて絶望。

3時過ぎ頃、プラクティスの会場へ到着。
顧問の知り合いの先生が僕のAOJのID知っててマークされてるらしく怖い
会場では、EPOCHの参加者など知ってる人がいたので去年のような悲しみは背負わずにすんだ。
問題は、やるだけと過去問だったので適当に解いて、乱数を吐く奴書いて負荷をかけて遊んでいた。

夕食は去年より品数が多かったように思う。覚えていない
自己紹介では、去年と同じようにTwitterアカウント晒しが始まってた。
Twitter昨日はじめた人やハラスメンターの方々が怖かった（小並感）
名刺交換タイムは毎回作ってこようと思っていて忘れてしまっているので見学

夜は談話室で他の学校の人と交流。
「実用がメインで競技はおまけです。去年は適当にやったら合宿いけました」などというハラスメントを受けて精神を傷つけられる。
魔理沙のコスプレをした人が、男性だということにかなり後半で気付く。言われなければ気付かない。
実用プログラムの怖い話を聞きながら、23時半までなのに23時頃風呂に向かい、日付が変わってから寝た。

2/10(日)

緊張してるせいか5:30→5:45→6:00を起床とn度寝を繰り返す。

朝食は高専の方々と食べた。EPOCHで一発街で盛り上がったように、今回は大浴場で盛り上がった。
笑いすぎて疲れて本選のこと忘れた。

8:30チェックアウトなのに8:30に宿泊棟を出る屑

待合室では、4問目にsegment木が出るそうなので蟻本読む……がわからん
座標圧縮とかLCAのページパラパラ見ながら時間を潰してるといつの間にか時間になってた。

入り口で綾鷹をもらい、競プロには炭酸がいいと何処かで聞いたのでccレモンを買って本線に望む。

1問目　電飾
緊張のあまり謎の解法で解いてバグる。
チグハグになってるとこを前後で3つ足せばいいことに20分ぐらいたってから気付く。

100/100

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
int n;
int a[1111111];
vector<int> v;
int main(void){
  scanf("%d",&n);
  int best = -1;
  int c = 0;
  int tu;
  int f=2;
  for(int i = 0; i < n; i++){
    scanf("%d",a+i);
  }
  for(int i = 0; i < n; i++){
    //printf("a:%d:%d\n",i,a);
    if(f != a[i]){
      f = a[i];
      if(!c) tu = i;
      c++;
    }else{
      v.push_back(c);
      f = 2;
      i--;
      c = 0;
    }
  }
  if(c) v.push_back(c);

  for(int i = 0; i < (int)v.size(); i++){
    //printf("v[%d] = %d\n",i,v[i]);
    int t = v[i];
    if(i) t += v[i-1];
    if(i+1 < (int)v.size()) t += v[i+1];
    best = max(best,t);
  }
  printf("%d\n",best);
}

2問目　IOI 列車で行こう
1問目遅くなったので問題文雑に読み解き始める。
stack使いそうとか思ったけど全然関係なかった。
・いくつか捨てられる事を忘れる。
・最後'I'でなくてはならないのを忘れる。
・一番最初しか捨てられないのを忘れる。
dp書いて気付いて直して気付いて…を繰り返したのでゴリ押し感がパない。
おみくじ通り間違ってると思ったらすぐ解法考えなおすようにしたのでなんとかいけた
40分ぐらいかかった気がする。

100/100

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <iostream>
using namespace std;
int n,m;
string s,t;
string io = "IO";

int dp[2][2002][2002];
int solve(int f,int a,int b){
  if(dp[f][a][b] >= 0) return dp[f][a][b];
  if(a == n && b == m) return f?0:-444444;

  int res = -1;
  if(a < n && io[f] == s[a]) res = max(res,solve((f+1)%2,a+1,b)+1);
  if(b < m && io[f] == t[b]) res = max(res,solve((f+1)%2,a,b+1)+1);
  /*
  if(a < n) res = max(res,solve(f,a+1,b));
  if(b < m) res = max(res,solve(f,a,b+1));
  */
  if(res == -1) return f?0:-444444;
  return dp[f][a][b] = res;
}

int main(void){
  cin >> n >> m >> s >> t;
  int res = 0;
  memset(dp,-1,sizeof(dp));
  for(int i = 0; i <= n; i++){
    for(int j = 0; j <= m; j++){
      res = max(res,solve(0,i,j));
    }
  }
  cout << res << endl;
}

3問目　現代的な屋敷
制限見てやばそう
とりあえずスイッチのある場所だけ考えればいいことに気付く。
おもむろにdp書き始める。サンプル微妙にバグって冷える。
12:00ぐらいで閉路であることに今更気付き絶望
ココらへんでccレモンが猛威を振るってきたのでトイレにいく
おみくじさんのおかげでDijkstraだと気付く。
解いてる途中5回ぐらいUbuntu壊れる（ctrl押しっぱなしの状態になる）

「時間超過1 (80)」絶望

辺おおすぎるからなぜかMLEだと思う
Dijkstraを信じすぎていたためTLEは全く疑わない
なぜかpriority_queueをただのqueueに直す
なぜか「時間超過1 (80)」

終わり際にDijkstraがO(ElogV)だったの気づくがもう遅かった。

80/100

ソースで時折char型が出てくるのはMLEだと思ってた時の名残

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#define F first
#define S second
#define INF (((ll)1<<20)<<20)
using namespace std;
typedef long long ll;
struct P{
  ll x,y;
};
ll n,m,k;
vector<ll> ix[111111];
vector<ll> iy[111111];
P s[222222];
ll d[2][222222];
bool flag;
int main(void){
 scanf("%lld %lld %lld",&m,&n,&k);
  k++;
  for(int i = 1; i < k; i++){
    ll x,y;
    scanf("%lld %lld",&x,&y);
    //if(x == 1 && y == 1) flag = true;
    P p = {x,y};
    s[i] = p;
    ix[x].push_back(i);
    iy[y].push_back(i);
  }
  P p = {1,1};
  s[0] = p;
  ix[1].push_back(0);
  iy[1].push_back(0);
  P q = {m,n};
  s[k] = q;
  ix[m].push_back(k);
  iy[n].push_back(k);

  priority_queue< pair<ll,pair<char,int> >, vector< pair<ll,pair<char,int> > > ,greater< pair<ll,pair<char,int> > > > que;
  //priority_queue< pair<ll,pair<char,int> > > que;
  //queue<pair<ll,pair<char,int> > > que;
  fill(d[0],d[0]+k+1,INF);
  fill(d[1],d[1]+k+1,INF);
  que.push( make_pair(0,make_pair(0,0)) );
  d[0][0] = 0;
  while(!que.empty()){
    ///*
    ll c = que.top().F;
    char f = que.top().S.F;
    int p = que.top().S.S;
    //*/
    /*
    ll c = que.front().F;
    char f = que.front().S.F;
    int p = que.front().S.S;
    */
    //printf("(%lld,%lld)\n",s[p].x,s[p].y);
    que.pop();
    if(d[f][p] < c) continue;
    if(p && d[(f+1)%2][p] > c+1){
      d[(f+1)%2][p] = c+1;
      que.push(make_pair(c+1,make_pair((f+1)%2,p)));
    }
    if(!f){
      for(int i = 0; i < (int)ix[s[p].x].size(); i++){
	ll q = ix[s[p].x][i];
	if(d[f][q] <= d[f][p] + abs(s[p].y-s[q].y)) continue;
	d[f][q] = d[f][p] + abs(s[p].y-s[q].y);
	que.push(make_pair(d[f][q],make_pair(f,q)));
      }
    }else{
      for(int i = 0; i < (int)iy[s[p].y].size(); i++){
	ll q = iy[s[p].y][i];
	if(d[f][q] <= d[f][p] + abs(s[p].x-s[q].x)) continue;
	d[f][q] = d[f][p] + abs(s[p].x-s[q].x);
	que.push(make_pair(d[f][q],make_pair(f,q)));
      }
    }
  }
  ll res = min(d[0][k],d[1][k]);
  if(res >= INF) puts("-1");
  else printf("%lld\n",res);
}

4問目　JOIOIの塔
よく分からん嘘貪欲を書く。サンプル通ったので何故かいけると思う。
制限見てO(n)であるこの解法は絶対違うだろ！と気付く
が解き方分からんので諦め

0/100

5問目　バブルソート
この問題蟻本でやった問題だ！！！
と思い何も考えずBIT書く。
書いてる途中にO(n^3logn)でこれダメじゃね？と思う。
別解法思いつかないので提出

0/100

結果

280/500

部分点全然取れなくて悲しい。
トイレに行きたくなる飲み物は良くない。2回行った
どっかで合宿いくのには3完+部分点と聞いていたので絶望してた

昼食は、競技終わったあとなのにカツカレーで英気を養う。
4問目部分点は前日の夜、他の人に偉そうに「n=15位だったらbitDPだと思えばいいよ（笑）」とか言っていたので恥ずかしくて死にそうだった

解説は、全部わかりやすくてとても良かった（5問目は例外）。
5問目は解説はすごい丁寧でわかりやすいんだろうけど、後半ちょっと何行ってるかわからなかった。激ムズ
3問目満点はなぜ気付かなかったか自分を責める。
4問目は頭良いなと思った

時間が遅れて、電車がやばかったのでろくに挨拶もせず帰ってしまったのがちょっと後悔
なにはともあれ、今年のJOIはとても楽しかったです

2/11に送られてきたメールでAランクだったとわかったので合宿いけるそうです。
皆さんよろしくお願いします！