あああああ

オタク & 競プロ

ARC140-F ABS Permutation (Count ver.) やや別解

問題

https://atcoder.jp/contests/arc140/tasks/arc140_f

 

解説

 

公式解説では [x^N] (x+2x^2+2x^3+...)^K を 1<=K<=N について求めよというパートが出てきてここでダブリングをしていますが、別の方法を紹介します。

 

Kを固定してみると、求めたい値は

[x^(N-K)] (1+2x+2x^2+...)^K

= [x^(N-K)] ( (1+x) / (1-x) )^K

= [x^(N-K)] (2/(1-x)-1)^K

となり、ここを二項定理でバラして K - i = j とすると、

(分子) = 2^i * (-1)^j  * (N-j-1)! * (i+j)!

(分母) = (N-(i+j))! * (i-1)! * i! * j!

になって畳み込めるので、そうすると高速になります。

 

実装 (fastest)

https://atcoder.jp/contests/arc140/submissions/43458503

 

質問

[x^N] f(x)^K を K=1,2,...,について求める系って一般的ななんかうまいやり方ありますか?

ARC122-F Domination 別解

問題

atcoder.jp

 

解法

 

赤い石は RX_1 < RX_2 < ... < RX_N , RY_1 > RY_2 > ... > RY_N となっているとして良いです。

このとき、各青い石がカバーするのは区間になります。

 

青い石を1個ずつ見ていきます。(石 t と呼ぶ)

 

パターン1

x座標もy座標も自分より大きいような赤い石がない場合

この場合は、既にいくつか(0個の場合もある)の赤い石をカバーしていて、y座標を増やすと区間の左端が左へ、x座標を増やすと区間の右端が右へ進んでいき、独立に考えることができます。

 

パターン2

x座標もy座標も自分より大きいような赤い石がある場合

そのような赤い石の集合をSとします。

この場合は、初期時点では赤い石を1つもカバーしていません。

石 t が赤い石を1個以上カバーするように操作するのが最適なら、石 t はSを全てカバーするとして良いことがいえます。

 

証明: 適当にカバーしている区間を縮めて、全ての赤い石のカバーされる回数がちょうどKになるようにしておく。a, a+1 をSの要素として、石 t がカバーする区間が [l , a] という解が最適だとする。このとき、a+1 はカバーしているが a はカバーしていないような石が存在するが、その石が追加で [l , a] もカバーするようにして石 t は 1 つもカバーしないようにしても解が悪化することはない。(証明終わり)

 

このことを利用すると、だいたいパターン1と同様に考えられるようになります。

Sの要素のうち x 最大のものを s としたとき、青い石 t を 赤い石 s のところまで移動させるコストを最初に払うと、石 s での更新処理を適切に行うことでパターン1のように扱えます。

 

最後に、ここからどう解くかを考えます。

dp[i][a][b] = i 番目の赤い石までは条件を満たしていて、y座標を増やしてカバーするのに使う青い石の借りが a 個あり、x座標を増やしてカバーするのに使える青い石が b 個あるときの最小コスト と定義して更新タイミングを頑張ると N=M として O(K^3 N + NlogN) で解くことができました。

(aを増やす、bを増やす、a+b+(最初からカバーされている個数) >=K かをチェック、aを減らす、bを減らす、パターン2の処理、の順)でやったのですが、スライド最小値を使わないで O(K^4 N + NlogN) にした方が速かった

 

提出

https://atcoder.jp/contests/arc122/submissions/41292048

ARC埋め

AGC埋めてたけど延期になったからARC埋めを久しぶりにやってたら残り4問ぐらいになったのでGWで気合入れてやってみたらできた、やったね

 

(〜〜〜〜〜)って人には精進量では勝てないんですけど、一応この前ratedになってからのARC(ARC058-ARC103)全部埋めたので、面白かったり気になった問題でも振り返ろうかな

