suta精進記

競プロ関連体験記や精進記録などを書きます

ICPC国内予選2021参加記

負の感情がこもったポエム多めです。ご注意ください

チームUHISHIROでshiro, kiyoshi, sutaのチームで出場しました。UHISHIROとしては2年目になります。

コンテスト前

今年はUHISHIRO最後ということもあってか、数ヶ月前からかなり気合が入っていて、夢中でAOJ-ICPCを埋めていました。

チーム練の感じもまあまあといった感じで、模擬国内でもそれなりの順位がとれました
模擬国内参加記

コンテスト当日

早めに大学に着いたものの、学内の久しぶりに会う人たちとも挨拶していたら16時半前になったので、呼吸を整えて開始に備えていました。

コンテスト

問題ページを開くと昨年に引き続き、問題ページが開かない→開けたと思ったらリハの問題が出てくる があってまたか~~~と言っていたら1分後くらいに問題が表示されてスタート。

いつも通りA : shiro, B : suta, C : kiyoshiで読んでいると、kiyoshiがC構文解析だ!というので即BとCの担当をswap。Cを読み始めます。

AとBが爆速で通って暫定5位くらい。調子のいいスタートが切れました。(A : 00:06:10, B : 00:06:56)

ただ、Cがまるで分からず、すぐにkiyoshiにhelpを呼び、Dの読解をshiroがやります。

Dの概要をshiroから聞いたあたりでDが解かれ始めて、これやっぱC難しくてDの方が解けるやつだねという話になり、Dを優先的に考えることにします。
この制約だからたぶんDPとかなんだろうなーと思いつつ、任意に動かせるとかなり厳しくないか?という話に。降順、昇順どちらにしてもダメで、終わりの2つ全探索とか考えてもまるで上手くいきそうな気がしなくて辛い気持ちになっていました。

そうこう言っているとライバルチーム含めた無限チームがDを解き始めて焦り始めます。するとkiyoshiが突然Cの解法が生えたらしく、どうやら全方位らしい... 気持ちはなんとなく分かりつつもあんまり書ける気がしなかったので実装もkiyoshiにお願いしました。

ここでkiyoshiから、Cの文字列を構文木にしてほしいという依頼があり、sutaが担当することになりました(これが結果的に良くなかった)。D : shiro, Cの全方位 : kiyoshi, Cの構文解析 : sutaの分担で進めました。

順位表で冷えているのを横目にCの構文解析パートでパグらせ、shiroもDで冷え、Cの全方位パートを書き終えたkiyoshiとshiroがDから離れてEに行きます。

やっとの思いで構文解析が終わり、kiyoshiに投げます。勘違い(?)で1WAが生えつつもすぐに気づいてAC。(2:04:30)←え、こんな経ってたの?(記事を書きながら気付く)

Eの解法は割とすぐに生えたらしく、shiroがEの実装、kiyoshiとsutaで炎上しているDの消火をすべく奮闘します。

Eはバグっているらしく、Dも本当に分からず困り果てていました。Dはとりあえずなんとなくの上界を考えたり、嘘っぽいようなそれっぽいコードを投げて、事前にshiroが書いていた愚直コードと照らし合わせてみることに。

色んな嘘を投げましたが、全く通りませんでした。降順にして3つとる→風船回収後また降順にシャッフルが実はok?とか、最後全探索→降順とか、なるべくデカいものとりあえず小さくしてから降順とか... 昇順/降順にこだわったものが多かった気がします。

Eの実装が炎上しているため、kiyoshiがDを離れてEに行きます。検討していくと良い感じにバグが治ったっぽいので提出→WA
Dもまるで分からずお通夜ムードに突入。
~~~
そのままコンテスト終了。本当に無力感が凄かった。ごめん........................................
Eは後で見たらなんと出力変数名が間違っていたらしいです(え)

結果

f:id:suta88:20211105234125p:plain 全体51位学内5位。ここ一番の激冷えを本番でやりました。
惨敗以外の言葉が見つかりません。

コンテスト後

うなだれながらツイッターを見ていました。Eの概要を聞くと、それ昔解いたことあるな~~となり、涙...
Dの解法が流れてきてもっと愕然。
同学年と集まって話をしたり発狂していたりしていました。
弊学のほとんどのチームがDにしっかりアプローチできていて、みんな天才なのを、実感...

解散した後ツバサさんに劔を奢っていただきました。ご馳走様でした。[ここにラーメンの写真]
コンテストの反省をしながら帰宅。電車の中で持て余して詰将棋をひたすらやっていました。

詰将棋でも分からされている図

振り返り・ポエム

