つちのこの日記

競プロと音ゲーがメインです。

ARC 145 作りました

はじめに

AtCoder Regular Contest 145 で writer をした nok0 です!参加していただいたみなさん、どうもありがとうございました!

楽しんでいただけたら writer 冥利に尽きます。

ぼくが人の作問記を読むのが大好きなので、折角なのでセットのコンセプトや各問題の一言作問経緯などをコメントしていきます。ネタバレが盛大に含まれるので注意してください。

ARC145 セットのコンセプト

前半(A-D)を考察一発の軽実装問で固めて、考察も実装も重い EF 問題を存分に楽しんでもらおうという感じのセットでした。なんと、writer の想定解では A-D の実装の合計が 30 行しかありません。

前半の意図はある程度上手くいったとおもうのですが、後半(特に E 問題)が想定より遥かに難しかったようで、ここは反省ポイントです…

前半は本当にアルゴリズム/データ構造の知識は不要で頭だけで解けますし、後半も ACL よりむずかしい高度な知識は不要なので、是非遊んでみてください!

ARC145 問題別一言コメント

A 問題 AB Palindrome

シンプルな設定ながら自然なコーナーケースもあり、かなりお気に入りの問題です。

この問題は ARC 131-F ARC Stamp が元ネタです。(元ネタの問題はまだ通せていないのですが…)低難易度は文字列を使うと生やしやすいことを前回学んで、

文字列の問題を作ろう→そういえば Stamp 押す問題あったな→文字を二種類にしたら簡単?→回文とセットにするといい感じ!

って感じで散歩しているときに生えました。

コーナーケースが 1 種類なこともあり、こるとん式(同じテストケースを何個も入れる)やマルチテストケースにするなども考えてたのですが、邪悪すぎて admin に止められました。

300 点を主張してたのですが、maspy さんが 400 点主張していて 400 点にしました。本当に変えてよかったです。  

B 問題 AB Game

簡単なゲームを数えさせる問題です。丁寧にやる力が大切?

これは特に元ネタもなくて、適当に生えた気がします。問題セットを組み終わった後に、問題名を A 問題と似た感じにしました(ARC140 もそうですが、ぼくは問題名で遊ぶのが割と好きです)。

C 問題 Split and Maximize

簡単な数え上げ問題です。実験するとすぐにわかったり?困ったら実験するの、大事です。

元ネタは UTPC 2021 Swap and Maximize (自作問) です。問題名を適当に変えて問題を作ろうとして、S から始まる単語を探してたら Split が出てきて、設定もそこから生えていい感じだったので採用しました。

D 問題 Non Arithmetic Progression Set

割となんでも通るタイプの構築問題です。想定解みたいなきれいな感じ以外にも、貪欲、乱択、なんでもあります。

元ネタは勿論(?)chinerist さんの良問、ARC 141-D Non-divisible Set です。とても綺麗な問題だったので、適当に設定を変えて出題してみました。

E 問題 Adjacent XOR

非自明な構築問題です。設定も割ときれいだし、解法も少し非自明で面白く、かなりお気に入りの問題です。少しだけ実装が重い点が玉に傷。

難易度推定を完全にやらかしました。非自明パートが 2 つあるものの、操作回数とかからやること直ぐわかりそうだし、行けるよね?って思っちゃいました。ごめんなさい。(admin さんがこれは D or E と言っていたのもあります) もともと D と E 逆だったんですが、maspy さんの指摘で E に移動しました(本当に移動してよかったです)。

元ネタは ARC 137-D Prefix XORs です。設定をめちゃくちゃパクり、数え上げから構築にしたら何故か解けちゃってびっくりしてました。逆から見るとより難しいことを maspy さんに指摘されて、逆から出題することにしました。

F 問題 Modulo Sum of Increasing Sequences

大ボスの数え上げ問題です。 コンテスト中単独 AC の leukocyte さん、本当におめでとうございます!!(何者?)

もともとはもう少し簡単だったんですが、admin さんとの議論でどんどん難しくなり、1200 点になりました。

やばそうな見た目ですが、形式的冪級数とか怖いものは出てきません。MOD の 3 乗が間に合うことがヒントです、是非挑戦してみてください!

おわりに

初めて単独 writer を出来てとても楽しかったです!たくさんの方に問題を見てもらえて、6 問全部自分の問題なのは本当嬉しいですね。