(↑パクってから気づいたけど104以降が追加されたから自分はこれになってないな、そんな...)

 

と言いつつ解いた時期がバラバラすぎてあんまり覚えていない & 今の自分から見たらなんだこれみたいなのもありそうなので適当に

 

面白かったやつ

Robots and Exits

Exhausted?

HonestOrUnkind

 

むずかったやつ

XorShift 解説見た

Donation 類題出てるし今はそうでもないかも

 

銀diff↑

文字列大好きいろはちゃん ,すぬけ君の塗り絵 2 ,Contest with Drinks Hard は ABCとかCFとか5h出てればたぶん簡単寄り

ColoringBalls ,Shift and Decrement ,Sweet Alchemy は考える必要がある

 

 

これから

ARC-Likeが5問残っててこっちもやりたいんだけど、Jewels と ModularPowerEquation!! には以前敗北していて厳しい(こっちの方が103より最近だからむずいのはそう)

あとは104〜のARC-FでAC多めのやつをそのままやろうかな

Toyota Programming Contest 2023 Spring Final 参加記

流れで書いてみた

 

 

予選

さすがに通る

 

着くまで

時間がバカすぎてなかなか寝られずに終了

腹痛を予想して早めに家を出たら大正解

前回のオンサイトとは違うんや(会場までダッシュして到着即コンテスト開始)

 

コンテスト

賞金ノーチャンだからやる気がとかの意見を見てイライラしながら俺はコンテストのために来ているんだと奮い立たせる

 

コンテスト中のこと書くの地味に初めてかもしれん、記憶なし

A

とりあえず4重ループを紙に書いて実装してサンプルが合うことを確認する

昔はどこをばらせるかでこんがらがってたけど、こういうのは行ごと列ごとの寄与を考えるとやりやすい

で、あとはどこを算数するかを考えるとまあ縦横の長さを全探索だよね、となって通す、こういう系はそこそこ得意なんだけど最上位速すぎる(rng挑戦状みて納得)

 

B

まあこれは明らかに適当な比較関数でソート

バラして確認したか聞かれたけど300点なのでもうそのまま適当に投げました

 

C

最上位bitが打ち消し合うかとか考えてたけど不要だった

B - A 以下以外不要なことに気づくと終わり

 

この時点で3位?とかでとりあえず次の速度だな、と意識

 

D

K%=Nして、とりあえず簡単な感じになる

あとは文字列アルゴで適当にやればいいんだけど思ったよりめんどくさくて、実はlog2個のSAの比較部分いじればそのままで書けたりしないか?(combinedで見た記憶)となって蟻本置いてきたことに絶望しつついじってたけど全然無理でやられた

仕方ないからSA+LCP+スパテで区間を縮める感じでゴリゴリやって通した

ペナは円環として見た時のみ区間になる、というパターンの処理を忘れてたこと

異常に時間かかってマジでゴミだった

これ通せば、というときの焦りは相変わらずでこれは慣れていくしかないと痛感

 

順位は圏外だからもう一問解く必要がある & これ4完上位だったら圏内だなと予想してショックを受けた

たしか G だけ yosupo さんが通しててちょっとして E を Nyaan さんが通して、という感じでとりあえず全部読んだ

 

E

分割統治かな〜で企業コンの1000点とかのを見に行ってまあうまくいかないのですぐやめる

 

F

最近AGCのこういう系かなり解いてまあやるならこれかなと思ったので、そのAGCらの解説と maspy さんのARC-Eの思考手順を眺めながらとりあえず実験をする

全消し条件が 3^N , 1文字残し条件が 3^N - 2^N の形でまあ必要十分条件はわかる

この時点で残り30分ぐらいで、こういう系って1時間とかで通し切るの相当厳しい事は過去問でもわかっていたのにどうして飛びついてしまったんだと後悔 (時間かけて難問を通す練習は重要だけどそれ頼りに立ち回り決めるのはまた別問題なんですね)

