ICPC模擬国内予選 2022 参加記

2022/06/25に開催された模擬国内予選にチームAobayama_dropoutで参加しました。今年のメンバーはha15さん・ホスフィンさん・僕です。

これで5年目、ついに最後のICPCシーズンとなりました。ほとんど僕のわがままのようなものですが、ずっと「Aobayama_dropout」として参加し続けることができたのはかなり達成感があります。僕と組んでくださった計4名のチームメイトの方々に感謝します。

jag-icpc.org

ha15さんは今日不参加とのことで、模擬国内はホスフィンさんと二人で参加しました。ホスフィンさんが大学の演習室を確保してくれて、そこに集まりましたが、部屋の窓以外3方向の壁にホワイトボードが設置されていたり、大きなモニターが運び込まれていたりして、望外に快適な環境でした。

今日の序盤の戦略は、ホスフィンさんにAとBを任せ、僕はC以降を読んでいくという割り振りでした。

C問題

まず、他の文字列の省略のされ方は関係ないことがわかります。よって、各文字列に対して最良の省略方法を独立に求めるという方針が立ちました。文字列の長さの最大値を（）として、で求められれば十分間に合います。先頭から残す文字数を全探索することを考えると、それで区別できない他の文字列の集合が求まり、それらを区別するために末尾から残す必要のある文字数を計算すればよさそうです。実装としては、最初に他の文字列それぞれについて「先頭から一致する文字数」「末尾から一致する文字数」をで求めると、先頭から残す文字数を決めるごとにで決定できます。

実装し、off-by-oneエラーを修正してサンプルが合ったので提出しました。しかしWA。処理をコピペした部分で変数名が修正できていなかったところを見つけ、直し、出力が変化していることを確認して再度提出するも、これもWAでした。ここでようやく考察の抜け、最初の時点で文字数が異なる文字列はどのように省略されたとしても互いに区別できてしまうということに気づきました。上で言っていた「区別できない他の文字列の集合」を求める部分の条件にこの判定を加え、ようやくAC。13分＋2ペナかかってしまいました。

D問題

すでにA問題を通していたホスフィンさんからヘルプが来て、B問題がDPで解けることを指摘しつつ、D問題に進みました。問題の雰囲気だけからエスパーして、答えを達成するとき少なくとも1点は頂点に乗るんじゃないかと思いましたが、の制約がよくわからないのでちゃんと考えることにしました。実際これはサンプルで落ちます。

一周する時間を個の適切な区間に分割することで、それぞれの区間では各点が線分上を動くようにできます。つまり区間内では点の座標が時刻の1次式になります。それを使って三角形の面積を表現した式は、時刻の高々2次式に絶対値を付けたような形になりますから、これの最小値を求めればよいです。2次の係数の符号は式の形からはよくわかりませんが、どちらにしても区間の両端点と、でない場合に頂点を見れば十分です。実装して40分時点でAC。

参加記を書いているときに気づきましたが、絶対値の中の式がちょうどになる場合を考察し忘れていました。実際にはこれも凸多角形であることから発生しません。

E問題

ここからは二人で取り組みました。まずという条件を無視すると、求めるはあるが存在してによってと表せます。このは拡張ユークリッドの互除法で求められます。ここでとりあえずの場合の答えをとする場合分けを書きましたが、実際にはそのようなケースは存在しません。

さて、ありえないことですがだった場合、この問題はオイラーの関数によって解けます。このことはホスフィンさんによって指摘されました。という計算方法を考えると、素因数ごとに互いに素でないものを取り除いていることがわかります。同じような原理で数えることができて、答えはになるのではないかと考えました。ただし、素数であってでもあるものについては、は常にで割り切れませんから、考えなくてよいです。つまりを計算するときの素因数としてであるものだけ見ることになりそうです。

重複なく取り除けているかなど細かいことはわかりませんが、これで良さそうな雰囲気があったので、実際に書いて愚直と比較することにしました。diffが出て絶望しそうになりましたが、そのケースを確認してすぐにの素因数を求めた後の素因数をちゃんと弾けていなかったことに気づきました。これを修正するとちゃんと愚直と一致したため提出し、AC。コンテスト開始から80分でした。