コンテスト中の反省としては、まずCの構文解析を僕がやって、shiroがDで冷やしていたというのがまず挙がりました。特にEみたいなのは僕が通すべき問題で、Cのような構文解析はshiroが得意なので、完全に分担を間違えていました。
Cの構文解析のhelpがEの問題概要の伝達直前に入り、2完の焦りもあってCに走ってしまった結果明らかに最適な担当swapができていませんでした。問題概要の伝達なんて何分も掛からないんだから、絶対に聞いてから判断すべきでした。
その後はDの反省ですが、任意に並べ替え可能なんだからそりゃ確かに集合に分けるのは考えるべきだよなといったどうしようもないものにしかなりませんでした。本番中考えもしなかったなあ...
色んな反省点を挙げても、結局Dを通さなきゃ通過できない&そのDに対するアプローチが1ミリもできていなかったことで全て無になってしまい、本当にどうすればよかったのという感想しか生まれませんでした。

マジで、これ... 998244353回いいねした(引用失礼します)

元々僕(とたぶんshiroも)はこういった発想一発系が苦手で、kiyoshiがなんとかカバーしてきた面があります。それが今回kiyoshiもハマり、CとEも大変なことになってこのような結果になってしまいました。
ICPCの問題、昔とはだんだん傾向が変わってきているような気がして(writerの層も変わっていそうだし)、ねっとりよりはむしろ(ボーダー付近には)天才問題が置かれがちになっています。AtCoderではボコボコにされながらもICPC系の問題ならなんとかと思っていた矢先にこれで、辛いですね。
Fとかが解けるような実力があればまた話は変わってくるんでしょうが、1年で劇的に強くなるほどのポテンシャルが僕にはなさそうなので...というのが正直なところです。(この1年でだいぶ証明されてしまったところが...?)

なんかもうここらへんから感情駄々洩れになります。

発想一発天才問題にはもう何度もやられていて、それは重々分かっているんですが、全然解けるようにならないのが現状です。例えば不変量があるんじゃないかとか考えてみても、累積和とか個数とかxorとか試してダメだったらもう何も分からない。引き出しが少ないのかなとも思いつつ、考え抜く力が無いのかなという気持ちもあり、何をしたらそういうのに正答できるようになるのかなと日々悩まされ続けています。天才問題に限ってパフォが低いこともままあり、さらに落ち込む要因になりがちです。
パズルやなぞなぞの類も本当に苦手で、やっぱりそもそも(少なくとも)TLの人たちにはそういう部分では叶わないなあと分からされています。

いわゆる"地頭"では周りには勝てないことは知っていて、今まで他人よりも多く精進時間を割いて、パターンマッチを繰り返すことによってなんとか追いついて(?)きました。ICPCでも同じなので、こんなに精進したのにと言う気持ちはかけらもないですが、こういった冷え方をすると無力感に包まれてしまいます。本当にどうすればいいんですかね。
ここ一ヶ月、ARCの天才セットで冷やされ、AGCの天才セットで冷やされ、そしてICPCの天才セットで冷やされました。
立て続けにこういうのが続くとマジで辛いです。いっそこんな思いをするくらいならという気持ちから、競プロは本日をもって引退しま










せん!!!!!!!!!!!!!!!!
絶対に少しでも克服して来年リベンジするので覚悟しておいてください。
来年が現役最後のICPCになるので、悔いのないように頑張っていきたいと思います。

give us, MSBへ

アジア地区予選進出おめでとうございます!昨年のリベンジをしっかり果たされてしまいましたね。3月の本番に向けて頑張ってください。
5hバチャ走る時にはぜひ誘ってください。

チームメイトへ

無力でごめん。情けないぜ、助けてくれ
2年間本当にありがとう。マジで良いチームでした。
海外遠征リベンジできる機会があるといいなあ

UHISHIROについて

今年度をもってkiyoshiが卒業するので、UHISHIROも解散です。shiroとは来年も組もうと思っているので、チームメンバー1人を熱烈募集します。高3の皆さんぜひ弊学へ。(唐突な宣伝)

p.s.
ICPCを理由におろそかになっていた研究が、ヤバい。

ICPC模擬国内予選2021 参加記

昨年同様チームUHISHIRO(suta, kiyoshi0205, shiro53)で参加しました。

コンテスト前

日曜日なのでご飯どころがだいたい閉まっていて詰んだ。結局コンビニ飯に
icpcフォルダを開くのが去年のアジア大会ぶりなので、コードが残っていてエモくなる。最近過去のものを見てはエモくなってる気がするんだけど、もう老人ですか?

コンテスト

そんなことをしているとあっという間に14時になってコンテストが始まる。
いつも通りA : shiro, B : suta, C : kiyoshiで進めることにした。

Bを読む。問題文の本質が下数行だけで優しいな~という気持ちになる。解法もシグマの変数分離をすれば終わり。
もう国内Bはこんな難易度が続くのかな。某国内の「折り紙」みたいな†実装†がBに来るのもそれはそれで楽しい(?)んだけど。
最初の提出ということもあって過剰にビビりながら出す。AC(0:06:47)

Aで問題文の解釈が微妙な箇所があったらしいがサンプルと照らし合わせてなんとかなったらしく、そのままAも通る。(0:10:40)

Dを読むと文字列を半分で分けてよしなにDPをすれば通りそうな感じがしてくる。