あとは適当な貪欲を信じてサンプルは当然合わなくてまあだとしたら簡単すぎるよねとか考えながらコンテスト終了

 

G

ほとんど考えていない

撃墜ケースを作れみたいな構築ってありそうであんまりないなと思っていたけど(意味不明なコード読ませるとかだと何がしたいんだよになりそう)今日のは綺麗な形で出てきてすごいと思った

昼食

憧れの叙々苑弁当が出てきて感動

色変祝うために叙々苑でも行っちゃおうかな〜とか考えてたけど5桁円がデフォなのは重くてランチで我慢かな...けど今回のは祝いたいしな、で迷っていたところでありがたい

1人1個のチェックとかやってないし弁当食べてない人多いから(これは交流ガチ勢が会話を優先しているだけでした orz)2個食ってもばれへんかwをしたかったんだけど、今まで食べた通常サイズ弁当の中ではトップクラスに量があって、お腹一杯になりました

ごちそうさまです

お茶は正直ペットボトルとかのを最初に配って欲しかったんだけどね

 

パネルディスカッション

upsolveタイムと行きたいところですが、惜しいところまで行ってる問題もなくて無の時間を過ごしていました

 

rngからの挑戦状

一応最近寄りの人らしくて初めて見ました

snukeさんがいないとか言ってるからAtCoderの人を集めてるのかな、と思ってたら自由色の方々が登壇してて感動

自己紹介ではユーザー名をそのまま言ってたのにrngさんが別の言い方で呼び始めてこれトップ層ウォッチガチ勢じゃないとわからないだろと思っていた

カラーコードの話、赤から変えてないのかと思ってたけど、赤のカラーコードを指定した可能性がある?どっちかわからん

 

競プロクイズ

1問目 ダントツFAはさすがだなあと思わせられた トイレでカレンダー眺めるのが好きだった人としては100を作るのは思いつきたかったなあ

2問目 解けなかった むずいことはたしかっぽい

3問目 1〜6まで紙あったら足すだろうなあと思いつつ、思考停止してしまったが 12C6になるのは何度か出た典型でした 紙実験多めプレイヤーなのでこの暗算はいける

 

雑談

まあこっちに行ってしまうよね

移動中にたぶん挑戦状出演者が目の前を歩いてて感動

 

universal cup 勢とか Muscat 勢とかICPCのチームメイトとそれらの話をしたり、今日のコンテストの話をした

下世話な話もまあ好きだけど、コンテストのために来たという気持ちもあって、競技に関係する話しかせずに終わったのはよかった

EでA_i = 1 が全てで成り立つ時にカタラン数になる理由を最初に思いついたのはかなり嬉しかった、これ今回のオンサイトのハイライトかもしれん(そんな)

F通ってるか聞かれて、確認する対象に入ってるのかとなった嬉しさ(?)と同時にTLEだとわかってるのを投げたことに対する申し訳なさを感じた

まあ今考えるとジャンル的におれでも2色下とかでなければ一応確認はするな

順位表が思ったよりCE多めでここまでCE多いことあったっけ?と思った、けどここまで崖ができてる回もあんまりないかも(8-8-9-9-10みたいなのが残ってたらこうはならなさそう?)

自分のたどり着いたところからまだ数ステップあると聞いて実力差を感じた、解説見てしまおうかな

そんな感じでまたオンサイトあったら会いましょう的な話をして終わり

 

懇親報告を聞くと、ほとんど移動せずだったのミスだったな(初めましての人ともたくさん話せたが、だいたい向こうから来てくれた感じだったので)と思った

まあコンテストバリうまくいったらウキウキで歩き回ろうと思います(個人の思想です)

 

Slovenia

3-8でやったら最初眠すぎて草だった

コンテスト直前に寝る報告する人をバカにしてたけど、イレギュラーなイベント入ってマジで眠い時は無理だわ、すみません

 