今回の ARC で温まった方、是非作問して Rated 増やしてください!!!お願いします

AtCoder橙になりました

はじめに

この記事は 競プロ Advent Calendar 2021 - Adventar の11日目の記事です。遅刻してしまいごめんなさい…

本題

競プロを始めて1年と8ヶ月、ようやく橙コーダーになることができました!

f:id:tsuchinok:20211213142913p:plain

皆さん、沢山のファボ及びお祝いリプライ本当にありがとうございます!

自己紹介は以前の記事(入緑しました!! - つちのこの日記)で書きましたし、ポエムは恥ずかしいので赤になるまでは取っておきます。 また、先人の皆さんがモチベーションの維持、コンテストの立ち回りなどの話は書いていたので、今回は別の視点から書きます。

本記事では、黄コーダーから橙コーダーになるための実力向上に役立ったことを、お薦め順に書こうと思います。

CodeForces Div.1 バチャ

  • 効果 ☆☆☆☆☆
  • 手軽さ ☆☆
  • 総合評価 ☆☆☆☆☆

最強です。ARC以上の難易度のセットを、緊張感を持って練習することができます。まったり精進をするのも大事ですが、やはりバチャは時間内に通し切ることが求められるため、考察と実装の精度力、速度力をバランス良く鍛えることが出来ます。 Upsolve をすることで新たな知識も身に付きます。

欠点としては、英語を読まなければいけない(これは利点かもしれません)、拘束時間が長い(最低2時間、Upsolveもするならばそれ以上)などがありますが、欠点を補って余りあるほどの利点があるので、是非やりましょう!

人のブログ・解説記事を読む

  • 効果 ☆☆☆
  • 手軽さ ☆☆☆☆☆
  • 総合評価 ☆☆☆☆

新しい知識や、他人の考察手順、コンテスト中の立ち回りを学べるなど、実は様々な利点があります。 知識ゲーはARC以上ではあまり出ないし、効果が微妙だと考える方もいるかもしれませんが、実は高度典型はARCで何回も出ています。実際、私が橙になった回も高度典型(k値PSP)が ARC-E として出題され、maspy さんの解説ブログを読んでいたおかげでコンテスト中にその問題を解き銀パフォを得ることが出来ました。 何より、コンテストに役立つ役立たない以前に、新しいことを学ぶのは人間の知識欲を満たすことが出来て非常に楽しいです!

記事を読むのは通勤・通学中等いつでも出来て、疲れている時でもやりやすいので、本当にお手軽です。貪欲に知識を仕入れていきましょう!

おすすめのブログ(HP?)は maspyのHP です。

AtCoder 橙diff埋め

  • 効果 ☆☆☆☆
  • 手軽さ ☆☆☆
  • 総合評価 ☆☆☆☆

AtCoderのレートは、基本的にちょっとした成功を積み重ねるよりも、一発大成功を当てた方が上がりやすい仕様となっています。そして、大成功を当てるためには異常早解きをする、もしくは自分の適正難易度以上の高難易度を解く必要があります。

高難易度を解くための練習として、橙diffを考えるのは非常に有用です。橙diffは、黄色程度の実力があれば時間をかければ大抵は苦労しつつも解けることができると思います。その経験を繰り返すことで、本番でも橙diffを通せる確率を上げていけると思います。

AtCoder 黄diff埋め

  • 効果 ☆☆☆(レートが2200以下なら☆☆☆☆くらい)
  • 手軽さ ☆☆☆
  • 総合評価 ☆☆☆

黄diffは、橙になるためには基本的に解けるべき難易度です。(といってもまだまだコンテスト中解けないことはあります…) 黄diffを埋めることで、抜けている典型を抑えられたり、ちょっとした ad-hoc の練習ができるので、特に黄色下位のうちはおすすめの精進方法です。

AtCoder 赤diffを考える

  • 効果 ☆☆☆-☆☆☆☆
  • 手軽さ ☆☆
  • 総合評価 ☆☆☆

橙diff埋めでも言及したように、高難易度を通す練習は大事です。ただ赤diffはむずかしいので、中々解けなくて大変だったり、解けなすぎてモチベが低下する危険もあります。まずは橙diffを埋めにいく方が良さそうな気がします。

作問

  • 効果 ☆☆
  • 手軽さ ☆ (原案を考えるだけなら☆☆☆)
  • 総合評価 ☆☆(楽しさは☆☆☆☆☆)

