JOI本選参加記・懺悔記

はい、懺悔です。
100+100+0+10+0=210
しぼんぬです。

流れ

会場に付く、人見知りフェイズ
エンターフェイズ
二階堂さんはじめいろんな人に声掛け事業してもらった。１番って受験番号は便利(^^)名刺を渡す
プラクティスフェイズ、適当に通して先輩方の輪になんとなく入り込む
部屋を確保し、夕食へ
自己紹介フェイズ、Twitterアカウントさえ言えなくて普通になってしまった
談話室、ぱない、ついてけない・・・とりあえずとざんさんあたりのユビート眺めてる
あり本たわーができてた、僕は第二版おいた

11時就寝、なかなか寝付けない、消費カロリーが少なすぎて疲れてなかったせいもあった
6時起床、この時点ではだれも起きてなかったらしい
しばらく部屋片付けてたらみんな起き始めたので流れで朝食いく
皆さん目標がぱない
いろいろぐだぐだあって本選フェイズ
一問目でさっそく躓いてあせる
とりあえず二完する
DP、サンプル通るのに・・・
昼食フェイズ
解説フェイズ、心にあるのは懺悔のみ
おわた

問題概要

一応、僕みたいにギリギリ受かるのではなく、ぎりぎり落ちてしまった人たちのために問題だけ上に。解説は後ほどで

JJOOII

J,O,Iからなる文字列Sが与えられる。Sの部分文字列のうちJがk個、Oがk個、Iがk個続いたものをレベルkのJOI列と定義した時、Sに含まれるJOI列のレベルの最大値を求めよ。

Card Game is Fun

1から1000までの数字が書かれた山が２つある。このうち片方の部分列と片方の連続部分列の一致した長さを得点としたとき、得点の最大値を求めよ。

Night Market

N個の祭りの夜店iについて楽しさ指数Aiと遊ぶのにかかる時間Biがわかっている。祭りは0時間目から始まり、T時間目に終わる。そのうちS時間目は花火があるのでここでは夜店で遊ぶことができない。ただし、開始時間または終了時間にかぶっているのは良い。夜店を番号順に回った時、得られる楽しさ指数の最大値を求めよ。

Nails

正三角形の形に釘がN行並べられており、上からa行目、左からb本目のことを(a,b)で表すとする。このときM個の輪ゴムの情報が(a,b,x)で与えられる。これは一頂点が(a,b)であるような長さxの正三角形を表す。与えられた輪ゴムを釘に張っていった時に、輪ゴムで囲まれた釘の個数を求めよ。

Festivals in JOI Kingdom

N個の街がM本の双方向に通行可能な道路で結ばれている。このうちK個の街で祭りが開催されている。このときs,tという始点と終点を表したクエリーがQ個与えられる時、sからtまでに行く全経路で通る街のうち祭りをやっているまちまでのそれぞれの距離の最小値の最大値を求めよ。

問題私解

一、二は自明な問題ですが、正解してしまっているのでちょっと後回しにします。

Night Market

DPで解こうと思いました。
変なことしました。
サンプルが通ってることに僅かな希望を抱き続けて部分点解法も書きませんでした。
しぼんぬ。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,t,s;
int a[3000], b[3000];
int dp[3001], dp2[3001]; // dp=i番目の店を使った最大値 dp2=i番目の最大値における終了時間
int main() {
    scanf("%d%d%d",&n,&t,&s);
    for (int i=0; i<n; i++) scanf("%d%d",&a[i],&b[i]);
    memset(dp, 0, sizeof(dp));
    memset(dp2, -1, sizeof(dp2));
    for (int i=0; i<n; i++) {
        for (int j=0; j<i; j++) {
            if (dp2[j]!=-1) {
                if (dp2[j]+b[i]<=t&&(dp2[j]+b[i]<=s||dp2[j]>=s)&&dp[i]<dp[j]+a[i]) {
                    dp[i]=dp[j]+a[i];
                    dp2[i]=dp2[j]+b[i];
                } else if (s+b[i]<=t&&(dp2[j]<s&&s<dp2[j]+b[i])&&dp[i]<dp[j]+a[i]) {
                    dp[i]=dp[j]+a[i];
                    dp2[i]=s+b[i];
                } else if (dp2[j]+b[i]<=t&&(dp2[j]+b[i]<=s||dp2[j]>=s)&&dp[i]==dp[j]+a[i]) {
                    if (dp2[j]+b[i]<dp2[i]||dp2[i]==-1) {
                        dp[i]=dp[j]+a[i];
                        dp2[i]=dp2[j]+b[i];
                    }
                } else if (s+b[i]<=t&&(dp2[j]<s&&s<dp2[j]+b[i])&&dp[i]==dp[j]+a[i]) {
                    if (s+b[i]<dp2[i]||dp2[i]==-1) {
                        dp[i]=dp[j]+a[i];
                        dp2[i]=s+b[i];
                    }
                }
            }
        }
        if (dp[i]<a[i]&&b[i]<=s&&(dp2[i]>b[i]||(dp2[i]==-1&&b[i]<=t))) {
            dp[i]=a[i];
            dp2[i]=b[i];
        } else if (dp[i]<a[i]&&b[i]>s&&(s+b[i]<dp2[i]||(dp2[i]==-1&&s+b[i]<=t))) {
            dp[i]=a[i];
            dp2[i]=s+b[i];
        }
    }
    // for (int i=0; i<n; i++) printf("%d%c",dp[i],i==n0?'\n':' ');
    printf("%d\n",*max_element(dp, dp+n));
}