おまけ

イベント勢への待遇 > 賞金額、って感じの配分にするのどうなんだと思っていたけど、講演の人数とか見るとむしろそっちがいてくれないと開催する企業いなくなりそうでワロタ

名札わかりにくい問題はどうしようね、一応裏側にも名前書いてみた

公式配布とはいえアニメアイコンを個人で印刷してあれこれするのは微妙に抵抗がある、変えようと思ってももう遅い

 

1か0か(厳密には賞金圏内の人は順位で差が出るのでratedとやること変わらないのかもしれないけど)のガチンコの戦いはたまにやると面白いと思った

あんまり以前の企業コンのイメージと一致しない、ratedに出てもおかしくなさそうな問題が多いので、結局練習方法は変わらないし緊張関連はhighest付近維持してそういう状況を増やして練習するしかないねと思う

最上位勢はしっかり強いのさすがすぎる、上が上でい続けてくれるとやる気はめちゃくちゃ出る

始めた時期がほぼ同じな2人が上位にいるのも悔しい & さすがという感じで自分も粘っていればいつかチャンスがあると信じてがんばりたい

三大大会が減ったけど国内オンサイトの戦いはまだ残りそう(?)(AIやめてくれ〜)だからそこで表彰を目的に頑張っていくのはだいぶ方向性としてはありだなと思ったのでいけてよかった

うーん、けどEFGなんだかんだトータル5人も通してくるんだよな、まともな額を得ようと思ったら早解きお祈りではいけないということです(最近はレートも上がって目標のレベルも1段階上がってプラス1問の意識がついてきたのでいいけど)

 

UTPCも現地なので会った人も会ってない人もよろしくお願いします

~ QU4RTZ Fluffy Magic ~ 参加記

こんにちは!

ラブライブ!虹ヶ咲学園スクールアイドル同好会 UNIT LIVE! 〜QU4RTZ Fluffy Magic~

に両日参加してきました

 

今なんですが、ロスがひどすぎて死んでいます

 

QU4RTZはユニット曲が好きだったりかすみんがいたりソロ曲がお気に入りだったりで一番楽しみにしていてそしたら期待を上回る最高さだったのでそれぞれの日で特に印象に残った場面だけ感想を(day1 100点 day2 100点みたいなのをいくつかday2に移してます)

 

 

day1

第3バルコニーで涙という感じだったんですが、2列目だったのでほとんど遮られなくて距離もそこそこ近くてよかったです

奇声で話題の人が目視できる範囲にいたのが残念でしたが...

 

Make-up session ABC

もともと曲のかわいい雰囲気が好きで、楽しみにしていたんですが、サビの振り付けが生で見るとめちゃくちゃかわいかったです

 

いつだってfor you! , TO BE YOURSELF , Silent Blaze , First Love Again

4thの曲はアルバム自体は旅行に行ったタイミングで移動中に聴きまくっててすごく印象に残っていて、けどライブには行けなくて、という感じですごく後悔していたんですが、観られて大満足です。

 

で、まあライブ前の予想とかを見たり自分でしたりすると、

・人数が多いけどソロ2曲ずつやれるのか(アニメだけとか日替わりとかにして全体曲増やすなど)

・Poppin' UP! をやるのか無敵級*ビリーバーをやるのか

 

などが話題になってて、これは自分としては

元アルバムも揃えていそうなことからソロ曲の部分で差をつけることはないと信じているが安心は全くできない

Awakening PromiseやったりCHASE!やったりで意味が強い曲には柔軟な感じがするのでワンチャンはある、けどこっちも50%以上を期待できるかというとほんとにワンチャン程度(そもそも2曲やれるのかからわからんし)

という感じでソロゾーンに入った時はこれを頭に入れながら観てたんですね

 

そこでのアコースティックver→ミチノサキで衣装も変わってるしああこれはソロ1曲パターンかもしれない、と少しショックを受けて(曲自体は満足だったんですがこれはday2で)いたんですが、なななんと

 