ここらへんでCが通って(0:15:00)暫定5位くらいになっていた気がする。kiyoshiいつもCでハイパフォーマンス出してる気がしていてすごい。

Dは本当に愚直実装するとO(|S|^3)なので、少し考えることにする。二人がかりでやる問題でもないと判断し、二人にはEに行ってもらって一人で詰めることにした。
DP自体は二乗ででき、あとはreverseすることで文字列が一致するかの判定だけできればよいというところに行きついた。
これは全体reverse後の文字列との一致判定をロリハで行うことでO(1)にできるので二乗解が完成。
二乗になったら書くことを決めていたのでここで書き始める。少し添え字が煩雑だがそこまで大きな詰まりはなく書きあがった。

データセットを実行するとセグフォした。10000*10000のbool配列は手元ではきついらしい。仕方なく陽に構築することをやめてその場で判定してDP遷移を行うことにする。
セグフォが消えて1秒ほどで実行が終わった。これ二乗想定では?そのままAC。(0:41:13)

ここでEの概要となんとなくの(途中までの)解法を聞く。
まずLISをとるかどうかがそもそも怪しいという話だったが、とりあえずとってみて考えることに。
その間shiroが愚直を書いて解法の正当性を確かめるという流れになっていた。
LISをとったあとの操作は一意に定まりそうだが、実装が面倒そうだねという話になり、僕が実装することになる。
AOJ-ICPCこの問題をなんとなく連想しながら書いていた。 細かいところで唸りながら書いていたら、kiyoshiが

「これ転倒数じゃない?」
「転倒数 + N - LISじゃない?」
「あ、これ下界でしかも必ず構成できることが示せました」

と次々に口走る。爆笑 天才問題やめてください
これは実装が無なのでそのままAC(1:12:45)

Fの概要を聞く。なんかよく分からないなあと思っていたが、kiyoshiからDP解法が伝えられる。
なんかあっていそうで、オーダーも五乗には収まっていそう。実装が大変なので少し考えてから全員で書こうということになる。
dp[文字列の長さ][1の個数] = pair(転倒数のmin, それを達成する辞書順最小の文字列)を組んでいたが、その中でdpの状態から文字列を復元したり、文字列を追加してからよしなに最適な移動をさせる実装が少し大変だった。

20分くらい(?)頑張ると書きあがった。しかしバグだらけで、修正にも20分くらいかかった。
やっとのことでサンプルが合ったので、投げる。WA そんな......

しばらく考え込んでやっとおかしい箇所が見つかる。修正しようとしていると、kiyoshiが四乗解を書き終えたらしい。
実行結果を送ってもらい、自分のWA出力と照らし合わせる。IMPOSSIBLEの箇所は一致、そのほかが割と違うという感じだったので良さそうじゃない?という気持ちになる。

そのまま提出してもらうとAC。(2:25:12)俺実装担当やめてお茶くみ担当になります...

残り30分くらいでGを読むがヤバそうなケースが次々でてきて無理そうな雰囲気が漂う。
フローできない?というとkiyoshiが(負辺あり)最小費用流に帰着した。
フロー 負辺除去とかで検索するとbeetさんのライブラリを発見。実装するとサンプルが合って笑った。

がデータセットを実行しても全然終わらない。よく見ると負辺のコストの総和だけ計算量がかかるらしく、計算量大爆発。悲しい。
木という性質もクッキー2枚以下という条件も使っていないので通らないのは、そう...

無理じゃんとなりコンテストが終了。

結果

f:id:suta88:20211025002540p:plain
6完 全体19位

同学3チーム圏内の20位以内に入れたのでまずまず。MSBに負けたのは悔しい...
前回の模擬国内はボロボロだったので挽回ができてよかった。
チームとしてのパフォーマンスも悪くなかったと思う。しいて言えばFがもう少し早くACできるともっと良かったかな(誰のせいでしょうね?)。
give us、ほぼかっつ君一人で6完していて震撼

コンテスト後

UHISHIROメンバー、感想戦に大学に来たかっつ君、serpent君、たまかけ君とラーメンを食べに行った。[ここにラーメンの写真]
最近(他学年の)競プロerで集まって飯に行くことがなかったのでなんか新鮮だった。
(趣味が共通している)人と話すのはやっぱり楽しいね。オンサイト行きたすぎ

その後研究室に戻って研究div2に出た。コンテスト中の21時に強制退去を命じられてkiyoshiと近くの公園でコーディングしていた。結局F2とGは解けなかった。

感想

久しぶりのICPC国内形式で楽しかった。
最近ICPCの問題純粋に楽しい問題が増えていて、楽しい。(語彙力)
Eに天才を置くかわりに凸多角形柱工業都市とか置いてもいいんですよ!(小声)
国内予選で勝ちたい一心でAOJ-ICPCに励んでいたらいつのまにかAOJ-ICPC中毒者になってしまった。人はなぜ...
国内予選本番までにもう少し実装を早くできるようにしたい。残り1週間全力で練習していきます。

最後に、JAGの方々ありがとうございました。

AOJ 2849 Route Calculator

