ICPC国内予選2020 参加記

チームUHISHIROとしてsuta, shiro, kiyoshiの3人で出場した。

コンテスト前

勝利祈願

アジア行くぞ！！！！！ pic.twitter.com/CdX79tGo8n

— suta (@suta28407928) 2020年11月6日

模擬国内ではCで2時間バグを埋め込んでいたので、本番は炎上しないことを最優先にする意志を固めた。
15時くらいからコンテストまでの時間は幾何ライブラリの確認やFox observationの愚痴を言っていた。そんなこんなするうちに コンテスト15分前くらいになっていたので、呼吸を整えて…コンテストのURLはリハと同じ…

コンテスト本番

F5を押すと謎の画面が出てくる。チームメイト全員そうらしくてかなり焦った。
運営にメールと電話をしてもダメで察したので、連絡担当 : shiro、リロード担当 : suta, kiyoshiに分かれた。これがチーム戦(？)

10分経つと問題が開けたので A : shiro, B : suta, C : kiyoshiで問題を読み始める。

Aをshiroがあっさり通し、Bは読解が終わると考察も実装も簡単でびっくりする。これ本当に国内Bか？　すぐ書いてAC

kiyoshiがCの解法をすぐに思いついていてすごい。shiroからDの問題文概要を聞き、把握に苦戦しながらもなんとか理解する。

するとCの実装をしているkiyoshiが唸っている。二分探索のコードで

while(ok > ng){
    ll mid = (ok+ng)<<1;
    if(f(mid)) mid = ok;
    else mid = ng;
}

と書いていたらしい(どこが間違っているか探してみてね！)
これがICPCの恐ろしさか…(いいえ)
修正すると難なくAC。この時点で8,9位だった気がする。
順位表を見るとライバルチームのRamen as a ServiceとGive us sociabilityとほぼ同列で、DとEの勝負だねという話になる。 (コーチyamadさんのツイートから引っ張ってきました)

Dが階乗はまずいので、多分bitDPなんだろうと思って考察するが全然遷移が思いつかない。きよしがE解けそうと言っていたが、計算量が厳しそう＆TLE解法でも 実装が軽くないという感じですぐにはACは無さそうという感じだった。

30分くらいDとEを反復しても何も分からない。解法っぽいことを言う→1秒で棄却→「分からねえ～なんだこれ」を連呼するを繰り返していた(真面目にやりましょう)。 kiyoshiが分配法則が成り立つらしいことを発見したが、それから先も長そうに感じて気が遠くなる。

それからEをkiyoshi、Dをshiroとsutaで詰める。
Dの構文解析パート＆階乗全探索をshiroに書いてもらい、ほどなくしてサンプルが合う(すごい)。
しかし全然解法が降りてこない。他のチームはもうDかE通してるのかなあ…と思いながら申し訳ない気持ちになる。

気分転換にトイレに行く。なんか頭がすっきりして解法っぽいものが生えた気がする。帰ってshiroに伝える。→嘘だった
すると次はshiroがトイレに行くらしいので、「アイデアよろしく～(他人任せ)」と言いながら見送る。

shiroが帰ってくると何か思いついたらしく、

shiro「文字決め打って、その前後の文字を上手く決められないかな」
と言い始める。これが大当たりで、
suta「それ各文字について、その決め打った文字より前か後ろかをbitで全探索できませんか」

shiro「え、それじゃないか？？？」

suta「天才！！！！！！！！！！！」

確かにある文字より前のもの同士演算されてもある文字より前に決まってるし、後ろも同様。勝ちました………　お通夜の雰囲気だったのが一気に明るくなり、即実装を始める

shiroが「ただ場合分けが必要そう」と話していた。が全くshiroの意図が理解できなかったのでとりあえず実装する(ごめん)。
実装している間にshiroが気付いたらしく、どうやらshiroが思っていたのとsutaが思っていた解法が違ったらしい。嘘解法を伝えたら正しい解法が伝わった最高のパターン。これがチーム戦(？？)

すぐに実装が完了したがバグっていそう。と思いきやサンプル1の1通りの列挙が間違っていた。サンプルが合う。心臓バックバクの状態でsubmitして、AC。しばらく発狂してた。

Dでそんなこんながあったうちに、Eもオーダーが落ちたらしく、kiyoshiが書いていたがバグっているらしい。Eを絶対に通そうという話になり、全員でコードを見る。が何も分かりませんでした。ごめんなさい。

しかしshiroと共にkiyoshiに質問を投げると、自分で説明しながらミスに気付き、修正し始める。それを繰り返すうちに考察と全然違うコードを書いていたことに気付いたらしく、それを修正するとサンプルが合う。もうお祭り状態。submitしてAC。暫定14位で通過を確信していた。バグっている時に質問を投げるの、かなり大事かもしれない。

興奮で頭が働かない中、Fを読む。きよしがすぐに二乗解を生やしていて書いていたが、時間切れ(sちょうどと誤読していたらしいが、s未満でも二乗解なら時間があれば書けると言っていた)。Fの問題文をもっと早く読んでいれば解けていたかもしれないが、DとEで手一杯だった。

結果

5完で全体17位、早稲田内1位で予選通過！！！！！
勝ち目は薄いと思っていたので、本当に嬉しい。チームメイト、本当にありがとう…

おまけ

ya〇adさん(鍵)のツイートを見ると、DとEのACした時刻が分かる(鍵なので誰のツイートかは伏せます)

この他にもUHISHIROが言及されているツイートがたくさんあって嬉しかった。