正直、作問で実力がすぐに向上するかと言うと微妙ですし、テストケースまで用意するとなるとやや面倒であることは事実です。ただ競プロの実力を上げたいのであれば、上に示した他の方法を行う方が効率はいいと思います。

しかし、作問は本当に楽しいです!自分が考えた面白そうな問題が解けた時は本当に気持ちいいですし、皆さんが自分の問題を解いてこの問題は面白かった、このテクニックは勉強になったなどと褒められるととても嬉しくなります。

ぜひみなさんにも作問を楽しんで頂きたいです!

おわりに

競プロを楽しんで続けることで、橙にまでなることができました。まだまだ知らないことばかりですし、これからも勉強していくことで強くなる余地は無限に残っているように感じています。長い道のりですが、赤を目指して頑張ります!

明日の記事は Rute さんの 「Sushiを食べながらSushiを解く」です。

Berlekamp-MasseyやBostan-Moriを使うことで殴れる問題一覧

はじめに

最近Berlekamp-MasseyやBostan-Moriで殴れる問題をよく見るので、そのような問題をメモしていこうと思います。 以下の説明はお気持ちなので間違ってる可能性が大いにあります。もし間違っている点がありましたら教えていただけるとありがたいです。

この記事ではアルゴリズム自体の解説はしません。世の中にはたくさんわかりやすい記事があるので、そちらを参考にしてください。

また、殴れる問題を見つけたらコメントやtwitterなどで教えていただけるととても助かります!

Berlekamp-Massey ってなに?

線形漸化式で与えられる数列の最初の何項かがわかっている時に、その漸化式を求めるアルゴリズムです。 計算量は、求める線形漸化式が $d$ 項間線型漸化式のとき $Ο(d ^ 2)$ です。

Bostan-Mori ってなに?

$d$ 項間線型漸化式を満たす数列の $N$ 項目を $Ο(M(d) \log N)$ で求めるアルゴリズムです。 ここで、 $M(d)$ は $d$ 次多項式同士の積を求めるために必要な計算量です。

$\bmod$ が $998244353$ のときなどは NTT を用いることで $M(d)=d\log d$ となります。 $\bmod$ が $ 1000000007$ のときは (任意modNTT を用いない限り) $ M(d)=d ^ 2 $ となります。

使い方

以上の二つのアルゴリズムを組み合わせることで、線形漸化式の導出が容易ではない(もしくはめんどくさい)場合に、愚直な解法で数列の最初の何項かを求め、Berlekamp-Masseyで線形漸化式を求め、Bostan-Moriで数列の $N$ 項目を求めることで容易に問題を解ける場合があります。

以下ではその手法が使える問題のリストをあげます。(随時教えていただけるとありがたいです)。

殴れる問題一覧

atcoder.jp

OEISを見ると漸化式が乗っているので、Bostan-Moriを使うだけです。

atcoder.jp

周期性がありそうなので、線形漸化式だと思うと、上記の手法で殴れます。

この問題は、あまりを求めるわけではないので、適当に2つの $\bmod$ を選び、復元する操作が必要です。

  • Many Bus Stops (easy) (yukicoder)

yukicoder.me

  • Many Bus Stops (hard) (yukicoder)

yukicoder.me

このように、行列累乗っぽい問題は大体線形漸化式なので、上記の手法が使えます。

  • Tetrahedron (mojacoder)

mojacoder.app

想定解法は対称性から状態を頑張ってまとめて行列のサイズを落とすものですが、この問題も殴ることができます。 愚直に最初の方を求めると、綺麗な漸化式が求まるのであとはやるだけです。

atcoder.jp

  • simple 門松列 problem Re:MASTER (yukicoder)

yukicoder.me

現在のFastest Codeは、これで殴ったものです。

  • Next Rational (yukicoder)

yukicoder.me

線形漸化式であることを信じましょう。 信じるものは救われます。

codeforces.com

周期性!(素振り)

atcoder.jp

頑張って計算すると $Ο(1)$ で解けますが、めちゃくちゃ大変です。

上記の手法で殴ると、とても簡単に解くことができます。 maspyさんの以下のブログが詳しいです。

maspypy.com

  • Good Sequence (yukicoder)

やるだけ

yukicoder.me

随時加筆します。

懺悔一覧