https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2849

問題概要

グリッドに数字または'+', '*'が与えられる。
$ (1,1) $から $ (h,w) $まで右または下への移動をするとき、通ったマスの文字を順番に並べてできる式の値の最大値を答える。
ただし$ i+j $が奇数の箇所は'+'か'*'、偶数の箇所は数字であること、また$ h+w $は偶数であることが保証されている。
式の値が$ 1e15 $より大きくなる場合は$ -1 $を出力する。

解法

$ dp[i][j][val] = (i,j)までみて現在の積の値がvalの時の最大値 $
をmapでもって回すとTLE(MLE)するので別方針を考える必要がある。

*でつながっているところを一気にみて、それらを+で連結することを考え、以下のものを求めていく。

$mul[i][j][k][l] = (i,j)から(k,l)までの積の最大値$
$dp[i][j] = (i,j)から出発するときの現在の和の最大値$

遷移できる候補は$ (i,j)→(i+2,j), (i+1, j+1), (i,j+2) $の3通り。
記号を見て遷移して良いかを見ることで適切に遷移できる。(例えば$dp[i][j]→dp[i][j+2]はs[i][j+1]=='+'のときのみ$)

  • $ mul $の前計算を先にしてから+の遷移をするイメージ
  • $ dp[i][j] $を$ (i,j) $から出発するときの最大値と定義してしまったので、$ dp[h+1][w+1] $を答える。$ s $の右段と下段に'+'を追加する。
  • $ 1e15 $まではokなのでINFの値を$ 1e15+1 $にする(ここ重要)

実装

mulを貰うDPで、dpを配るDPで書いたので分かりずらいかも。

template<typename T1,typename T2> inline bool chmax(T1 &a,T2 b){
    if(a<b){
        a = b; return true;
    }
    else return false;
}

ll mul[55][55][55][55];
ll dp[55][55];

int main(){
    int h,w; cin >> h >> w;
    vector<string> s(h); rep(i,h) cin >> s[i];
    ll INF = (ll)1e15+1;
    rep(i,h) s[i].push_back('+');
    s.push_back(string(w+1,'+'));
    rep(i,h) rep(j,w) rep(k,h) rep(l,w){
        dp[i][j] = mul[i][j][k][l] = 0;
    }
    dp[0][0] = 0;
    rep(i,h) rep(j,w) if((i+j)&1^1) mul[i][j][i][j] = s[i][j] - '0';
    rep(k,h) rep(l,w){
        if((k+l)&1) continue;
        rep(i,h) rep(j,w){
            if(i>k || j>l) continue;
            ll c = s[k][l] - '0';
            if(k>=2 && s[k-1][l] == '*') chmax(mul[i][j][k][l], min(INF, mul[i][j][k-2][l] * c));
            if(l>=2 && s[k][l-1] == '*') chmax(mul[i][j][k][l], min(INF, mul[i][j][k][l-2] * c));
            if(k>=1 && l>=1 && (s[k-1][l] == '*' || s[k][l-1] == '*')){
                chmax(mul[i][j][k][l], min(INF, mul[i][j][k-1][l-1] * c));
            }
        }
    }
    rep(k,h) rep(l,w){
        if((k+l)&1) continue;
        rep(i,h) rep(j,w){
            if(i>k || j>l) continue;
            ll res = min(INF, dp[i][j] + mul[i][j][k][l]);
            if(s[k+1][l] == '+') chmax(dp[k+2][l], res);
            if(s[k][l+1] == '+') chmax(dp[k][l+2], res);
            if(s[k+1][l] == '+' || s[k][l+1] == '+') chmax(dp[k+1][l+1], res);
        }
    }
    if(dp[h][w] == INF) dp[h][w] = -1;
    cout << dp[h][w] << endl;
}

ARC078 E : Awkward Response

atcoder.jp

解法

二分探索を考えると、問題になるのは判定したい数より大きいのか小さいのかです。
2クエリで1回の探索を以下の方法で実現できます。

判定したい数を$ n $とする。

①$ n $をクエリに投げる
②$10n$をクエリに投げる
③①と②で"Yes"と"No"が入れ替われば$ N > n $。そうでなければ$ N \leqq n $。

よって$ 2log_2 N $回で解を求めることができ、64回に収まります。

10倍しても(右端に0を1つつけても)辞書順はほとんど変わらず、数の大きさだけを変えることができるので、$ n $より大きい場合のみに対して結果を変えることで判定を行うことができます。

具体例を以下に示します。ここでは$ n = 28$とします。

①$ N = 52 $
このとき、最初のクエリでは$28 < 52$かつ$str(28) < str(52)$のため"Yes"が返りますが、10倍の280で判定を行うと$280 > 52$かつ$str(280) < str(52)$となるため、確かに結果が入れ替わっています。これは最初に"No"が返ってきたときも同様です。

②$ N = 9 $
このとき、最初のクエリでは$9 < 28$かつ$str(9) > str(28)$のため"No"が返ります。10倍の280で判定を行っても同じように$9 < 280$かつ$str(9) > str(280)$なので"No"が返ります。