コンテストのラスト、kiyoshiがFを書いている間に順位表を眺めていたんですが(おい)、順位表のUHISHIROの真下に「suta」が見えて一瞬びっくりしてしまった(tsutajさんの連続する部分文字列だったことを初めて知りました)。なおチームtsutajにtsutajさんは居ないらしい

今後

横浜大会は初めてなので、良い成績が残せるように精進を頑張る！！(学業さん…)
まずは黄色を安定して維持できるようにしたい。

Educational Codeforces Round 97 F : Emotional Fisherman

問題リンク :

codeforces.com

問題概要

長さ$N$の数列$A$が与えられ、これの並べ替えを考える。
左から見た時に、それより前までのmaxを記録して現在見ている数字がmaxの2倍以上またはmaxの半分以下であるような数列の並べ替えの総数をmod $998244353$で求めよ。
ただし一番左の要素を見ているときのmaxは0とする。
例えば1 1 4 9は2番目を見た時に条件を満たしていない。4 9 1 1は条件を満たす。

解法

以降解法では全て1-indexで考えます。
挿入dpのような考え方をします。
数列を昇順にソートしてから、状態として

• 何番目を見ているか
• max(をとるindex)

をもつことを考えます。すなわち $$ dp[i][j] = i番目まで見てmaxがa_jであるときの場合の数 $$ として動的計画法を行うことを考えます。

その前に、前処理として以下の値を求めておきます。

• $pre[j] = a_j \geqq 2a_k をみたすkの最大値$

数列は昇順なので、$k$以下の$a$の値は全て$a_j$の半分以下であることが保証されます。

dpにより$i+1$番目の数を決める時に、考えるべき遷移は2つです。

① $a_j$ よりも小さな値を挿入するとき
$i$番目まで見たという事実から、$i$番目までの数は全て$a[pre[j]]$よりも小さいということが確定しています。なぜならmaxをとるindexは昇順に更新されるからです。
これによってこれまで何を選んだかを考える必要がなくなり、$pre[j]$以下の値がまだ何個使用されていないかを係数とすることで更新が可能になります。
そして、$a_j$よりも小さな値を挿入するとき、maxは再び$a_j$となります。
よって更新式は以下のようになります。 $$ dp[i+1][j]= dp[i][j] * (pre[j] - i + 1) $$ $j$番目の数が$i$個の中に1つ含まれるため(maxが$a[j]$なのでそれはそう)、+1が入ることに注意します。
$pre[j]$は1-indexedであるため、0-indexedで実装する際は+2となります。

② $a_j$ よりも大きな値を挿入するとき
数列は昇順なので、大きな値として$a_k$を取ることにすると$j<k$となります。
これを貰うdpとして考えると、次にmaxをとるindexとして$k$を選ぶとき、それまでのmaxの2倍以上でなくてはならないので$pre[k]$以下の場合の数を足しこむ形になります。
よって更新式は以下のようになります。 $$ dp[i+1][k] = \sum_{l=1}^{pre[k]} dp[i][l] $$

高速化

このdpは状態数が$O(N^{2})$、①の方の遷移が$O(1)$、②の方の遷移が$O(N)$となっており、全体の計算量は$O(N^{3})$です。
しかし、②の遷移は累積和を使用することで$O(1)$で更新できるようになります。

以上で$O(N^{2})$でこの問題を解くことができます。

実装

#include <iostream>
#include <algorithm>
using namespace std;
const int mod = 998244353;

void chmax(int &a, int b) {if(a < b) a = b;}

int a[5050], pre[5050];
long long dp[5050], sdp[5050];

int main(){
    int n; cin >> n;
    for(int i=0; i<n; i++) cin >> a[i];
    sort(a,a+n);
    for(int i=0; i<n; i++) pre[i] = -1;
    for(int i=0; i<n; i++){
        for(int j=i+1; j<n; j++){
            if(a[j] >= 2*a[i]) chmax(pre[j],i);
        }
    }
    for(int i=0; i<=n; i++) sdp[i] = 1;
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            if(pre[j] >= i-1) dp[j+1] = dp[j+1] * (pre[j] - i + 2) % mod;
            else dp[j+1] = 0;
            (dp[j+1] += sdp[pre[j]+2]) %= mod;
        }
        sdp[0] = 0;
        for(int j=0; j<=n; j++){
            sdp[j+1] = (sdp[j] + dp[j]) % mod;
        }
    }
    cout << dp[n] << "\n";
}

感想

累積和dpの添え字はいつも悩みますね
遷移を完全に把握した状態で書き始めないとでたらめな実装になりがち

ACPC2020 Day2 J : DEG MUL SUM

問題リンク
onlinejudge.u-aizu.ac.jp

問題概要

$N$頂点0辺の無向グラフがある。このグラフに$Q$回辺が追加されたり削除されたりする(指定された箇所に辺が無ければ追加、あれば削除)。
「各辺の両端の頂点の次数の積」の和をQ回それぞれ求めよ。

制約

• $1 \leqq N \leqq 10^{5}$
• $1 \leqq Q \leqq 10^{5}$

解法

辺についての積の和　→　頂点についての和の積として考えることができます。
ある頂点$u$が答えに寄与する値$W_u$は、$u$と直接辺でつながれている頂点の集合を$S$、頂点$x$の次数を$d_x$とすると
$$W_u = d_u\displaystyle \sum_{v \in S}^{} d_v$$ となり、「和の積」の形になります。

以降の$u,v$はクエリで与えられた2頂点を指します。
各頂点について「その頂点とつながっている頂点の次数の和」を保持しながら差分更新することを考えます。
追加(削除)によってそれらの値が変わる箇所は、頂点$u,v$と隣接する頂点です。
よって愚直に更新しようとすると次数が大きい頂点に辺の追加や削除がされると計算量が増大します。

