2021/10/24に開催された模擬国内予選にチームAobayama_dropoutで参加しました。今年はメンバーに変更があり、碧黴さんが一足先に引退されて新たにha15さんが加わりました。つまり、ゆきのんさん・ha15さん・僕です。碧黴さんはコーチとして関わってくださいます。

昨年の参加記を読むと、どうやら当時は部室にチームで集まって参加したようですが、今年は完全にオンラインでした。ツールはSlackとHackMDを用意したものの、僕が一人で考察を抱え込んでしまい、HackMDのほうはあまり活用できませんでした。国内予選本番では集まりたいと思っていますが、どうなるんでしょう。今年のICPC準備は新サークル長に任せて、自分はあまり口出しをしていないので、参加場所の確保がどうなるか・そもそも確保されるかがわかりません。

ha15さんは用事があって今日不参加とのことで、ゆきのんさんと2人でコンテストに臨みます。特に何も相談をしていませんでしたが、僕は初めにB問題を読むことにしました。

B問題

さすがにやるだけなので、書きながら考えます。和を取る配列を用意しましたが、書いているうちに定数個の変数でよいことに気づきました。適当に割り算するとサンプルが合ったので提出作業に入ります。ここで、普段コンテストに出るときのディレクトリで作業していることに気づいたので、icpcディレクトリに移動しました。中には今年3月の横浜大会の残骸が残っており、非常に懐かしい気持ちになりましたが、コンテスト中なのでとりあえず全部削除しました。

提出するとAC、7分弱でした。

D問題

次にどの問題に進むか決めるとき、A問題を担当してくれる（と自分が勝手に思っている）ゆきのんさんの音沙汰がないことに気づきました。いないならC問題を読もうかな、と思いつつメンションを飛ばしてみると反応があったので、Dを読むことにしました。どうやらログインに少し手間取っていたそうです。

Dは文字列長が10000文字以下という微妙なサイズの制約で、テストケース50個を含めても2乗が通りそうです。何でもできる気になり、文字列の後半を見て、今何文字目まで処理したかをキーに持つdpを書くことにしました。キーと遷移がそれぞれ文字列長のオーダーなので、全体で2乗……と思っていたら、遷移のチェックをする必要があることに気づきました。幸い、Z-algorithmを遷移前に計算することでチェックを定数時間で行えるため、そのまま実装を進めます。添え字がちょっとややこしいですが、適当に書いたらサンプルが合い、そのままACしました。

1ファイル5sec弱で実行できているので、定数倍はかなり軽めのようです。22分弱でした。

コンテスト後に気づきましたが、遷移先としては最も近いインデックスのみを考えるので良いですね。manacherアルゴリズムと同様に考えると、遷移が2種類以上あるなら、長いほうの遷移は短いほうの遷移を使って2つ以上に分解できます。線形時間の解法があるようで、この事実を使うのでしょうが、~~まだ遷移を探すフェーズをどうするのかわかっていません~~この記事を書いている間に解説が公開されて理解しました。

僕がZ-algorithmでチェックしていた文字列一致は、ローリングハッシュを用いたり、あるいは文字列全体を使って接尾辞配列を作ることで、線形時間の前計算が1回で済むようになります。また遷移を探すのも、短い文字列から順に試して見つかった瞬間に更新すれば、全体で線形時間になります。

E問題

適当に読むと、例えば列の左右から貪欲にそろえていくとか、 $1$ と $N$ から貪欲にそろえていくとかが思い浮かびます。自分の勘はよさそうだと言っていたので後者を実装してみましたが、サンプルすら合いません。2つの要素を1個ずつずらすよりも、1つの要素を2個ずらすほうが安いからです。

貪欲の実装時、「移動しない」要素の処理のためにif文を書いていました。通常は移動距離 $+1$ だけコストがかかるのですが、移動しない要素はコストがかからないからです。このことを鑑みると、移動しない要素を先に決め打っておけば、あとは貪欲に操作してよいようになりそうです。これを信じて、移動しないと固定した要素の最大値をキーに持つdpを考えることにしました。