F問題

流量下限制約付きの最小費用流です。辺をあらかじめ倍しておけば愚直に流すだけで解けます。流量の下限については確か事前に流しておけば普通の最小費用流になったはず、と思いつつ辺の張り方を調べて、頂点辺のグラフに流量のフローを流せば解けることがわかりました。とりあえずこれを書いてサンプルが合うのを確かめ、入力をダウンロードして計算し始めてから真面目に考察しようとしました。

10分くらい経ってから出力を確認すると、思ったより計算できていることがわかりました。大体20分で1ケース終わりそうです。ぶん回せば終わるということを確信してからまともに考察しようとする集中力が完全に切れてしまいました。その後も何とか考えるポーズを保っていると、辺のコストの取得時にすでに流れた流量を参照して計算すれば辺を倍する必要がなくなり高速になるのではないかということを思いつきましたが、ライブラリをどのように書き換えれば良いか考えているうちに1ケース目の実行が終了したので提出してしまいました。

無事通ったので、2ケース目の実行を始めると同時にホスフィンさんのPCで逆順に計算し始めました。書き換えに手間取って結構遅れてのスタートになりましたが、最後10ケース分くらいはこちらの出力からコピーして、手作業でマージし提出。ここをミスると追加で20分ですから、二人で画面を睨みつけつつ丁寧丁寧丁寧に行いました。こちらも通り、136分時点で6完になりました。実は5完時点ではCのペナルティが響き、ギリギリで同じ東北大のチームであるsuzukaze_Aobayamaに負けていたので、抜き返すことができて一安心でした。

G問題

の累積和をと定め、これでコストを書き直します。と移動するとき、ならが、ならが所持金に加えられます。よって、所持金の変化の総和を列に係数を掛けて足したものと捉えると、その係数はとが対応するちょうど二つについて、それ以外はのどれかになることがわかりました。またその係数列を達成するような移動が存在するためには、総和がになっていること、累積和が途中でより大にならないことも明らかに必要です。

ここまででいったんdpを書き、コストだけ求めることにしました。するとサンプルのでが出てしまいました。手で試してみると、の係数列としてを考えているようです。がちゃんと最初と最後になれるように適当な場合分けを入れようとしましたが、もうちょっと考えて、より一般に係数列を達成するような移動がどこかで分割されてしまうと問題ということに気づきました。これを抑制するためには、累積和が最初と最後以外でになってはいけないという条件が良さそうです。書き直すとコストについては正しい値が出たので、あとは復元です。残り20分強。

dpの遷移元を記録しておくことで、係数列に関しては容易に復元可能でした。あとはここから具体的な移動を構築します。始点はに該当する2点のうちどちらでもよく、そこからスタートして最も近い折り返しできる場所を探し、折り返す、ということを貪欲に繰り返すことにしました。わざわざ遠いところまで行く必要はありませんから、移動が構築できるならこの方法でよいはずです。サンプルを試しつつ実装を修正し、REが出なくなったので入力をダウンロードして実行します。幸いこちらでは落ちることなく実行が完了し、提出すると通りました。2ケース目も同様にして、ついに170分時点でACしました。