コンテストやバチャ等での失敗を懺悔します

一般的な話

  • 部分問題(や,制約を弱めた版)ですら,これでしか解けない → それに近いアルゴリズムを使う

例題:

atcoder.jp

  • 区間に対する操作や区間和など -> 累積の二要素への作用or演算の言い換えを考える

例題:

atcoder.jp

  • swapをすることで区間を連続にする → $B_i:=A_i -i$ の置換をした上で, $B_i$ を一致させると考えると筋が良い。

例題:

atcoder.jp

bit

  • bit 毎に見てもよい

  • クエリの順番が bit 毎に独立なことがある

期待値関連

  • 総和の期待値 -> $i$ 以上の個数の期待値を $i$ を動かして足し合わせる。 決めうち二分探索とお気持ち的には近いかも、忘れがち。

例題:

atcoder.jp

  • 終了までの期待値などでも、ここに操作をする回数の期待値の和 という期待値の線形性が使える

期待値の線形性!(素振り)

例題:

atcoder.jp

最適化関連

  • 実は自明な上界 or 下界が達成可能です!!!!!!!!!! ←解けない時には一回疑う!!!

例題: atcoder.jp

  • gcdは,一つ決めれば候補はその約数のみ $ 10 ^ 9 $ 以下の高度合成数の個数は $1344$ 個

例題: atcoder.jp

  • 最適化であっても,最終形の判定問題を最初に考えるとうまくいくことがおおい.

例題:

atcoder.jp

atcoder.jp

  • 絶対値の最大化 は max$(x,-x)$ の最大化で言い換えるとうまくいくことが多い.

atcoder.jp

atcoder.jp

動的計画法関連

  • bitset高速化でもしない限りbool配列でDPは基本的に良くない 何か情報を持たせたい

  • DPの遷移で、使用しない場合の chmax(dp[i+1][j], dp[i][j]) みたいなのを忘れない!!(やらかしが多い)

  • 結果としてありうるか状態を判定する -> 判定問題は貪欲にできる -> 貪欲法をDPに落とす の思考をスムーズに出来るようにする

例題:

https://techful-programming.com/user/event/session/I1Hs4VIF/problem/coding/18306

計算量関連

  • 素直な全探索$ Ο(N ^ 2) $ が間に合うなら,まずそれを試す.

例題:

atcoder.jp

  • 調和級数も疑ってみる(特に数列がdistinctだったりする時)

例題:

codeforces.com

置換関連

  • $i$ から $p_i$ に有向辺を貼って考えるとうまくいくことがおおい.(2点swapなどでも)

例題:

atcoder.jp

実装関連

  • bitのi番目を取る時の bit >> i & 1 この & 1 を忘れない!!! (もはやライブラリ化したほうがよくないか?)

  • if(i == j == k) とか書かない! C++pythonじゃありません!!

メンタル面

  • 落ち着く
  • 冷静になる

純粋培養競プロerの応用情報技術者合格体験期

令和3年4月の応用情報技術者試験に無事合格したので、合格体験期を書きます。

試験勉強前のスペック

都内の大学生(情報は専門外)で、かつPCいじりとかの趣味がなかったので、そこらへんに関する知識は0でした。 競プロは少しやっていた1ので、プログラミングだけは出来るかなーという感じでした。

受験のきっかけ

前回の試験の後に、合格した人のツイートが沢山流れてきて存在を知りました。 春休み暇だし、一個くらい資格取れるといいなーみたいな軽いノリで受験を決めました。

使った参考書

キタミ式イラストIT塾 応用情報技術者 令和03年 | きたみ りゅうじ | コンピュータ・情報処理 | Kindleストア | Amazon

評判が良さそうだったこの本を試験の2ヶ月くらい前に優しいフォロワーさんから頂きました。 かなり噛み砕いて書いてあって2、重度のパソコン音痴だった私にもわかりやすかったです。

午前の勉強でやったこと

自分が怠惰すぎて、気づいたらほぼ何もしないまま試験1週間前くらいになってました。時がすぎるのって早いですね。。

そこで

www.ap-siken.com

のサイトを使って午前の過去問をやってみたところ、40%くらいしか点が取れなくて絶望していました。 そこから毎日少しずつ過去問をやってわからないところを参考書で調べて、当日には55~65%くらい取れるようになりました(合格ラインが60%なので、危ない)