int main(){
    ll l = 0, r = 1000000000;
    while(r-l > 1){
        ll m = (l+r) / 2;
        cout << "? " << m << endl;
        char c; cin >> c;
        ll M = m * 10;
        cout << "? " << M << endl;
        char d; cin >> d;
        if(c != d) l = m;
        else r = m;
    }
    cout << "! " << l + 1 << endl;
}

ICPC2020アジア地区予選 参加記

今年はオンラインでの参加です。
早稲田からは1チームのみの参加となってしまい、プレッシャーを少なからず感じていました。
国内予選参加記↓

suta88.hatenablog.com

1日目

学生証確認と練習のコンテストが行われました。
チーム名が呼ばれている様子や、judgeの使い方の説明で怪しいACが出たりしてゲラゲラ笑っていました。

f:id:suta88:20210318120814p:plain WAを出したら積極的にclarに投げていきましょう(いいえ)

練習コンは無事全完でき、ジャッジの確認もできたので一安心。
翌日の起床が怖くなってコーチに電話番号公開が行われました。 f:id:suta88:20210318121658p:plain

その後はAOJ-ICPC等を埋めたり、サークル仲間でAmong Usをしていたら2時半くらいになったので祈りながら就寝

2日目

7時半起床 起床界のtouristですって言いながらTL眺めたら無限人起床していてびっくりしました。
3人とも無事起きれたので良かった…!

コンテスト

いつも通りA : siro、B : suta、C以降kiyoshiで始めました。Aを読んだsiroが早々にkiyoshiに概要を伝えて問題をパス。kiyoshiがすぐに解法を思いついたようで難なくAC(0:16)。判断が早い。

Bを読み終わると小さい順に入れていくだけなような気がします。程なくして書き終わって出すとWAが出てしまいました。
するとすぐにsiroがhackケースを与えてくれて、悶えながら実装を修正しました。AC(0:46)

チームThe atamaが爆速でJを通しているところに目をつけたkiyoshiがJを読み終えており、概要が伝えられました。BFS/DFSでよしなにできそうだな~→できましたということで書きます。AC(1:10)
C~Kの大海原の中でThe atamaに救われたのは我々だけではないはず(?)

Gの読解に加わり、読めたところでsiroがIの読解、kiyoshiとsutaでGの考察を進めました。二分探索はできそうにないので昇順に見ていくしかないということになり、これはUnion FindとUndo可能Union Findで管理すればよいです。その時に題意を満たす条件がO(1)で判定できるが問題になりますが、kiyoshiが必要条件を見つけ、大丈夫そう(お気持ち証明)ということになり、kiyoshiに実装を任せてIの考察に加わりました。
おそらくこの動きがまずくてGの実装は自分が担当すべきでした…

Iは箱根DPっぽいという気持ちになってsiroと考察を進めますが、数字が既に1箇所だけ出ている箇所の処理が思い浮かばず1時間ほど冷やしていました。その間にGの実装をしているkiyoshiが唸っていて、大変そう…(小並)という気持ちでIと格闘していました。オフラインなのでUndo可能UnionFindすらいらないらしく、自分が実装すべきだったと後悔し始めました。

siroがIから撤退してパズルっぽいCに行きました。しばらくすると
「これ少ない手数でいけたりしないかな」
という話になり、確かにsample output 4が賢くて、右手法とかで確実に5,6手で行けるならありえそうという気持ちになりました。5手でもgoto 1~5、if open 1~5、forward、left、rightを全探索しても135×NMくらいで間に合いそうなのでとりあえず全探索を書いてみようということでsiroが書き始めました。
kiyoshiはGでメンタルが崩壊していて、sutaもIで方針が立たず苦しんでいて、気づけば残り1時間半くらいになっていました。

Gとの戦いで辛くなっていたkiyoshiが、かすれた声で
「もうこれ落ちたらしらないよ~~~~~」
と言いながら提出するとAC(3:53)。本当にお疲れ様でございました……
ここまでずっと3完のままだったので、UHISHIRO大丈夫か…?と心配になっている方も居たかもしれません

siroがCの全探索コードを書いているので、Gを終えたkiyoshiがCのヘルプに回ります。このあたりで突然Iの考察が生えます(!)

もう一度冷静にsample input 1で考えてみました。
'I'のindexと'O'のindexを上下に並べ、2回出てきている数字はカットして、数字が1回のみ出てきている数字のindexに色をつけてみます。
1 2 4
3 5 7
左から順に、'I'1つと'O'1つを同時にペアリングして同じ数字を割り当てることを考えると、各'O'のindexに対してペアリングできる'I'の場所の種類数は単調に増加していきます。すると自由に数字を割り当てられるindex(上でいう黒い数字)にi番目まででj個割り当てたという状態を持つことでDPによる遷移ができそうです。
sampleで手計算DP(謎用語)をすると答えやDPテーブルの結果が合うのでこれだ!となり実装を開始しました。
Cで二人とも頑張っていそうなのと、もう凍結段階に入っていて時間がなかったので解法の伝達は行わず、こっそり実装をします。