dpの遷移は、今見ている要素を新しく固定するか、あるいは左に飛ばすか、右に飛ばすかです。移動しない要素を固定している以上、残りのコストについては「飛ばす」側と「飛ばされる」側のどちらに注目して計算してもよいです。よって僕の実装では、自分より左にある自分より大きな要素の個数を数えて、dpの全ての値にコストとして加えることにしました。あとは、要素を固定しないならコストに $+1$ する、要素を固定するなら新しく値をセットする、の操作が必要で、結局区間ADD区間MINの遅延セグメント木で対応できます。

サンプルが合ってそのままAC、結構考察が難しく65分くらいでした。

書いている途中に薄々感づいていましたが、固定する要素はLISと一致し、残りのコストは転倒数のようです。固定するものがLISであると決め打ってよいのかすぐにはわからなかったので、間違いなく計算できそうな上のアルゴリズムを実装しましたが、コストを「移動距離」と「 $+1$ 」に分けて計算していることをはっきり自覚していれば、それはそうという気持ちになりました。

また、途中でゆきのんさんが書いてくれていたC問題が微妙に炎上しかけていました。僕は一読してbitDPだと感じたのですが、どうやらゆきのんさんもそれで実装していて、結構大変なようでした。単純なdfsで通らないかということを聞かれ、特に計算量を見積もれたわけではないですが通りそうだということを伝えると、しばらくして、爆速で実行が終了したということが報告されました。

F問題

問題文を読むと、dpだろうなという直感がありました。その方針で考えます。まず必要なのは0と1の個数で、これで $O(|t|^2)$ かかります。ほかに交換回数が求まるような情報を持つと安心ですが、遷移が $O(n)$ 種類あることや、交換回数が $O(|t|^2)$ くらいになりうることを考えると、これ以上dpの次元を増やせません。

しかし冷静に考えると、交換回数というのは2つの文字列における1のインデックスを取り出して、それぞれ先頭からペアにしつつ差の絶対値を足し合わせたものに他なりません。つまり、途中まで確定した文字列があったとき、それ以降どんな文字列が来るかというのは現時点での交換回数の計算に影響しないことがわかります。

このことから、交換回数を毎回求めつつ最小値を達成するもののみを保存することで、文字列が完成した時の交換回数の最小性が満たされることが言えました。さらに考えを進めると、dpの各値を達成するような文字列については辞書順で最も小さなもののみを保存しておけば、辞書順最小という性質も満たされると言えます。前半の文字列で、0と1の個数が等しいにも関わらず交換回数や辞書順に差がついていれば、後半の文字列がどう頑張っても取り返せないということです。

0と1の個数を持つ代わりに、現在構築した文字列長と1の個数を持ってdpしました。状態数は変わらず $O(|t|^2)$ 、遷移は $O(n)$ 種類で、各遷移で交換回数を求めるのにさらに $O(|S_i|)$ かかるので、だいたい100⁴になります。定数倍はかなり軽めなものの、代わりにさらにテストケース数が100個あり、手元で少し時間をかけて回しました。ただ解法に至るのがかなり速かったのでACは75分くらいでした。

解説では、文字列を後ろから構築しなければならないと書かれていましたが、その必要はありません。

G問題

問題文に全方位木dpだと書いてあったので、読んですぐ実装に入りました。実は想定解は全方位木dpではないらしく、びっくりです。

まず、各頂点に対して「親に戻ってこないときの最大値」「親に戻ってくるときの最大値」を求めました。頂点 $u$ について、それぞれ $dp_{u,0}$ と $dp_{u,1}$ とでもしておきましょう。初期値はそれぞれ $1$ で、 $u$ の子 $v$ を見ているときの更新は $dp_{u,0}\leftarrow dp_{v,0}+1$ と、x[u]=='2'のとき $dp_{u,1}\leftarrow dp_{v,1}+2$ です。 $\leftarrow$ はchmaxの意味です。

X[u]==2のとき、 $dp_{u,0}$ についてはもう少し考える必要があります。つまり、 $u$ から $v_1$ に行って、戻ってきてからさらに $v_2$ に行くようなケースがあります。後から述べるように $v_1=v_2$ であるケースが存在して今の状態では対応できませんが、当時は $v_1\ne v_2$ だと思い込んで実装していました。

とりあえず、 $v_1\ne v_2$ なる $v_1,v_2$ を選んで、 $dp_{u,0}\leftarrow dp_{v_1,1}+dp_{v_2,0}+2$ としたいです。僕は $dp_{v,1}$ のargmaxを求め、それが $v_1$ になる場合と $v_2$ になる場合をそれぞれ求めました。