午後の勉強でやったこと

友人に午前が出来れば午後も出来ると言われた3ので、当日まで何もしていませんでした。4 本当に心臓に悪いので、少しは前から見ておきましょう。

当日

天才なので、起床試験に無事合格しました。5

会場に着いたら、全然人がいなくてびっくりしました。結局椅子は3-4割くらいしか埋まらなかったです。(受験料、もったいなくないですか?)

午前試験

テスト直前まで参考書を見てめっちゃ詰め込んでいました。6

午前試験はとりあえず60分くらいで全問埋め終わり、手応え6割強だな、受かってるといいなと祈りながら途中退出しました。

お昼

お昼は八王子でラーメンを食べました。八王子ラーメンを食べるのは初めてだったのですが、上に乗ってる玉ねぎがいいアクセントでおいしかったです。

ラーメンを食べながら、午後の選択科目を何にするか考えてました。この時点ではプログラミングを選択することしか決めていませんでした。

文明の力であるグーグルさんによると組込みシステム開発がプログラミングに近いらしいので、これを選択することに決めます。

残りは2つです。データベースはなんかプログラミングっぽいので選択することにして、後一つを悩んでいました。

すると国語力でシステム監査が解けるという噂を見たので、最期の一枠をシステム監査に決めました。結果的にはこれが大成功でした。

その後は会場に戻り、午後の過去問を見ながら、プログラミングはいけそう、データベース何もわからんという気持ちになっていました。

午後

解いた順番に書きます。

  • 情報セキュリティ

まともに午後の勉強していないのでそれはそうなのですが、何もわかりません。適当に埋めて次に行きます。

  • プログラミング

情報セキュリティが全く解けなくて嫌な気持ちになったので、得意なプログラミングに行きます。 全問を10分くらいで解けて、全知の気分を味わえました。

かなりプログラミングに近い内容でした。一応全部の問題を20分くらいで埋めて次に行きます。

  • システム監査

国語の試験のような感じでした。読解することで知識ゼロでも大体埋められました。

  • データベース

最後にデータベースをやります。 sql 文も大体プログラミングみたいなものだと思って舐めていたのですが、全然違ってなにもわかりませんでした。とても悲しい気持ちになりました。

全部終わったので、1時間強を残して帰りました。手応えとしては五分五分くらいでした。

結果発表

f:id:tsuchinok:20210625125155p:plain

無事合格しました! 午後の点数は、体感ですが

  • 情報セキュリティ 7点

  • プログラミング 20点

  • データベース 7点

  • 組込みシステム開発 17点

  • システム監査 18点

くらいだと思います。

感想

ギリギリでしたが、合格できて嬉しいです!

勉強の過程で、様々な知識が身につけられて面白かったです。

次に試験を受けるときは詰め込まなくてもいいように計画的に勉強しようと思いました。

競プロer向けのおすすめ科目

個人的には以下の3つがおすすめです。

  • プログラミング

緑コーダー以上なら全く勉強せずとも十分満点が狙えると思います。 正直取らない手はないです。

これもプログラミングに近い科目でおすすめです。

  • システム監査

競プロで難読な問題文を読んでいる経験があれば、これくらい読めると思います。知識をほぼ要求しないのでおすすめです。


  1. 現時点でAtCoder2200

  2. その分ページ数は多くて持ち運びは不便です(電子版のほうがよかったかも?)

  3. 要出典

  4. 午後試験の問題を見たのも、当日が初めてでした

  5. 起床試験で足切り食らう人を多く見かけます

  6. 結局直前の詰め込みは正義です(?)

AtCoder Beginner Contest 205 一言解説

30分で解き終わって暇だったので書きます。

A.kcal

$\frac{AB}{100}$ を出力します。

B. Permutation Check

与えられた配列をsortして、 $1,2,\dots,N$ になってるか確かめましょう。 std::iotaを用いると配列 $(1,2,\dots,N)$ が得られるのでこれを用いるのが簡潔でしょう。

C.POW

$C$ の偶奇で場合分けしましょう。 $C$ が奇数ならば $A,B$ の、 $C$ が偶数ならば $|A|,|B|$ の大小関係を判定すればよいです。

D.Kth Excluded

$X$ が小さい方から $K$ 番目 $\leftrightarrow X$ より小さい数が $K- 1$ 個あるという同値変形を行いましょう。