ここで2パターンに分けて考えます。

• 頂点$u,v$
• 頂点$u,v$と隣接する頂点($u,v$以外)

別々にした方が頭が壊れにくいと思いました(たぶん)。平方分割、頭壊れやすい気がする…

①頂点$u,v$

追加される際は「追加後の$u$の次数」と「追加後の$v$の次数」の積がそのまま加算されます。削除されるときは逆で、削除前のそれぞれの頂点の次数の積が差し引かれます。

②頂点$u,v$と隣接する頂点

唐突ですが、頂点を特殊な頂点と一般の頂点に分けます(以降は青(の頂点)、黒(の頂点)と呼ぶことにします)

青の選定基準は、
「$\sqrt Q$回以上クエリで登場している」
です。
青は最大でも$2\sqrt Q$個しか存在しません(クエリで与えられる数字の数が$2Q$個であるため)

各クエリの中で、青と黒で全く異なる操作を行います。それぞれの操作は以下の通りです。
青…上記で述べた「その頂点とつながっている頂点の次数の和」を陽に管理して差分更新を行う。

黒…和を持たずに、クエリごとに毎回隣接頂点の情報を調べ上げて差分更新を行う。

操作の具体的な説明の前に、このように頂点を分けることによって計算量が改善されるのかを先に明らかにします。

頂点を分けることによる嬉しさ

青、黒それぞれについて各クエリごとの計算量を確認します。

青…次数こそ多いものの、和を管理しているので計算は$O(1)$でできます。更新ですが、色を分けたことによって黒の頂点についてはそもそも情報を持たないため、更新する必要がないのです。これが大きく、青の頂点は高々$2\sqrt Q$個なので、更新は$O(\sqrt Q)$で完了します。

黒…クエリに$\sqrt Q$回以上登場していないので、当然次数は$\sqrt Q$未満です。よって求値や更新が$O(\sqrt Q)$でできます。

よってクエリあたり$O(\sqrt Q)$の計算量で抑えられ、全体計算量が$O(Q \sqrt Q)$で済むことになります。

平方分割、考察かなり進めないとどうして計算量落ちるのか分からないがち…(慣れていないだけかも)

具体的な操作

「嬉しさ」のところで述べたところを実装に移していくことを考えます。

削除は追加と逆の操作をすればよいので、追加クエリのみを考えることにします。また$u$と$v$で操作が変わらないので、頂点は$u$とします
ここまでの説明で用いた「ある頂点とつながっている頂点の次数の和」を$sum$とします。

$u$が青のとき

• 答えに$sum$を加算($u$の次数が1増えるため、$1 × sum$分だけ増える)

• $sum$に$v$の次数を加算する。$v$の次数はクエリ前より1増えていることに注意。

• $u$と隣接する青い頂点について、$sum$を1増やす($u$の次数が$1$増えるため)

• $u$の隣接する頂点リストに$v$を追加する
  
  

$u$が黒のとき

• 隣接する頂点の和を愚直に調べて取得し、答えに加算

• $u$と隣接する青い頂点について、$sum$を1増やす

• $u$の隣接する頂点リストに$v$を追加する
  
  

ここで、隣接する頂点を見る際に$v$は見ないようにします(追加する時は追加する前に、削除する時は削除した後に操作を行う)
$v$でも同様の操作を行った後、最後に$u$の次数と$v$の次数の積を加算(減算)します。

実装上の注意・バグりそうなところ

• 青だけを更新するため、隣接頂点リストの中でも「隣接頂点 : 青」、「隣接頂点 : 黒」に分けておく

• $u,v$が青かどうかを高速に判断したいため、setもしくはvectorで青リストを作成して、二分探索で存在判定(vectorの場合はソートを忘れずに)

• $u$の隣接頂点リストに$v$を追加すると、$u$の次数が1増えた状態で取得される
  
  

実装

#include <iostream>
#include <vector>
#include <set>
using namespace std;
typedef long long ll;