あとはこれを全方位木dpにします。親から子に遷移するときの値を求める際、上の計算が邪魔をして、単純に左右から累積maxを取るだけでは対応できません。そこで、子らを区間MAXのセグメント木に乗せることにしました。ついでにargmaxも求まるようにしておけば、計算に使えない要素が遷移先の子と $dp_{v,1}$ のargmaxで2種類になっても、区間を3つ用意して調べるだけで対応できます。

実装が完了してサンプルを試すと、最後のケースだけ答えが1小さくなってしまいました。先ほども述べた通り $v_1=v_2$ となるようなケース、つまり途中で親と子を往復してまた子の先に行くというようなケースです。これに対応するため「親に戻ってこず、頂点 $u$ も1回しか通らないときの最大値」として $dp_{u,2}$ を定めました。

初期値はこれまた $1$ で、更新は $dp_{u,2}\leftarrow dp_{v,0}+1$ です。また往復するケースに相当するのは、x[u]==x[v]=='2'のときの $dp_{u,0}\leftarrow dp_{v,2}+3$ になります。 $u$ を2回、 $v$ を1回通ることになるので、 $dp_{v,2}$ では $v$ は1回しか通らないことを保証したかったのです。x[u]だけでなくx[v]も見る必要があるので、親から遷移するときに親のxも渡す必要がありましたが、全方位木dpにおける遷移の計算自体はこれまでのもののコピペで十分対応できました。

サンプルを試すと合ったのですが、提出のためデータセットを落としてくると、途中でセグフォしてしまいました。どう考えてもスタックオーバーフローです。いろいろ調べて、コンパイル時のオプションに-Wl,--stack,104857600を指定すると、ちゃんと最後まで実行されました。

できた出力ファイルを恐る恐る提出したところ、WAでした。一人黙々と実装してしまっており、このときゆきのんさんに言われてようやくコードを共有しました。

とりあえず適当なケースを試そうと思い、3頂点の直線グラフでx="222"としたケースを投げると、9が返ってくることに気づきました。初手でHackケースを引き当ててびっくりしつつ、デバッグ出力を挟んで確認してみます。 $dp$ の値は問題なく計算できていましたが、そこから全方位木dpにするにあたって、親からの遷移の値がおかしいようでした。

よくよく見ると、 $dp_{v,2}$ の値をセグメント木に乗せる際x[v]=='2'であることを確認していなかったのと、確認していても、そもそもセグメント木の初期化のため用意したvectorの中身がintのデフォルト値 $0$ になっていて、それに遷移で $+3$ するものだから、このような値になってしまったようでした。乗せるモノイドの単位元をより小さな値にして、初期化のためのvectorも作成時にその値で埋めるようにしたところ、ちゃんと正しい値である5を返すようになり、再度提出するとAC。132分でした。

残り時間はHを考えていて、 $b$ を固定した時の $a$ としてありうる値の区間幅を積分するとかそういう方向で計算していましたが、うまく区間になってくれるかもよくわからないし、適当に出した式はminなどが入っていて積分が面倒そうだったしでやりたくなさが物凄かったです。結局その後はコードも書かずコンテストが終了しました。

コンテスト終了

結果は総合・現役5位、学内1位でした。G問題がただの重実装だったので、差がつく問題がそれで望外に良い結果が出たという印象です。

立ち回りは相変わらず下手くそで、チーム戦ができていません。大体ずっと一人で問題を抱え込んでいて、今回は解けたからよかったものの、E問題などちょっと間違えば考察で詰まりかねないものは積極的に共有するべきでした。

G問題のコードを貼っておきます。ACLのsegtreeを使用します。そういえば、G問題の木の入力は各頂点の親を与えるもので、dfs呼び出しで親の頂点番号を渡す必要がなかったり、子らにインデックスを割り振るとき隣接リストから親をわざわざ抜く必要がなかったりするのが便利でした。