$X$ を二分探索し、判定にはsetのlower_boundを用いることでこの問題に答えられます。

E.White and Black Balls

カタラン数を知っていますか?カタラン数は競プロで頻出なので、知らなかった場合は覚えておくと良いでしょう。

知っていればあとはその考えを用いることで答えが $\binom{N+M}{N}–\binom{N+M}{N-K- 1}$ となります。

$M+K<N$ ならば答えが $0$ になることに注意しましょう。

F.Grid and Tokens

蟻本210ページのDiningとほぼ同じ問題です。辺を湧き出し口→行番号→駒→駒→列番号→吸い込み口の順番で貼ります。

aclのmf_graphを用いると実装が簡潔でしょう。

CodeForces div.1 バチャの記録

6/7からdiv.1バチャをすることになりました。

せっかくなので各回について記録と解けなかった問題の分析をメモっていこうと思います。

解けたけど消化しきれていない問題や、解けなかったけど大事そうな問題については個別に解説記事を書くかもしれません。

よろしくお願いします。

6/7 Codeforces Round #499 (Div. 1)

結果

ABCD4完

一言解法

  • A.こういうのは逆から見ます 1のやつがあったら無理で他は最小にすればよい、簡単でした
  • B.ちょっと悩んでしまった。。 クエリの回数見るとにぶたんで、最初のN回 1以上かという結果が自明なクエリを投げれば真偽が特定できます。
  • C.無限回見ました、GCDをとるだけ K進法のくだり、いりますか?
  • D.やることは割とすぐ見えて、各場所のbitを確かめてからdfsでどうなるかを決めます。実装が170行で破滅してしまいました。。

感想

A-CがDiv.1にしてはかなり簡単でびっくりしました、Dみたいな実装問でうまい実装方針にたどりつけるようにしたいです。

6/9 Codeforces Round #691 (Div. 1)

結果

AB2完

一言解法

  • A.gcdと差は相性が良いのではい
  • B.一瞬貪欲を疑ったがうまくいかないので実家のようなDPをします
  • C.逆置換をうまく処理する方法、初めて知りました(全然見えなくて飛ばした)
  • D.ARCとかにありそう、うーん
  • E.解けそうでしたが終了後に一個勘違いに気づきました。(翌日通しました、考察はEにしては軽かったですが実装でバグらせまくりました、、、)

感想

やー、CからEのどれか一つは通したかったですね。 Bで0.5出てくるのにint / 2 をして1ペナ出したの本当にもったいない、反省です。 E、めちゃくちゃ面白かったです。

6/11 Codeforces Round #580 (Div. 1)

結果

ABC3完

一言解法

  • A.+1と-1に着目するシンプルな構築
  • B.同じbitが立っている数が3つあれば終わりなことには気づいたのに、頂点数が120以下なことに全然気づかなくてロス、勿体なかったです
  • C.仮置きすると大体決まる 特定パートは未証明でやっちゃいました(反省)

感想

Bみたいなギャグをパッと通せるようになりたいです。

6/14 Codeforces Round #485 (Div. 1)

結果

ABCE4完

一言解法

  • A.多始点bfs
  • B.転倒数
  • C.反転させたやつとかにいい感じに辺を貼る、むずかしいです。。。
  • D.めんどそう
  • E.素因数ごとにイベントソートしてHL分解でパス和取得 面白かったです。

感想

Cがむずかしかった、こういうのパッと思いつけるようになりたいです。 Eはかなり好きな感じでした。

6/16 Codeforces Round #692 (Div. 1)

結果

ABCE4完

一言解法

  • A.むずかしい お気持ちでUF
  • B.こういうのは0と1集めた方がいいのでBITでシミュ
  • C.よく考えると後ろ2つ以外自由 コストが2ベキなので貪欲が正当性を持つ
  • D.めんどそう
  • E.終了後に通しました どちらもすごい面白かったです
    • 方針その1 grundy数が $ 512 $ 未満なことに着目すると、連立方程式立てて履き出せる
    • 方針その2 操作が $f(x) = \sum cnt_i x^{i}$ をxor畳み込みでかけることに対応しているので、 $\frac{1}{1-f(x)}$ みたいなのを求める invは FWTしてから各点逆元とってIFWTすればもとまる

感想

Cまで割と素早く解けて成長を感じました。Eは知見が得られてよかったです。