int main(){
    int N,Q; cin >> N >> Q;
    int q = 320;
    vector<int> u(Q), v(Q), cnt(N,0);
    for(int i=0; i<Q; i++){
        cin >> u[i] >> v[i]; u[i]--; v[i]--;
        cnt[u[i]]++;
        cnt[v[i]]++;
    }
    set<int> sp; //特殊頂点をsetで管理
    for(int i=0; i<N; i++){
        if(cnt[i] >= q) sp.insert(i);
    }
    ll ans = 0;
    vector<int> sum(N,0); //隣接頂点の次数の和(特殊頂点のみ使用)
    vector<set<int>> ads(N), adn(N); //隣接頂点を管理 特殊/一般

    //先に追加・削除の処理をラムダ式で記述
    auto ins_sp = [&](int node, int sz){
        ans += sum[node];
        sum[node] += sz;
        for(auto x : ads[node]) sum[x]++;
    };
    auto del_sp = [&](int node, int sz){
        sum[node] -= sz;
        ans -= sum[node];
        for(auto x : ads[node]) sum[x]--;
    };
    auto ins_nor = [&](int node){
        ll s = 0;
        for(auto x : ads[node]) s += ads[x].size() + adn[x].size();
        for(auto x : adn[node]) s += ads[x].size() + adn[x].size();
        ans += s;
        for(auto x : ads[node]) sum[x]++;
    };
    auto del_nor = [&](int node){
        ll s = 0;
        for(auto x : ads[node]) s += ads[x].size() + adn[x].size();
        for(auto x : adn[node]) s += ads[x].size() + adn[x].size();
        ans -= s;
        for(auto x : ads[node]) sum[x]--;
    };

    set<pair<int,int>> query;
    for(int i=0; i<Q; i++){
        //頂点uの処理
        ll sz = ads[v[i]].size() + adn[v[i]].size();
        if(query.count({u[i],v[i]})){
            if(sp.count(v[i])) ads[u[i]].erase(v[i]);
            else adn[u[i]].erase(v[i]);
            if(sp.count(u[i])) del_sp(u[i], sz);
            else del_nor(u[i]);
        }else{
            if(sp.count(u[i])) ins_sp(u[i], sz + 1);
            else ins_nor(u[i]);
            if(sp.count(v[i])) ads[u[i]].insert(v[i]);
            else adn[u[i]].insert(v[i]);
        }

        //頂点vの処理
        sz = ads[u[i]].size() + adn[u[i]].size();
        if(query.count({u[i],v[i]})){
            if(sp.count(u[i])) ads[v[i]].erase(u[i]);
            else adn[v[i]].erase(u[i]);
            if(sp.count(v[i])) del_sp(v[i], sz + 1);
            else del_nor(v[i]);
            query.erase({u[i], v[i]});
            ans -= (sz + 1) * (ads[v[i]].size() + adn[v[i]].size() + 1);
        }else{
            if(sp.count(v[i])) ins_sp(v[i], sz);
            else ins_nor(v[i]);
            if(sp.count(u[i])) ads[v[i]].insert(u[i]);
            else adn[v[i]].insert(u[i]);
            query.insert({u[i], v[i]});
            ans += sz * (ads[v[i]].size() + adn[v[i]].size());
        }

        cout << ans << "\n";
    }
}

HUPC2020参加記

HUPC2020に全日程参加しました。 ICPCチームメイトのsiro53も参加記を書いているので是非ご覧ください。

bakamono1357.hatenablog.com

day1

ICPC出場予定でのチームUHISHIRO(siro53, kiyoshi0205, suta)の3人で参加しました。
最初はレート順に
A : shiro
B : suta
C : きよし
が担当することになりました

Aをshiroがすぐ通す
Bを読んで「区間一次関数加算できません！詰み！w」とか言っていたがよく見ると最終的な値しか問われていないので例のimos2回やるやつだと理解
→少し戸惑いながらもバグることなくAC(良かった)
Cをきよしがギャグじゃんと言いながら書いて出す→MLEが出たがすぐ修正して提出してAC

Cをきよしが書いている間shiroとDの考察をする
suta「N個の点が平行な二直線上に全てないときつそうじゃない？知らんけど」
shiro「あるかも」
suta「きよしに聞けばヨシ！」
Cを通し終わったきよし「あ、はいそうですね」
ということでそうなっているかどうかの判定をO(N)でやりたいねという方向で考察を進める。
がなかなか良い案が出ず、shiroとsutaはEの考察をはじめ、Dはきよしに任せることに

Eの考察は比較的順調に進み、
suta「とりまワーシャルフロイドやってワープできるとこ列挙して新しくグラフ作ればいいか」
shiro「これ作り直したグラフって二部グラフじゃない」
suta「天才か？」

確かここらへんできよしがDの考察を終わらせて実装を始めた　O(N)回見て比較がO(N)回かと思いきや最初の数個みればNG判定ができるらしい　すごい
再びEの考察に戻る
shiro「連結成分の頂点数/2の合計で良さそう」
suta「ウニのときどうするんですか」
shiro「」
suta「連結成分ごとに色塗って少ない方を足しこめば良さそう」
shiro & suta「はい勝ち～もろたで！w」
完全にACを確信してきよしがDを通した後にshiroが実装を始める
ほどなくして実装が終わり、提出
！？！？
実装ミスを隅々まで確認するが、間違っていなさそう
きよし「一応assertつけて二部グラフかどうか確認する？」

WA　それはそう
かなり厳しい気持ちになる。F以降も読んでみるが厳しそう

～30分後～
きよし「これだめじゃんww(WAのケースを見つける)」
shiro & suta「ほんとだ………」
「連結成分の中で色塗って少ない方」は貪欲だという認識が抜けていた　大反省

フローを疑いながら最小カットや最小費用流をきよしが考察し、自分はDPでできないか考えはじめる

色々考察するもなかなか解法にたどりつかない
suta「なんかこれ最大マッチングとか最小点カバーとか最小辺カバーとかそこらへんだったりしない？二部グラフだし」
きよし「最小点カバーじゃん」
二部グラフでは最小点カバー = 最大マッチングを知っていたのが救いだった…
shiroが書き始める。途中でバグったらしくきよしに交代し、ギリギリでAC。

結果

5完28位。1時間あればFを詰め切れた雰囲気もあったので残念。

3時間コンテストでは1問破滅すると大変なことになることがよく分かりました。国内予選では炎上しませんように……
？？？「直感に頼った未証明のgreedyは危険です」

解いた問題の感想

A : 先に掛け算をしましょう
B : imos2回の等差数列加算は某ARCで書いた経験が生きました
C : 不思議な制約　面白いギャグ
D : 鳩ノ巣の考え方全く出てこなかった。きよしがすごい
E : 直k…(以下略)
Fが、解けません…(数え上げやっぱり苦手)

day2

day1と同様UHISHIROで参加しました。
最初の3問もday1と同様に
A : shiro
B : suta
C : きよし
が担当しました