遷移も考察段階で詰められていたのですぐに書き終わり、提出するがWA。申し訳ないと思いながら焦っても無駄なので冷静にコードを見返すと一部カウントを怠っていた箇所があることに気付きました。修正してAC(4:19)。肩の荷がおりました。

Cは2人でバグ修正を繰り返していたので、EとHを読みにいきました。Eは概要を把握すると、最小包含円っぽいけどヤバそう…という気持ちになり、Hを読み始めます。

ここでついにCの実装が終わり、サンプルが合いました。提出するとWAが返ってきます。なんで……???と言っていたら凡ミスをしていたようで修正して出すとAC(4:41)。

その後Eの概要を伝えると無理そう~となったのでHを考察するも、K=1ですら撃沈。ジャッジに"MURIDESU"(文字列)を投げてコンテストが終了しました。

結果

f:id:suta88:20210318131427p:plain 6完21位でした。よく頑張ったと思う反面、あと1問くらい取りたかったという気持ちもあり、少し複雑です。終盤の3並列がしっかり決まったのがせめてもの救いでした。Yes!を世界に届けられたのが嬉しかったですね。
弊チームは中盤冷えがちなので、直していきたいと思っています。
21位ということで企業賞を頂きました。メルカリさんありがとうございます。

コンテスト後

専用ツール「gather」で懇親会が行われました。前半はjupiroさん、Lorentさんとお会いして話しながらYouTube Liveを見ていました。チームonionsのコンテストの様子や問題の解法の話だったりLorentさんの神記事
区間に辺を張るテクの実装例(Dijkstra法セット)と使用例 - Lorent’s diary

の話をしていました。
Yes/Noで腹筋がもっていかれました。初っ端から面白いのは、ずるいだろ

その後NOSSさんと久しぶりに話しました。NOSSさんと話すたびに思い出深いACPC2019がよみがえってきます。
当時のオンサイトでは天上界だった方々と今張り合えているということにとてもエモくなったりしていました。
NOSSさんもまた来年があるということで対戦よろしくお願いします。

cirnoさんnasatameさんふるやんさんともお話させていただきました。オンサイト時代の横浜大会の話を聞いてあああああああとなったり(語彙力…)、再び記事の話もしていました。ふるやんさんの神記事
競プロのための高速フーリエ変換

cirnoさんがヤバ問の話をkiyoshiとしているのを聞いてやべーと言いながらお菓子を食べていました(は?)

終了時刻も近づいてきて俳諧を始め、チームtsutajのTABさんとmonkukuiさんとお会いしました。国内でも地区予選でもチームtsutajとは1位差で密かにライバル意識がありました。やっぱり「tsutaj」の文字列を見ると一瞬反応してしまいます。連続する部分文字列に「suta」があるので。

まだgatherに30人ほど居るはずなのに人が見当たりません、cirnoさんが「follow」機能(特定のユーザーのところに自動で言ってくれる機能、これマジで便利、オンサイトでもほしい(え?))で探したところ、ド辺鄙なところに10人ほど固まっていて面白かった…
ピクトセンスで小学生並の下ネタでゲラゲラ笑っていました。早朝から叩き起こされていたので実質深夜ですね、うん。

gatherはここで解散となりましたが、その後も三次会(?)でボドゲやAmong Usをしていました。めちゃくちゃ楽しかったです。

最後に

いろいろな人と話ができて楽しかったです。チーム練以外でこんなにしゃべるのはいつぶりかな…
オンラインと聞いたときはとても悲しくなってAOJ-ICPCに手がつかなくなっていたのですが、徐々にモチベーションも回復して本番では楽しむことができたので良かったのかなと思います。
運営の方々はもっと大変だったと思います。本当にありがとうございました。

オンサイト渇望してるので次回は是非オンサイトでお願いします!!!横浜行きて~~~~
次回間違っても予選落ちしないように精進していきたいと思います。kiyoshiが来年で卒業ということでUHISHIROフルメンバーでの参加は次回が最後です。頑張ります。

ABC050 D(ARC066 B) : Xor Sum

問題リンク atcoder.jp

問題概要

$a \, xor \, b= u, a + b = v \,\,(1 \leqq u,v \leqq N)$を満たす$(u,v)$の組の個数をmod $10^{9}+7$で求めよ

解法

$(u,v)$ではなく$(a,b)$を数えることを考えます。
そのままでは$(u,v) = (5,9)$に対して$(a,b) = (7,2)$や$(a,b) = (6,3)$など複数通り考えられてしまうので、正しく数えられません。
アルメリアさんの記事を参照すると$(u,v)$から$(a,b)$への1対1の対応づけが分かると思います。
具体的には$a$と$b$とであるビットの値が異なる場合、必ず$a$に1を立てて$b$を0とすることで一通りに定まります。
先ほどの$(u,v) = (5,9)$に対応する唯一の$(a,b)$を$(a,b) = (7,2)$に限定しています。