無敵級*ビリーバー (王)(勝利)(天才)

これはさすがにday1のハイライトでいいでしょう

シルエットで気づいてイントロ流れてきたときの興奮はもう一生忘れることはないでしょう、今でもまだ思い出しただけで涙腺が

僕は自然な盛り上がりは好きなので、このサプライズでの沸き方も他とは明らかに違って鳥肌でしたね

今思うと4th曲を先にやって、そこで全体曲入れてMCも挟んで、で次にこれ、って完全に狙ってやってるな、と思います、僕はもうまんまとやられてめちゃくちゃにされたのでもっていきかた1000000000点です

今思うと、MCが途中から2人しかいなかったのが伏線だったんですね、当時は頭が死んでおり全く(マジで)気づきませんでした

今までは片方は行きたい、的な取り組み方でday2だけしか参加してなくて、そっちの方が告知あったり完成度高かったり曲数多いことあったりで結構満足はしてたんですけど、一番好きなユニットだし最近の展開的に次いつソロ曲フルでいくつも聴けるんだよってことでCD大量に積んでBDも買って、他の用事も抜けて(すみません)、で気合入れて参戦したらサプライズでday1でしかできない経験ができて最高でした

自分語りをさせてもらうと、僕は大事な大会の前には(といっても月3ぐらいはあるんですが) このMVを視聴して勇気をもらって気持ちを奮い立たせるのをルーティーン?にしていて、イントロを聞くだけでその時の気分になって汗が出てくることもあるようないろんな感情とリンクしている思い入れの強い曲なので、なんかすごくてひどい顔になってしまいました

 

Butterfly , La Bella Patria , ツナガルコネクト

という流れもあって、このあとのソロ3曲も盛り上がらないわけがないんですよね、ニヤニヤしまくりで腕振って叫んでました

あそこからのButterfly の入り最高じゃないですか?

ツナガルコネクトのコールも入れてくれたら嬉しいみたいなのを読んでから真面目に予習して望んだのでテンションmaxなのもあって楽しかったです

 

PASTEL

QU4RTZはハーモニーが魅力ですが、曲調によってその雰囲気も様々で、僕は明るかったり走ってる感じの曲が好きなのでこの曲もとても楽しみにしていました

僕のこの曲の好きポイントは、イントロがなくていきなりハモリから始まるところで、(他の曲はイントロは短いけど存在するものが多いので実は珍しめ)まあ実際聴いてみるとおおっってなりますね(魔法の色は、がなんか好きです)

 

Beautiful Moonlight

モニターに映っているのと合わせて印象に残っているのはこの曲

ここのユニット曲4連ゾーンは曲順に緩急がつけられていて、最後を大人な感じで締めるのがよかった

 

NEO SKY, NEO MAP!

よかった...

スタッフが何かを渡しているのが目を凝らすと見えて、傘がブレードに見えて繚乱かと思って(w)(最後にそれは冷静に考えるとどう考えてもないんですよね)、しかもQU4RTZでそれは違うだろオイオイオイオイとなっていたところで無駄に落差を感じて神神神セトリが確定した瞬間でした

合唱する文化を知らなかったので、day1は聴き入っていたのですが、後で調べてday2は歌いました、歌ってみるとED曲は合唱しようみたいなのがあーわかるなーという感じでエモエモでした

 

day2

最速先行なのにこの日も第3バルコニーで涙涙という感じだったんですが、なんと最前を引けてはいて、いうて1列目も2列目もたいして変わらないんじゃね?立つと高くて怖いって話も聞くし大丈夫かな、と思っていました

しかし!たった1人差であっても目の前に視界を遮るものがないというのは想像以上に大きく、低身長なことも合わせるとアリーナの真ん中よりはいいな、ぐらいに良い席で、未来ではバーチャルで全員最前みたいな話も楽しそうだなと思いました