Aをshiroが通した後もBが読解すら完了しておらず焦る　Cもまだ詰められていなさそう
なんとかBの読解が完了し、やりたくねえ～と言いながら書き、1ペナ(PE)してAC
Cが行列累乗で解けるらしく、shiroが爆速で書いてAC

Dをきよしが読んでいて、これなんだろう？貪欲か？いや違うだろ…解けませんという気持ちになる

Gを読むとダブリングっぽいから最初のステップだけなんとかできればいいねという話になる。
XとYを独立に見ることができ、きよしがさらに等差数列として計算できることに気付く
きよしがGの実装を始め、Dが解かれていたのでshiroとsutaでDを詰めにかかる

Dが全く分からないままきよしがGを書き終わり、提出
デバッグ作業に加わってバグを探すが、最初の1ステップもダブリングパートにもバグが見つからず、day1の悲劇を思い出して悲しくなる。

Gが諦め気味になり、再びDの考察へ。すると
きよし「これ多分貪欲でいけるよ」
suta「マジ？？？？」
きよし「去年のPG battleにそっくりなのがある」

さすがに草　よしなに書いて証明 : AC

Mを詰めはじめる
各コマ独立で、K回まで数字が言えてある数を言ったら負けなゲームが複数みたいなことを伝えると、きよしがgrundy数で考察を始める
自分が変なことを言いまくってた気がしたが、きよしが詰められそうなのでJの考察を始める

しばらくするときよしがMを詰め切り、実装を始める
Jは実家DPに近いものだろうという気持ちになりながら考察しているとDPの値は単調増加に、maxの値は単調増加になることに気付いて希望を見出す
shiroにa[i]の値は負になることもあることを指摘されて破綻したと思っていたが、そもそもmaxが負の区間は全部負の時以外取る必要がないことに気付いて勝ちを確信

ほどなくしてMが通ったのでJを書き始める
するとGのデバッグに回っていたshiroときよしが突然笑いだす



1LL<<60は無限回やらかした経験があるだけに気付けなかったのがかなり悔しい…
きよしではなくshiroが発見したらしい。情報共有は大事ですね
G　AC

Jが書き終わるが、添え字関連が難しかったので一発で書けるわけがないという謎の自信(?)があった
が、テストケースをもらってもWAケースが出ない

suta「じゃあ俺が天才だったっということで、、、出していいっすか？？？？w」

初めて仕事ができたような気がした

Jを書いていた時にshiroときよしがIを詰めていて、数学何も分からんと言いながらEを考える　Eも何も分からん
I詰め切れないままコンテストが終了。数弱で協力できずごめんなさい…

結果

7完28位。28に愛されたチーム
ICPC国内予選でもライバルになるであろうgive us、Ramen as a serviceに完数で負けてしまった。

解いた問題の感想

A : 多倍長整数は要りません
B : AOJ-ICPC 100-150点問題
C : 三項間漸化式　これCなんだ
D : 証明 : AC(は？)
G : ぱっと見ダブリングで、最初のステップをどう詰めるか　1e9でも解けるのすごい
J : JはDPのJ　解けてよかった…
M : 頂点ごとにgrundy数が予め定まることに気付けるかどうか。遷移が高々O(NK)なのが面白い

day3

HUPC day3優勝しました pic.twitter.com/UnhvTwahhM

— suta (@suta28407928) 2020年9月16日

実家であるところの「麵屋こころ」です。遊びにきてね

shiro、yamadさんと大学に集まってチームmouko_tanmenで参加しました。
yamadさん㊙情報 : mouko_tanmenが好きではないらしい

最初の3問はまたレート順に
A : shiro
B : suta
C : yamad
が担当

Bを読むが分からない。shiroが間違えてBを読んでいたらしく慌ててAを読んで通す。Bが分からない。
申し訳ない気持ちになりながらyamadさんにCを書いてもらい、無事通る。
順位表をのぞくとBが誰にも解かれていない　マジか…

yamadさんとshiroは他の問題を読み、sutaがBを考える

しばらくしてBの答えはXの差 + Yの差またはそれに1足したものだろうと確信し、Xの差とYの差が両方1以上なら途中で調整できて1足さずに済むだろうとエスパー。
本当か？と思いつつも提出する→WA 29/47
なんとなくあってそうという気持ちになったところで0 0 0 0の答えが1になっていたことに気付いてがっかり
Xの差またはYの差が0の時の場合分けを細かく書いて再提出→WA 34/49
分からなくなり、shiroから愚直解の疑似コードをもらう

少ししてshiroがIの解法をyamadさんに説明し、解かれている数的にも正しそうということになり、yamadさんが書いてAC
Mの解法もyamadさんが分かったようで書く。

yamad「TL4秒でも少し不安ですが、出します」submitを押す
yamad「ありがとうありがとうありがとうありがとうありがとうありがとうありがとうありがとうありがとうありがとう…」
ジャッジにありがとうを言うとTLが緩くなるらしいです。1日n回オンラインジャッジいつもありがとう。


どうして……

何回か提出するもACにならない。するとshiroがmapを使わなくても良いことに気付き、yamadさんが修正してAC。15 * 3¹⁵にlogつけると感謝しても通らないんですね(棒)

Gを読むとDPっぽいので、コストを前計算すれば良さそうという話になり、yamadさんがGを詰め、sutaはBの愚直を書く。
書き終わって試すと、Xの差が0、Yの差が1の時だけ余計な場合分けをしてしまっていたことに気付く。ごめん……　修正してAC
かなり盛り上がった

shiroとsutaでF、yamadさんはEを詰めていたが途中でGの考察に入る。
Fは実は誤読していて(iとi+1の色が同じでも操作ができると勘違いしていた)、N >= 3以上は基本的にできる！wという話になり、提出→速攻でWA