$a,b$の下から$i$番目のビットを$a_i, b_i$と表すことにします。
このとき、必ず$(a_i, b_i) = (0,0)\,or\,(1,0)\,or\,(1,1)$となります。
桁dpで解くのですが、数字として考慮する対象は$v$として、各$v$に対して$(a,b)$が何通りあるかを考えることにします。
$v \leqq N$のとき、必ず$u \leqq N$となるので、$v$のみを考えて数え上げた$(a,b)$の数は全て条件を満たすことになります。
桁dpを行う際は各ビットについて$(0,0)\,or\,(1,0)\,or\,(1,1)$のいずれかを選択していく形をとります。(何も条件の縛りがないと$3^{桁数}$ということになります)
桁dpを行う上で欲しい状態は以下の3つです。

  • 現在何桁目か
  • 繰り上がりが存在するか(繰り上がりは必ず0 or 1なので状態数は2)
  • 暫定$N$より大きいか(下から見るので常に現在見ているビットが数の大小に大きく関わります)


遷移を一つづつ考えます。
①$(a_i,b_i)=(0,0)$
次の桁への繰り上がりはありません。下位ビットからの繰り上がりがあるときには、出来上がる$v_i$には1が立つということになります。

②$(a_i,b_i)=(1,0)$

  • 下位ビットからの繰り上がりがあるとき、繰り上がりがあり、$v_i$は0となります。

  • 下位ビットからの繰り上がりがないとき、繰り上がりはなく、$v_i$は1となります。

③$(a_i,b_i)=(1,1)$

  • 下位ビットからの繰り上がりがあるとき、繰り上がりがあり、$v_i$は1となります。

  • 下位ビットからの繰り上がりがないときも繰り上がりがあり、$v_i$は0となります。

暫定$N$より大きいかのフラグについて

例えば$N=10$で3ビット目を見ているとき、それまでが**11になっていたとします。10は2進数で"1010"なので、この状態を暫定で$N$よりも大きいと表現しています(この先のどこか1箇所以上で$N$より小さい箇所が存在していなければならない)
$v_i$に1を立てる時、

  • largerが確定している(フラグが1)とき→largerのまま

  • largerフラグが0のとき→$N_i$($N$の$i$ビット目)が1ならばそのままフラグは0、$N_i$が0ならばフラグは1に変わる

といった遷移になります。$v_i$を0とするときも同様に考えることができます。

答え

最終的に欲しい値としては、繰り上がりはしておらず、$N$より大きくはない(つまり$N$以下)ので、
最後に答えるべき値は$dp[m][0][0]$($ m $は桁数(適当に60などとしておいてもよいです))となります。

実装

modintのライブラリ部分は省いています

mint dp[65][2][2]; //i番目,carry,larger

int main(){
    ll n; cin >> n;
    dp[0][0][0] = 1;
    rep(i,61){
        int v = n>>i & 1;
        rep(j,2) dp[i+1][0][v==0&j] += dp[i][0][j]; //0,0
        rep(j,2) dp[i+1][0][v==0|j] += dp[i][0][j]; //1,0
        rep(j,2) dp[i+1][1][v==0&j] += dp[i][0][j]; //1,1

        rep(j,2) dp[i+1][0][v==0|j] += dp[i][1][j]; //0,0
        rep(j,2) dp[i+1][1][v==0&j] += dp[i][1][j]; //1,0
        rep(j,2) dp[i+1][1][v==0|j] += dp[i][1][j]; //1,1
    }
    cout << dp[61][0][0] << "\n";
}

AGC049 D : Convex Sequence

問題リンク

atcoder.jp

問題概要

整数$ N, M $が与えられる。長さが$N$かつ以下の2条件を満たす非負整数列の個数をmod $ 10^{9} + 7 $で求めよ。

  • $ A_1 + A_2 + \dots + A_N = M $
  • $2A_i \leqq A_{i-1} + A_{i+1} \,\,\ (2 \leqq i \leqq N)$

制約

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

解法

以降狭義単調減少(増加)を単調減少(増加)と呼ぶことにします。

一旦一つ目の条件を無視して、二つ目の条件を満たす数列を考えると、(単調減少 → )一定( → 単調増加)のようになります。
例えば$ N = 4 $のとき、4 1 1 1, 1 1 1 3, 4 3 1 2は条件を満たしますが、4 1 3 2は条件を満たしません。

数列の最小値を$ C $とし、$ i $番目で最小値をとるとします。このとき$ A_i = C $です。こうすると、問題は

  • $ i $番目まで数が単調減少し、そこから$ j (i \leqq j \leqq N) $番目まで$ A_j = C$となり、$ j $番目以降から単調増加

となる数列を数え上げるということになります。ここで$ i $番目までは必ず単調減少とすることで、各$ i $について数え上げた結果に重複がないことが 保証されます。

単調減少というだけでは実は二つ目の条件を満たしません。

  • $ i $に近づくにつれて隣接する数の差が広義単調減少