Nails

わからないのでシュミレーションしました。10点。

#include <cstdio>
#include <set>
#include <map>
#include <algorithm>
using namespace std;
typedef pair<int, int> P;
typedef pair<P, int> PP;
int n,m;
set<PP> loop;
int solve() {
    int res=0;
    for (int i=1; i<=n; i++) {
        for (int j=1; j<=i; j++) {
            for (set<PP>::iterator it=loop.begin(); it!=loop.end(); it++) {
                int a=(*it).first.first, b=(*it).first.second, x=(*it).second;
                if (a<=i&&i<=a+x) {
                    if (b<=j&&j<=b+(i-a)) {
                        res++;
                        // printf("%d %d %d %d %d\n",a,b,x,i,j);
                        break;
                    }
                }
            }
        }
    }
    return res;
}  
int main() {
    scanf("%d%d",&n,&m);
    for (int i=0; i<m; i++) {
        int a, b, x; scanf("%d%d%d",&a,&b,&x);
        loop.insert(make_pair(P(a,b),x));
    }
    printf("%d\n",solve());
}

Festivals in JOI Kingdom

祭りまでの最小値をすべての街で出しておくことはすぐ思いつきました。
Dijkstra書きました。
デバックしたらなんか正しく求められてません。
Dijkstraって閉路だめだっけ？っていう意味分からない思想
ベルマンフォード書く。
なんか合わない。
このあと全域木っぽくして解けるかな〜と思いつつ祭りへの距離が求められなかったのでできませんでした。
No Submit

JJOOII

続く文字の個数で表したRun-Length圧縮という名前は知らなかったけど、似たものをhosさんいわくバグを埋め込みやすい方法でやった。

#include <cstdio>
#include <climits>
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
void init(int *cnt) {
    for (int i=0; i<3; i++) cnt[i]=0;
}
int me(int *cnt) {
    int res=INT_MAX;
    for(int i=0; i<3; i++) res=min(res,cnt[i]);
    return res;
}
bool isok(int *cnt) {
    if (cnt[0]>=cnt[1]&&cnt[1]<=cnt[2]) return true;
    return false;
}
int cnt[3];
int main() {
    string in;
    cin>>in;
    int res=0;
    char flag='*';
    for (int i=0; i<in.length(); i++) {
        if (flag=='*'&&in[i]=='J') {  // J task start
            init(cnt);
            flag='J';
            cnt[0]++;
        } else if (flag=='I'&&in[i]=='J') {
            if (isok(cnt)) res=max(res,me(cnt));
            flag='J';
            init(cnt);
            cnt[0]++;
        } else if (flag=='J'&&in[i]=='J') {
            flag='J';
            cnt[0]++;
        } else if (flag=='O'&&in[i]=='J') { // J task end
            flag='J';
            init(cnt);
            cnt[0]++;
        } else if (flag=='J'&&in[i]=='O') { // O task start
            flag='O';
            cnt[1]++;
        } else if (flag=='O'&&in[i]=='O') {
            flag='O';
            cnt[1]++;
        } else if (flag=='I'&&in[i]=='O') { // O task end
            if (isok(cnt)) res=max(res,me(cnt));
            flag='*';
        } else if (flag=='O'&&in[i]=='I') { // I task start
            flag='I';
            cnt[2]++;
        } else if (flag=='I'&&in[i]=='I') {
            flag='I';
            cnt[2]++;
        } else if (flag=='J'&&in[i]=='I') { // I task end
            flag='*';
        }
        // for (int j=0; j<3; j++) printf("%d%c",cnt[j],j==2?'\n':' ');
   }
   if (flag=='I'&&isok(cnt)) res=max(res,me(cnt));
   printf("%d\n",res);
}