何も分からず1時間くらい辛い時間が経過。辛かった

yamadさんがG書けそうということになり、書いてもらう。その間も二人でFの考察をしているが、やはり解法は浮かばない。解かれすぎでしょ……

気分転換にトイレ行きつつ外をうろついて戻ると、各文字の出現回数が関係ありそうという気持ちになり、shiroに伝える。すると
shiro「これSが全部同じ文字の時以外任意の2点swapできないか？？」
できそう
部屋の雰囲気が明るくなった
Gをyamadさんが通す　テンションが上がる
さらにyamadさんが操作によって各文字の出現数の偶奇が全て反転することに気付く
すると必要条件が浮かびあがってきた
「SとTの各文字において出現回数の偶奇が全て一致または全て違う。並び方は問わない」


一同「必要条件出たし、これは必要十分だろ！証明 : AC！www」


SあるいはTが全て同じ文字な時はコーナーケース(ということにした)として弾き、書くとAC、めちゃくちゃはしゃいでた

その後JとEを読むと、Eの問題文が修正されていたことが発覚
yamadさんが再度Eを詰め、shiroとsutaでJを考察
yamadさんがEを書いて提出したが、通らずコンテスト終了(1行変えたら通ったらしい。無念)

結果

7完24位。give usとRamen as a serviceにギリギリ勝利。UHISHIROでもACPCで勝ちたいですね。
主にBとF担当でかなり苦しい5時間になってしまった。

解いた問題の感想

A : いつもif文で書いていた大文字小文字判定。C++ islowercaseで調べたらどうやらislower関数があるらしい…
B : 難易度順ってなんだっけ
C : コンテスト後に見たら分かりませんでした。既出らしい…(精進不足)
E : 解説みてすげーって言ってた。「時計回りで最初」の実装にかなり苦労した。「凸多角形の面積は符号付き面積の和」はいつかのICPCで見て驚いた記憶がある
F : コンテスタントには天才しかいないらしい
G : コスト計算が尺取りみたいにできるのが面白い。三分探索でもできるらしい。
I : 見るべき辺が高々NlogN本
J : dp[i][l][r]、3乗に収まるとは思わず…
M : 底が3の高速ゼータ変換　初めて見ました

全体感想

どの問題も考えがいのある良い問題ばかりで本当にすごいと思いました。(WUPCでの作問数ぜロ並感)
どうもチーム練でなかなか仕事できなくて悲しくなる時が多いので、精進します。
運営の方々本当にお疲れ様でした。楽しかったです。

そしてACPCへ…

Codeforces Round #635 div2-E (div1-C) Kaavi and Magic Spell 解説

問題リンク(div2)https://codeforces.com/contest/1337/problem/E

問題概要

2つの文字列$S,T$が与えられる。$S$を左から1文字ずつ取り出して別の場所に並べていく。$i+1$文字目を取り出すとき、$i$文字目まででできた列の先頭か最後尾に置くものとする。このとき接頭辞が$T$に一致する数を$998244353$で割った余りを求めよ。ただし、取り出している途中過程で接頭辞が$T$に一致するときも答えに含むものとする。また、前に置いても後ろに置いても同じ文字ができる場合は、それぞれ別のものとしてカウントすることにする。

制約 : $1≦|T|≦|S|≦3000$

例 : $S ="abab",\quad T="ba"$

最初、先頭と末尾どちらに追加してもできる文字は"a"となる(つまり2回カウント)。それから$S$の次の文字bを先頭に加えると"ba"(図の左), 最後尾に加えると"ab"(図の右側)のようになる。これを$S$が空になるまで繰り返す。このとき、途中経過含めて接頭辞が$T="ba"$に一致するのは赤く表示された6つである。ただし最初のaが先頭と最後尾どちらに追加されても同じ遷移をたどるので、最終的な答えは$6\times2=12$となる。

考察

以降 $ |S|=n,|T|=m $ とします。 $n≦3000$という制約と、1文字ずつ追加ということでdpを考えます。

$dp[i][j]$…$T$の左から$i$番目(以降全て0-indexed)から$j$個文字が一致している場合の数(添え字$j$を右端のindexとしても解けます)

dpテーブルの初期化

各iについて、i番目から0文字部分は$T$と一致すると考えられるので(イメージは少しつきにくいですが…)、初期化は $$ dp[i][0] = 1\quad(i=0,1,…n) $$となります。 ここで、$ i>m $を満たす$i$にもdp配列を定義することに注意します(遷移のところで後述します)

dp遷移

文字列$S$の$j$番目を見ているとき、並べられている数はぴったり$j$個なので、dp遷移の中で、配列の2つ目の添え字は必ず$j\rightarrow j+1$に移行します。文字列$S$を一回取り出すときに考えるべき遷移は、先頭に追加・最後尾に追加の2つです。説明の都合上最後尾の方から詰めていきます。

①最後尾に追加

このとき、左端の位置は変わらず、文字数だけが1増えることになります。
まず$ i+j<m $であるとき、つまり$T$の左端から$i$番目のところから$j$文字取り出しても右端に届かないときを考えます。 $dp[i][j+1] = dp[i][j+1] + dp[i][j]$となる条件は$S[j]=T[i+j]$、つまり追加しようとしている箇所の文字が$T$の該当箇所に一致することです。逆に$S[j]\neq T[i+j]$であるとき、これから右に追加しても$T$と一致する可能性が一切ないので、左端が決まっている以上棄却されることになります。
次に$ i+j≧m $のときを考えます。このとき、右端に追加するときにはすでに$T$の範囲から外れることになります。つまり何を追加しても条件を満たすことがわかります。よって必ず $$dp[i][j+1] = dp[i][j+1] + dp[i][j]$$となります。