を条件として追加する必要があります。

すると、例えば$ A_{i-1} = C+1 $としたとき、必ず$ i-1 $番目より左側も隣接する数の差が1以上にならなければならないため、

  • $A_{i-1} \geqq C+1$
  • $A_{i-2} \geqq C+2$

$\dots$

  • $A_1 \geqq C+(i-1)$

が成り立っています。$ C $との差分のみを足し上げると、 $$ 1 + 2 + \dots + (i-1) = \frac{1}{2} i (i-1) $$ となります。よって1つ目の条件を考えると、$ i $は、$ i \leqq \sqrt{2M} $を満たす必要があることがわかります。
以降$ m = \sqrt{2M} $とします。数列は左から順に

  • 長さ$ O(m) $の単調減少数列
  • $ O(N-m) $個の $ C $
  • 長さ$ O(m) $の単調増加数列

のようになっています。

ここで差を1増やしたら全体の和がいくつ増えるのかを考えます。

  • $ i-1 $番目の値を1増やすと、$1 + 2 + \dots + (i-1) = \frac{1}{2} i (i-1)$だけ和が増える
  • $ i-2 $番目の値を1増やすと、$1 + 2 + \dots + (i-2) = \frac{1}{2} (i-1) (i-2)$だけ和が増える

という形になります。和が$ M $になるまでどこに何回1増やしてもいいので、これは個数制限なしナップザックのような形に帰着できます。
ここで加算する候補は$ 1, 3, \dots \frac{1}{2}i(i-1) $ であり、$ O(m) $個しかないので、和が$j \,(1 \leqq j \leqq M)$となるような場合の数を求める時の計算量は$ O(M\sqrt{M})$ となります。

$$ dp[i][j] = i番目まで単調減少としたときに和がjとなるような加算方法の総数 $$ としたときの遷移を考えていきます。 ここで$ i $番目まで単調減少と決めたら、必ず$ i-1 $番目に1以上加算しなければならないと考慮すると、以下のように遷移します。

  • $0,1, \dots , i-1$番目までの$ dp[j] $の値の和を用意し($ S $とする)、$$ dp[i][j] = S + dp[i][j-\frac{1}{2}i(i+1)] $$

これで必ず1回は加算するようになります。
また、今回は1から$ m $までの全ての$ i $における和が$ j $になる場合の数が知りたいので、$ mM $個の値全てを保存します。

また、$ C $の値は0から$\frac{M}{N}$までの値をとりますが、これを愚直にやっていては間に合いません。しかし、和がちょうど$ M $ではなく、和が$ M - (Nの倍数)$ とすることで、前処理を行うことができます(具体的には$ dp[i][j+n] $ += $ dp[i][j] $とすることでできます)。

ここから$ i $を動かし、答えを求めます。
左から$ i $番目までを単調減少区間としたとき、単調増加区間の開始地点は$i, i+1, \dots, N$が考えられます。
ただし、単調増加開始地点は$ N-m $以上でないと単調増加を始められないことに注意します(和が$ M $を超えてしまうので)

左から単調増加は、右から単調減少と考えられるので、dpの値を利用することができます。
また、各$ i $について独立になるように計算されているので、右側は$ i $から$ N $までを足し合わせたものと考えることができます。
まとめると、左から$ i $番目までを単調減少とするとき、

  • 各$ j (1 \leqq j \leqq M) $について$ \displaystyle dp[i][j] * \sum_{k=0}^{k=N-i} dp[k][m-j] $を加算する

という操作をすることで答えを求められます。ただし、$ N $が大きい場合には$N-i$と$ m $のminをとります。
シグマの箇所は先ほどのdp遷移で用いた累積和を配列に格納することで、それをそのまま用いることができます。

以上で$ O(Mm) $でこの問題を解くことができます。

実装

includeやmodintの箇所は省きました。
メモリと時間はかなりギリギリです。

mint dp[450][101010], sdp[450][101010];

int main(){
    ll n,m; cin >> n >> m;
    ll sq = sqrt(m*2) + 1;
    vector<int> a(sq);
    for(int i=0; i<sq; i++) a[i] = (i+1) * (i+2) / 2;
    dp[0][0] = sdp[0][0] = 1;
    for(int i=0; i<sq; i++){
        for(int j=0; j<=m; j++){
            if(j-a[i] >= 0) dp[i+1][j] += dp[i+1][j-a[i]] + sdp[i][j-a[i]];
        }
        for(int j=0; j<=m; j++) sdp[i+1][j] += dp[i+1][j] + sdp[i][j];
    }
    for(int i=0; i<=sq; i++){
        for(int j=0; j<=m; j++) if(j+n <= m) dp[i][j+n] += dp[i][j];
    }
    mint ans = 0;
    for(int i=0; i<=min(sq,n-1); i++){
        if(n-i-1 < 0) break;
        for(int j=0; j<=m; j++){
            ans += dp[i][j] * sdp[min(n-i-1,sq)][m-j];
        }
    }
    cout << ans << "\n";
}