アイドル + モニター + 舞台 + 下段の光、だけなのはほんとにかなりよかったです、東京ガーデンシアターに感謝

 

Sing & Smile!!

day2はファンミと同じ最初の曲 & 衣装になりました

ENJOY IT!は5thの記事で語ったように好き曲ランキングでかなり上位に入る好き曲なのですが、QU4RTZの世界に入るにはこれだな〜という感じでまた違った気持ちでふわふわしながら開幕することができました

 

虹色Passions! , 夢がここからはじまるよ

アコースティックアレンジで1期の大事な曲を聴けるのはここだけ!

いやここだけじゃなくて特典とかで解禁してほしいです

まさかここでもサプライズを入れてくるとはね、やられました

この日のニヤニヤポイントはここです

ところで俺やっぱり予想外のがきた時のおおってざわめき好きなんだよな、現地参加の魅力を感じる

 

ミチノサキ

某jpopみが感じられる(?)曲

曲調的にこれを最後に持ってきてユニットライブ最後にするのかな?とかの予想をしていたから真ん中に持ってこられたのは少し意外だった

ダンスが結構激し目なのがギャップで面白い

 

First Love Again

何度でも初恋してしまう

これも語らせてくれ

僕が4thアルバムで一番好きなのはこの曲で、恋愛ソング少なめ?な中でてきた曲をしっとりと璃奈ちゃんが歌い上げるという俺得な感じのやつでした

なんでday2で別で話し出したかというと、曲順なんですね

この曲をMCで一度リセットされたところで最初に持ってくるのはアップテンポな中放り込むのとはすごく違いがあって、100%それに集中し切ることができて僕は大正解だと思っています

衣装もめちゃくちゃいいですね、今回のライブで一番です

 

Swinging!

中学体育ダンストラウマ振りコピ苦手部なんですが(Love U my friendsぐらいとは思っているけどめちゃくちゃむずかしい)、このサビのスウィングは体が勝手に動いて楽しい

 

おまけ

今回は高くてヴィラ・フォンテーヌに泊まらず直帰したんですが、帰省退場がほぼ最後だとさすがに有明ガーデンの飯屋は混んでいて厳しいですね

諦めて帰路の途中で食べようとしたらday1は結構な店が閉まってるしday2は日曜だから単純に混んでるしでオタクが早食いしてそうな有明ガーデンの店に並んでおけばと後悔しました(店内BGMもいいし!)

 

フラスタってそこまで考えたことなかったんですが、プロが要望通りにきれいに作ってくれてそれで応援を伝えられるっていいものだなと思いました

僕は真面目な感想はできるだけ伝えたほうがいい派なんですが、けど鍵は外したくないなということで0.000001%にかけつつ自己満足99.9%でブログを書いていたりします

 

ところでブレード両手持ちだと手を叩きにくくてこれどうしたらいいのか気になっている

毎回手放すと拾うの苦戦しそう

 

アンケートで毎回ソロアルバムを期待しているオタクになっています、実際次はいつになるんでしょうか...(ファンミツアー、OVAがあるから早くてもそのあとなのかなあ)

 

にじたび!とりあえず東京は行きます、出演みると福岡も行きたいんだけど遠征って想像してたより金かかるんですね

まあ東京みてからでも一応間に合うのでとりあえずそっちですね

 

5thのライブBDが明日届くらしいので楽しみです

 

ではでは

 

Codeforces LGM Legendary Grandmaster になった

から偉そうに語ってやるかwと思ってたけどcampのせいで書く時間ないなと思ってたら連日ボコボコにされてマジで浮かれてたなとなって結構本当に参ったので反省のために残しておく

 

中難易度までをそこそこの速度でそこそこの割合で回収する、という戦い方しかしてない & それしかできない、のが弱点なんだけど、レート稼ぐことを考えたらこれ別にそこまで間違ってないしな、ということで変える気もたいしてなくて困った