②先頭に追加

このとき、①と同様に2つ目の添え字は$j\rightarrow j+1$となります。1つ目の添え字については、左端が一つ左にずれるので$i\rightarrow i-1$となります。 遷移は①の時と似たようなものになります。まず$ i=0 $のときは先頭にこれ以上追加できないので遷移はありません。次に$ i≦m $のとき、$S[j]=T[i-1]$なら先頭に追加できるので $$ dp[i-1][j+1] = dp[i-1][j+1] + dp[i][j]\quad if \quad i>0\quad and\quad S[j]=T[i-1] $$となります。 また、$ i>m $であるとき、先頭に何を追加しようと$ T $とは関わりを持たないので、必ず

$$ dp[i-1][j+1] = dp[i-1][j+1] + dp[i][j] $$が成り立ちます

以上の遷移をまとめると以下のようになります。 $$ dp[i][j+1] = dp[i][j+1] + dp[i][j]\quad if\quad i+j≧m\quad or\quad S[j]=T[i+j] $$$$ dp[i-1][j+1] = dp[i-1][j+1] + dp[i][j]\quad if\quad i>0\quad and \quad (i>m\quad or \quad S[j]=T[i-1]) $$

dpテーブルを埋めていく様子の一部を表すと次のようになります。(最初に書いた$S="abab",\quad T = "ba"$を例にします) $dp[0][0]\rightarrow dp[0][1]$については$S[0]\neq T[0]$なので加算されず、 $dp[1][0]\rightarrow dp[0][1]$についても$S[0]\neq T[0]$なので加算されません。

$dp[1][0]\rightarrow dp[1][1]$については$S[1]=T[1]=a$ なので加算されます。 $dp[2][0]\rightarrow dp[1][1]$についても$S[1]=T[1]=a$ なので加算されます。

$dp[1][1]\rightarrow dp[1][2]$については、$ m=2 $ なので $ i+j=2≧m $となり、最後尾に任意に追加できるので加算されます。 $dp[2][1]\rightarrow dp[1][2]$については$S[2]\neq T[1]$なので加算されません。

dpテーブルを埋めきると以下のようになります。 実装を単純化するために$ i+j≧n $となるときの遷移は無視しています(答えには影響しません)

答え

最後答えにする部分は、$T$の$0$文字目から$ m $字以上一致するものです($ m $字を超えるものについては、一致するというよりm字より先を無視できるという感じです) つまり

$ans = \sum_{j=m}^{n} dp[0][j] $

となります。

ACPC2019参加記

※インデント入れまくったせいで見づらくなってしまいました。ごめんなさい（直す気力がないです）直しました(2020 11/10 追記)

ACPC(会津大学競技プログラミング合宿)2019に参加しました。

Day0

13時開始のATNDが13時20分には補欠になっていて驚きました。今回が初めてのオンサイトで、弊大学以外の競プロerと交流することが初めてだったので、楽しみ半分不安半分でした。絶起が怖かったので3時には寝ました(は？)

Day1

無事に起床できて良かったです。朝飯にカツサンドくんを買っていきました。

今日の朝飯であるところのカツサンドくん pic.twitter.com/iB4LupCW3S

— suta (@suta28407928) September 17, 2019

新幹線内では寝る予定でしたが、景色に見とれてたら郡山に着いてしまいました。そこから磐越西線に乗ると、方々から競プロの話が聞こえてきて新鮮でした。

pic.twitter.com/HdGzzuG2ae

— suta (@suta28407928) September 18, 2019

 会津若松駅から大学まで徒歩30分強あったので、競プロ関連の話をしたり、ツバサさんから去年のACPCのことを聞きながら勇者になっていました。

わいわい pic.twitter.com/RA9rLShx3N

— suta (@suta28407928) September 18, 2019

 ～コンテストDay1(立命館大セット)～

複数人で問題を解くのはICPC国内予選以来でした。チームは全日程でランダムにしま

した。

beetさん、rollmanさん、自分の3人でチームacpc_kakuniramenで参加しました。

初めてのオンサイトでbeetさんと組むことになってとても印象強かったです。

beetさんはE以降を読み、rollmanさんがAを通し、自分がBを通した後、rollmanさんが「Cは強連結ですね」というとbeetさんが秒で通していました。その後beetさんにGの概要と考え方を教えてもらい、自分はGの場合分け等の考察をすることになりました。

rollmanさんがDの考察をしていて、beetさんはその間にEを通していました。Gの考察は煩雑すぎて全然進みませんでした。つらい。

しばらくbeetさんとGの考察を進めると、「フローでは？」ということになり、（自分は全く分かりません）beetさんがrollmanさんと交互に実装を始めました。自分は"o"単体を後回しにできるかをひたすら考えていました。

しばらくすると実装が終わって提出するもWA。自分はテストケースジェネレーターになりました。色々ケースを考えながら修正するとGが通って、凄いなあとただひたすら感動していました。

その後Dの実装が上手くいかなかったようで、

beetさん「(rollmanさんに対して)お前スコープもまともに考えられねえのか」

rollmanさん「あ、完全に理解した」

beetさん「理解してねえだろ」

とbeetさんがキレ気味で、思わず笑ってしまいました(何もできない人並みの感想)。その後beetさんもDの実装を始めて提出するもWA。残り2分ほどになってもう苦しいかと思ったところでbeetさんがソートを逆にすると通る。

beetさん「これが競技プログラミングなんだよなあ」