コードを以下に貼っておきます。係数の符号を反転して実装しています。

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int N;
int C[3000];
long long S[3000];
long long dp[3001][6060][2];
int prv[3001][6060][2];
bool chmax(long long&a,long long b)
{
    if(a<b)
    {
        a=b;
        return true;
    }
    else return false;
}
int main()
{
    while(cin>>N,N)
    {
        S[0]=0;
        for(int i=0;i<N-1;i++)
        {
            cin>>C[i];
            S[i+1]=S[i]+C[i];
        }
        int now=0;
        for(int j=0;j<=2*N;j++)for(int k=0;k<2;k++)dp[now][j][k]=-1e18;
        dp[now][0][0]=0;
        for(int i=0;i<N;i++)
        {
            int nxt=i+1;
            int now=i;
            for(int j=0;j<=2*N;j++)for(int k=0;k<2;k++)dp[nxt][j][k]=-1e18;
            for(int j=0;j<=2*N;j++)for(int k=0;k<2;k++)if(dp[now][j][k]>(long long)-1e18)
            {
                if(j>=2)
                {
                    if(chmax(dp[nxt][j-2][k],dp[now][j][k]+2*S[i]))prv[nxt][j-2][k]=j*2+k;
                }
                if((k==1?j%2==1:true)&&j>=1)
                {
                    if(chmax(dp[nxt][j-1][1],dp[now][j][k]+1*S[i]))prv[nxt][j-1][1]=j*2+k;
                }
                if(j+2<=2*N)
                {
                    if(chmax(dp[nxt][j+2][k],dp[now][j][k]-2*S[i]))prv[nxt][j+2][k]=j*2+k;
                }
                if((k==1?j%2==1:true)&&j+1<=2*N)
                {
                    if(chmax(dp[nxt][j+1][1],dp[now][j][k]-1*S[i]))prv[nxt][j+1][1]=j*2+k;
                }
                {
                    if(chmax(dp[nxt][j][k],dp[now][j][k]))prv[nxt][j][k]=j*2+k;
                }
            }
            if(i+1<N)dp[nxt][0][0]=dp[nxt][0][1]=-1e18;
            now=nxt;
        }
        cout<<dp[N][0][1]<<endl;
        vector<int>coef(N);
        int nzc=0;
        {
            int j=0,k=1;
            for(int i=N;i>0;i--)
            {
                int njk=prv[i][j][k];
                int nj=njk/2,nk=njk%2;
                coef[i-1]=j-nj;
                if(coef[i-1]!=0)nzc++;
                j=nj,k=nk;
            }
        }
        vector<int>x;
        vector<int>usd(N,0);
        {
            int st=0;
            while(coef[st]%2==0)st++;
            x.push_back(st);
            usd[st]=1;
        }
        for(int t=2;t<=nzc;t++)
        {
            int pos=x.back();
            if(coef[pos]>0)
            {
                while(true)
                {
                    if(!usd[pos]&&coef[pos]==(t==nzc?-1:-2))
                    {
                        usd[pos]=1;
                        x.push_back(pos);
                        break;
                    }
                    if(!usd[pos]&&coef[pos]==0)usd[pos]=1,x.push_back(pos);
                    pos++;
                }
            }
            else
            {
                while(true)
                {
                    if(!usd[pos]&&coef[pos]==(t==nzc?1:2))
                    {
                        usd[pos]=1;
                        x.push_back(pos);
                        break;
                    }
                    if(!usd[pos]&&coef[pos]==0)usd[pos]=1,x.push_back(pos);
                    pos--;
                }
            }
        }
        for(int i=0;i<N;i++)cout<<x[i]+1<<(i+1==N?"\n":" ");
    }
}

コンテスト終了

残り時間はHを読んだだけで終わりました。僕らの後にもう1チーム7完が出て、最終順位はペナルティ差で3位でした。今回のコンテストはほとんどのタイミングで完最下位だったので、やはり序盤に大量のペナを出すと辛いということを実感しました。結果的には過去最高の順位でしたが、たまたま完数で差をつけることができただけです。数年前はいつも最終的に完最速に近い位置で終わっていて、もう1問が解けず悔しい思いをしていたのを覚えていますから、これも成長の一つでしょうか。

コンテスト後は本番の戦略について話していました。序盤・中盤の問題をどれだけ二人に振るかが問題です。例えば昨年の予選ではDとEをチームメイトに任せてFに特攻し、結局解けなかったのですが、しかしこれはムーブとしてはなかなか理想的な動きでした。今年もそういう感じで積極的に振ったうえで、自分もちゃんとコーディングできたらなと思っています。そのためにはFを解く必要があるので、解ける問題が出ることを祈っています。精進については……いろいろコンテストに参加してこそいるものの、upsolveすらできていない現状はかなり微妙ですね。