けどラスト1時間にPC触ってる割合があまりにも少なすぎて(これはソロでもそうかも)、解法はとりあえず出た、を増やしたいという気持ちはある

 

数え上げ→どうせ俺より強い人いるからこれが一番ない

木、グラフ→なくはない 最近はこれ最後に考えてるパターンが地味に多いかも

クエリ、データ構造→全然整備してないから厳しい & やる気が微妙

文字列とか→毎回論文じゃないか?をしている気がする いまいち初手がわからなくて苦手がち 制約クソデカだから実質数学とかクエリじゃんみたいなの多いと思う

数学→頼んでしまいがちでよくない PEやってはみたんだけどこれテクの吸収むずくね?公式解説あるのはいいけどスレッド読んでもなんか頭に残らない...

笑笑笑みたいな場合わけとかネチネチパズル→やっぱりこれかな〜(間に合うとは言ってない)

 

やっぱりJOI埋めなんじゃないかと思ってきました(インタラクティブとかもあるし)

 

editorialが出てる5hを昼間にやって夜に復習、というのはかなり効率よさそうで可能性感じまくりなのでまたいつかやりたいね

universal cupの昼参加はeditorialない状態で半日upsolveできるの結構いいと思ってるんだけど、ABC/ARCだったりCFだったりが結構入ってしまうので実は時間なかったし日曜昼は寝たいしで終了

 

ところで4月から毎日1限の予定で俺どうしたらいいですか?

AGC035-F Two Histograms 別解

 

問題

atcoder.jp

 

解法

 

上の行から決めていきます。

i 行目のマスを全て決めた時、l_j >= i となる j がなるべく多くなるように k, l を決めておいて損しません。

 

いま、i - 1 行目までのマスを決めたときの l_j >= i - 1 とできる j の集合が S であるとします。

l_j >= i とできる j の集合が T となるような i 行目のマスの決め方が何通りあるかを考えます。

 

これは簡単な式になって、

T が S の部分集合でない時は 0 通りで、

部分集合の時は、W + 1 - (|S| - |T|) となります。

 

k_i は基本的には 0 以上 W 以下の全ての値を取れますが、k_i = x かつ x は S に含まれるかつ x は T に含まれない、とすることは不可能(その場合は k_i = x - 1 として x を T に含めていいため)であることからこの式が出てきます。

 

dpしたくなって、適当な係数をかければ集合のサイズでまとめて良いことから、l_j < i となった要素の個数に注目して書くと、

 

mint ans=0;

    

    vector<mint> pa(W+1);pa[0]=1;

    

    for(int t=1;t<=H;t++){

        vector<mint> ne(W+1);

        for(int j=0;j<=W;j++){

            for(int a=0;a+j<=W;a++){

                ne[a+j]+=pa[j]*comb(a+j,a)*(W+1-a);

            }

        }

        pa=ne;

    }

    

    for(int j=0;j<=W;j++){

        ans+=pa[j]*comb(W,j);

    }

    

    cout<<ans.val()<<endl;

 

このような3乗解にできます。

 

グッと睨むと結局多項係数になってるじゃん、ということでその部分をバラすと、

 

{ (W+1-i) / i! * x^i } ^ H * (1 / i! * x^i) の x^W の係数 * W! が答えになります。

 

これは結局 (W+1-x)^H * exp((H+1)*x) になるので、

(W+1-x)^H = comb(H,j) * (W+1)^j * (-x)^(H-j) の 0<=j<=H についてのsum

を利用することでO(H+W)で解くことができました。

 

提出

https://atcoder.jp/contests/agc035/submissions/39384404

 

感想

まさか自分が詰めをFPSでできるなんて!?と感動していたりする

最初は式変形が下手くそすぎてpowにしかならずに窃盗して通して、そのあともう一度考え直した、使いこなすのはまだ遠い