#include<iostream>
#include<vector>
#include<algorithm>
#include<atcoder/segtree>
using namespace std;
int N;
string X;
vector<int>G[1<<17];
int dp[1<<17][3];
void dfs1(int u)
{
    dp[u][0]=1;
    dp[u][1]=1;
    dp[u][2]=1;
    int mx2=-1;
    for(int v:G[u])
    {
        dfs1(v);
        dp[u][0]=max(dp[u][0],dp[v][0]+1);
        dp[u][2]=max(dp[u][2],dp[v][0]+1);
        if(X[u]=='2')
        {
            dp[u][1]=max(dp[u][1],dp[v][1]+2);
            if(X[v]=='2')
            {
                dp[u][0]=max(dp[u][0],dp[v][2]+3);
            }
        }
        if(mx2==-1||dp[mx2][1]<dp[v][1])mx2=v;
    }
    if(X[u]=='2'&&mx2!=-1)
    {
        int n0=0,n1=-1e9;
        for(int v:G[u])if(v!=mx2)
        {
            n0=max(n0,dp[v][0]);
            n1=max(n1,dp[v][1]);
        }
        dp[u][0]=max(dp[u][0],max(dp[mx2][1]+2+n0,dp[mx2][0]+2+n1));
    }
    //cout<<"dp["<<u<<"] = ("<<dp[u][0]<<", "<<dp[u][1]<<", "<<dp[u][2]<<")"<<endl;
}
using dat=pair<int,int>;
dat op(dat a,dat b){return a<b?b:a;}
dat e(){return make_pair(-1e9,-1);}
int ans;
void dfs2(int u,int p0,int p1,int p2,char pc)
{
    //cout<<u<<" <- ("<<p0<<", "<<p1<<", "<<p2<<")"<<endl;
    {
        int now0=max(dp[u][0],p0+1);
        ans=max(ans,now0);
        if(X[u]=='2')
        {
            int n0=0,n1=-1e9;
            for(int v:G[u])
            {
                n0=max(n0,dp[v][0]);
                n1=max(n1,dp[v][1]);
            }
            ans=max(ans,max(p1+2+n0,p0+2+n1));
            if(pc=='2')
            {
                ans=max(ans,p2+3);
            }
        }
    }
    int n=G[u].size();
    vector<dat>in0(n+1),in1(n+1),in2(n+1,e());
    in0[n]=make_pair(p0,n);
    in1[n]=make_pair(p1,n);
    if(pc=='2')in2[n]=make_pair(p2,n);
    for(int i=0;i<n;i++)
    {
        in0[i]=make_pair(dp[G[u][i]][0],i);
        in1[i]=make_pair(dp[G[u][i]][1],i);
        if(X[G[u][i]]=='2')in2[i]=make_pair(dp[G[u][i]][2],i);
    }
    atcoder::segtree<dat,op,e>P0(in0),P1(in1),P2(in2);
    for(int i=0;i<n;i++)
    {
        int np1=1;
        if(X[u]=='2')
        {
            np1=max(np1,max(P1.prod(0,i).first,P1.prod(i+1,n+1).first)+2);
        }
        int np2=max(1,max(P0.prod(0,i).first,P0.prod(i+1,n+1).first)+1);
        int np0=np2;
        if(X[u]=='2')
        {
            np0=max(np0,max(P2.prod(0,i).first,P2.prod(i+1,n+1).first)+3);
        }
        if(X[u]=='2')
        {
            dat tmp=op(P1.prod(0,i),P1.prod(i+1,n+1));
            if(tmp.second>=0)
            {
                int l=tmp.second,r=i;
                if(l>r)swap(l,r);
                np0=max(np0,tmp.first+2+max({P0.prod(0,l).first,P0.prod(l+1,r).first,P0.prod(r+1,n+1).first}));
                np0=max(np0,P0.get(tmp.second).first+2+max({P1.prod(0,l).first,P1.prod(l+1,r).first,P1.prod(r+1,n+1).first}));
            }
        }
        dfs2(G[u][i],np0,np1,np2,X[u]);
    }
}
int main()
{
    while(cin>>N,N)
    {
        cin>>X;
        for(int i=0;i<N;i++)G[i].clear();
        for(int i=1;i<N;i++)
        {
            int p;cin>>p;
            G[p-1].push_back(i);
        }
        dfs1(0);
        ans=0;
        dfs2(0,0,-1e9,0,'1');
        cout<<ans<<endl;
    }
}

kotatsugameの日記

ICPC模擬国内予選 2021 参加記

B問題

D問題

E問題

F問題

G問題

コンテスト終了