Card Game is Fun

どちらの山を固定するかで考えた。
最初任意の引きかたができる方を考慮してみたが当然場合の数が多すぎてNG。
次もう片方を単純に固定する・・・はずがなんか任意の引きかたが出来る方でループ回し、もう片方の見つかったところから固定して求めるというわけわからないことをした。
結局O(AB)と正解と同じオーダーなので結果おーらい。

#include <cstdio>
#include <algorithm>
using namespace std;
int an, bn;
int a[5000], b[5000];
int c(int num, int s) {
    for (int i=s; i<an; i++) {
        if (a[i]==num) return i;
    }
    return -1;
}
int main() {
    scanf("%d%d",&an,&bn);
    for (int i=0; i<an; i++) scanf("%d",&a[i]);
    for (int i=0; i<bn; i++) scanf("%d",&b[i]);
    int res=0;
    for (int i=0; i<an; i++) {
        for (int j=0; j<bn; j++) {
            if (a[i]==b[j]&&j==bn-1) {
                res=max(res, 1);
            } else if (a[i]==b[j]) {
                int pos=j+1, s=i+1;
                while (true) {
                    int ans=c(b[pos],s);
                    if (ans==-1) {
                        res=max(res,pos-j);
                        break;
                    } else {
                        pos++;
                        s=ans+1;
                    }
                }
            }
        }
    }
    printf("%d\n",res);
}

問題解説

JJOOII

ほとんど僕の解法と同じ。
バグを発生しにくいようにRun-Length圧縮を最初に一通り作ってそれをなめてもオーダーは同じ。

Card Game is Fun

私解のところでも述べたが、僕の気持ち悪いコードは別にして、単純に連続部分列を固定してもう片方を探索でO(AB)
DPでもできるらしい。

Night Market

ナップザック拡張版。といってもさほど難しい拡張ではなくsを跨ぐようなときだけ飛ばせばいい。
普通に考えればできた。

Nails

累積和と最大値の伝搬の２つのやり方がある。
最大値の伝搬は正直頭よすぎて、それぞれの上の頂点に長さを持っておいた時、自分＝max(自分、max(左上、右上)-1)とするとその行を含めた下何行が輪ゴムに囲まれているかという情報になるのでこれを更新していき、0で無いところを数えればよいというもの。
累積和は多少の説明要

普通に累積和を計算するとシュミレーションとさほど変わらないので、まず四角形に簡略化して累積和のテクニックを。
とりあえず上の図みたいにそれぞれの枠の左上隅とか特徴的なところに数値を持っておく。すると横一列に1足していけば-1まで単純ループ、その後今度は縦にみてやっぱり足していくと累積和できちゃうよ的なぱない工夫。
これをこの問題ではさらに応用して、正三角形は四角形を階段型に切ったものに帰結するからさっきと同じテクニックをまず適用する。でも横・縦だけだと計算できないのでまず斜め方向に操作してから横・縦ってやるとできるらしい。
正直性にあうのは最大値の伝搬だけどしょっちゅう思いつくとも他の問題で使えるとも思わないから累積和のことはまたいずれ勉強しなきゃならない。

Festivals in JOI Kingdom

まぁ最初にDijkstraでお祭りまでの各街の最短距離を出しておく。これを各街のコストとする。
このコストを辺に見立ててDijkstraもう一回やったり、スコアの大きい順ソートしてUnion-Find木で単純にやると10点。
Union-Find木を使うときに、全域木的に構築していけば最後に加えたスコアがすなわち答えになるという考え方で30点。
そして満点解法ですが、いろいろあるらしいですが一応iwiさんが解説したやつ。単純に表すと以下