強い人って強いなあと思いながら会場を後にしました。

コンテスト後、早稲田勢で喜多方ラーメンを食べて富士の湯に行きました。

喜多方ラーメン pic.twitter.com/0FAUoXBdKk

— suta (@suta28407928) September 18, 2019

 shiroがなかなか風呂から出てこないなあと話していたところ、こういうことだったようで…

銭湯につ🌲刺さって寝てしまっていた…

— shiro (@shiro537) September 18, 2019

 銭湯で寝る人は初めて見た

1時からのこどふぉに出たHyado君やかっつ君すごいな～と言いながら12時くらいには寝(落ち)ました。

Day2

12時寝6時半起きの健康生活を久しぶりにして、健康っていいなーと思いました(？)

健康 pic.twitter.com/Yv5lgnq54j

— suta (@suta28407928) September 18, 2019

～コンテストDay2(会津大セット)～

ninja7さん、T.Mさん、Kuri174さん、自分の4人でチームacpc_niconicoで参加しました。

自分がAを通した後、TMさんにCの実装をお願いされましたが、幾何が全く分からなかったため投げ返してしまいました…(ごめんなさい)。そこで初めてnext_permutationの概念を知りました(今更)

ほどなくしてTMさんがCを通し、KuriさんもBを通しました。ninjaさんはD以降を見ていて、G、H、I、M あたりがいけそうという話になりました。Mはしばらく考察して二項係数と2べきだなあという話になった直後にはTMさんが通していました。すごい。

ninjaさんがIの考察を終えていて「DPですね」「あ、確かにそうですね」と言っていたらしばらくしてIが通っていました(後から問題をしっかり見たらDP以外にもその高速化やMOD演算など考えるポイントがいくつもあって全然簡単ではありませんでした。)

その後ninjaさんがH、TMさんKuriさん自分がGの考察をしました。どちらもあと一歩のところで詰め切れず、結果はA、B、C、I、Mの5完でした。Grundy数のG、勉強します。

～懇親会～

 色々な人と話せて美味しいお酒が飲めたのでとても満足しました。誕生日が8月で良かったです。途中で銭湯に行くために抜けたのですが、その頃には酒に飲まれた人やそれを撮影する人がいて面白かったです。それから1時間くらいするとツイートの限界さが増していて心配でしたが、翌日には何事もなくコンテストが行われていました。

beetさん｢4足歩行は2足歩行の2倍安全｣

— おきもち (@IKyopro) September 19, 2019

 これすき

この日はこどふぉに参加しました。DPのDが解けてDigits Paradeのリベンジができたので舞っていました(この後悲劇が起こることは知る由もなかった…)

同室の人がACして踊っている

— shiro (@shiro537) September 19, 2019

 気付いたら3時半になってて慌てて寝ました。

Day3

shiroに叩き起こしてもらい事なきを得ました。(一人だったら確実に寝坊していました)起きた後definitely unratedをみて絶望。

ギリギリ朝飯を食べる時間もあり、余裕をもって到着…あれ？？

ちゃんとした時間に起きてちゃんとした時間にご飯を食べてちゃんとした時間にチェックアウトを済ませたのに遅刻をした
人はなぜ

— ツバサ (@emtsu_ba) September 20, 2019

～コンテスト(北大セット)～

NOSSさん、Enderedさん、自分の3人でチームACPC_ROUSAIで参加しました。

自分がAを通し、Bが重いということでEnderedさんがBを詰めている間NOSSさんがC、Dの考察、自分がCの考察をしていました。

なかなかCの良い解法が思い浮かばずにいると、Dを中心に考察していたNOSSさんが急にCの解法を思いつき、教えてもらいました。

直後にNOSSさんがDの実装を終えAC。Enderedさんと交互に実装し、前日に知ったnext_permutationを、レファレンスを見ながら書いていました。

どちらもWAを吐かれてしまい、3人でバグ処理をすることに。しばらくするとEnderedさんがBを直してAC、その後やっとCのコーナーケースM=0を見つけてなんとか通す。全員がこのコーナーケースで引っかかっていたようで、作問者天才だな～と思いました。

その後全員でEの考察をしました。見た目完全にセグ木だなーという話になり、自分は全くセグ木を理解していないので悲しくなりました。Enderedさんが考察部分を詰めていて、その間にNOSSさんが実装をし、自分はテストケースジェネレーターになりました。

インデックス部分が大変そうで、惜しくも生成したテストケースの一部がおかしくなり、4完で終了となりました。

コンテスト後、会津大学の食堂でソースカツ丼を食べました。500円でめちゃくちゃ満足してしまいました。W大の食堂よりも…(おっと誰か来たようだ)

そこでこどふぉが実はsemiratedだったことを知り、青になれたな～とウキウキしながらこどふぉのページを開きました。

二度とやらんわこんなクソゲー

東京に着いた後、おきもちさん、りあんさん、ツバサさんとラーメンを食べました。

東京に帰りました#acpc2019 pic.twitter.com/iOQ64fef0V

— suta (@suta28407928) September 20, 2019

 煮干しラーメン最高か？？

感想

A,Bしかまともに太刀打ちできる気がしなくて辛かった反面、数人で考察を詰めたりするのが楽しかったです。周りに圧倒的に強い人しかいない環境がとても新鮮で有意義でした。色々勉強しなきゃいけないところが見えてきたので、引き続き精進を頑張ります。来年はもう少し強くなって、ACPC全参加者の平均レート以上にしてからまた参加したいと思います。

初めてのオンサイトでしたが、とても楽しく過ごすことができました。ありがとうございました。