noya2のブログ

noya2の精進記録

yukicoder380 開催記

はじめに

しょぼん (@shobonvip) / Twitterさんと共同でwriterをしました。ご参加くださった皆様、ありがとうございました。

2週にわたって開催することにしました。2週目は3/24(金)の21:20~23:50(2.5h)です。こちらもぜひご参加ください。

年が明けて1/11にshobonvipさんに共同writerコンテストの開催をしようとお誘いして、快諾してもらいました。春休みの開催に向けてとりあえず問題をどんどん挙げていこうということで、たくさんの問題が集まりました。自分は春休みに入って競プロしかすることがなくなり、多めに問題を提案してしまったので、shobonvipさんにはかなり負担を強いることになってしまいました。付き合ってくれて本当にありがとうございます。

shobonvipさんも自分も、AtCoderやCodeforces、yukicoderのコンテストには欠かさず参加しており、準備期間中はその反省会も含めて競プロの話題でかなり盛り上がりました（もっとも、自分が競プロ以外なにもしていないため、他の話題はないわけですが...）。その中で、たとえ星の少ない問題だとしても、解いてくれる人に少しでも面白いと思ってもらったり気づきを与えられたりしたらいいなぁ、という共通認識が生まれていました。考察ステップをいくらか踏むような問題を目指しましたが、私はそういうことを狙った作問をしたことはないので、数を打って当てるに限る、という気持ちで作問していました。

各問題へのコメント

自分がwriterをした問題は、作ったときのエピソードがあれば書きます。

Friday

開催1週間前には2問目のWACが1問目に置かれていて、合計6問でした。改めて見直してこれが1問目なのは攻めすぎ、という判断になり、前に1問足す運びになりました。脳内でランダム作問ガチャを回すと4回目くらいでこれが出てきたので、事なきを得ました。作問ガチャの回し方ですが、「今日はフライの日。」を第1文に固定し、それにつながるようにアジフライとエビフライを登場させよう、という大枠のみ決めていました。

WAC

WAとACで何か作れないかなぁと作問ガチャを回していると、1回目でレアを引きました。ラッキーです。それなりに考察要素があって、解き終わってみれば典型に分類されてもおかしくないですが、個人的に好き寄りの問題です。

Reach 1

shobonvipさんの提案から30分くらい悩んだ後、想定解に辿り着きました。考察はそこそこ難しいのに実装がギャグで、好きです。数学色が強く、難易度評価に困りました。

Cities and Teleporters

このセットの典型実装枠1です。解法はすぐに浮かびましたが、実装がやや難でした。雑にやると落ちるケースをたくさん用意してもらいました。

Coaching Schedule

このセットの典型実装枠2です。昔のABCの問題を誤読して生まれた問題ですが、解けたので出題しました。素直な包除原理でFFTで高速化できる形になりますが、その前に1ステップ工夫が必要で、これは以前のABC-Gに出ていたテクと同様です。組み合わせたら星4は付くだろうという予想でした。高度典型ではあるので、星をたくさんつけたのは保身の意味もあります。

Integer Complete

shobonvipさんに提案してもらった当初は別の素数の分布に関する予想をもとにした問題でしたが、紆余曲折あってルジャンドル予想をもとにした問題になりました。知っていないときついですが、知っていると考察も実装もスムーズに進むと思います。

Second Smallest

来週の分も含めて唯一、ストックから出した問題です。明らかな典型要素がありますが、「グリッド上のどの最短経路にも高々1つ」という条件がうまく表せることに気づいたのが嬉しかったので、セットに組み込みました。数学色が強いですね。

さいごに

面白い問題が作りたい、という気持ちで作問をしていますが、実際に万人に面白いと思ってもらうことはやっぱり難しいですね。私が作問のときに意識しているのは、少なくとも自分が面白いと思う問題を出そう、ということですかね。「問題文が面白い」「設定が面白い」「考察が面白い」「想定解の実装が面白い」「解説が面白い」「解説が天才」「サンプルケースが面白い」など、”おもしろ”要素はいろんなところに入れられるので、多様な面白さを意識するとよいかもです。 あと、意外と重要なのは「解説を充実させる」ことかもしれません。B問題（WAC）の解説には力を入れました。解説は問題の完成度の高さを保証してくれる要因のひとつであり、競プロ勉強のよい資料となる指標のひとつでもある、と思っています。まぁ、なんやかんや書きましたが、作問は楽しいです。自己満足の面も大きいですが、みなさんに楽しんでいただけたなら幸いです。

3/24のコンテストはよりパワーアップしたセットとなっているので、ぜひご参加ください！

Codeforces で Masterになりました！

2022/08/19までのレート遷移

CodeforcesでMaster(レート2100以上)になりました。名前が薄橙色で嬉しいです。大学1年生になって深夜に時間を取ることができるようになったので、Ratedはなるべく出るようにしました。AtCoderの方は高1の終わりからずっと参加していて、大学1年生になったときは青でした。そのままAtCoderでは停滞を続けているうちに26回の参加を経てCodeforcesではレートを700程度上げたことになりますね（Codeforcesでははじめのレートが1500ですが、競プロを始めてすぐのときに1回出て-111を食らったので）。これから先の停滞が怖いですが、精進を続けていこうと思います。

AtCoderの停滞をはやく脱出しないと...！！！

AtCoder Beginner Contest 260 参加記

ooooox--

A問題. 場合分けを極力避けた実装をした. 各文字が何回出現したかを管理.

B問題. 実装量が大変なことに. std::sort に投げる比較関数を3つも書いた.

C問題. 再帰関数で書こうかとも思ったが, 冷静になるとレベルが $1$ 減ると石がどのくらい増えるかが分かる. 赤, 青の宝石の数を $A,B$ とするとレベルが $1$ 減るごとに $(A,B)\longmapsto (A(X+1)+B,AXY+BY)$ となる.

D問題. std::set を用いて山の先頭をシュミレーション. atcoder::dsu を用いて山の中身とサイズが管理できる. ちょっと前にstd::set の lower_bound を履修したので簡単に書けた. 山のサイズが $K$ になったら ans[dsu::leader(p[i])]=i などとして, 最後に rep(i,n)ans[i]=ans[dsu::leader(i)] などとすればよい.

E問題. 条件を満たす区間の右端を伸ばしてもやはり条件を満たす. よって左端を固定したとき条件を満たす最も左の右端を見つけたい. 素直に左端を昇順に動かしていく. はじめは最も左の右端は $\max _i(A_i)$ であるが, 左端が $A_i$ を超えた $i$ については $\max _i(B_i)$ を計算する必要がある. コンテスト中は思考を停止してセグメント木を用いたが本当に素直に処理すれば良い.

F問題. $T$ が小さいことに注目して $\Theta(T^2)$ の解法を考えたが分からず. ひとつ見つけさえすればいいので鳩の巣原理に思いを馳せるも $V_2$ 側の要素を固定した全探索が頭から離れずいい案が思い浮かばなかった. upsolve で冷静になると, $T^2$ はループ側ではなく鳩の巣側にすれば良いことに気づく. つまり, $V_2$ の中から $2$ 点選ぶ方法は高々 $T^2$ 回なので, $T^2+1$ 回 $V_2$ の中の $2$ 点を見ると必ず既に見たことがある $2$ 点が出てくる. よって, $V_1$ の頂点を順に見て, その頂点に接続する $V_2$ の頂点のうち任意の $2$ 点を見れば良い. 見たことがあるかを管理する配列には $V_1$ のどの頂点に見られたかを記録すれば良い.

G問題. コンテスト中はほとんど見ていないし考察も全くしていない. 変な imos法と呼ばれているらしい. 階段状の領域への加算を斜め方向に累積和を考えてimos法と同じように処理すれば良い. 累積和をとる回数に対して線形 ($2$ 倍)の点への加算をすれば良いので大変有用だと思う. 今回は $3$ 方向に累積和を取るので $6$ 点に加算をした.

Ex問題. 見ていません.

Codeforces Global Round 21 参加記

ooooo---

A問題。$z$ が大きくなることはないので、高々 $1$ 回のみ操作を行えばよい。

B問題。$l=1,r=n$ として $2$ 回操作すれば必ず達成できるので $0,1,2$ のどれかが答え。

C問題。操作 $1$ の逆操作が操作 $2$ であることに注目すると、$a,b$ にできるだけ操作 $1$ を適用したときにそれらが一致するかを確かめればよい。愚直には持てないのでランレングス圧縮して持つ。

D問題。単調増加または単調減少な連続部分列の両端以外の要素は経由しなくてもよいので削除。このとき数列の増加減少はジグザグしているため、$1$ から $n$ に向かう際に戻らなくてよいことが示せる。ここで、毎回貪欲になるべく遠くまで進んでもよいことをエスパーした。これは区間min,maxのセグ木をそれぞれ持ってセグ木上の二分探索と組み合わせることでシュミレーションできる。

E問題。二項係数の和の和になる。$\displaystyle\sum_{k=0}^{n-1} {}_{m+k}\mathrm{C}_m= {}_{m+n}\mathrm{C}_{m+1}$ を用いれば高速に求められる。$a$ が $n+1$ 要素で与えられることになかなか気づけず悲しいことに。

F問題。なにこれ、入力形式に悩まされる。考察をしてみるも何の情報も得られそうにない。結局最後まで分からず。

G問題。見てません。

H問題。見てません。

AtCoder Beginner Contest 257 参加記

ooooooo-

A問題。$\lfloor\frac{x-1}{n}\rfloor$ 番目(0_indexed)の英大文字を出力すればよい。

B問題。左から $i$ 番目の駒の位置 $a[i]$ の配列を持ってシュミレーション。

C問題。体重でソートしておく。候補となる $X$ は $W_i$ と $W_i-\varepsilon$ だけとしてよい。同じ体重の人に気をつけて map<体重,pair<その体重の子供の人数,その体重の大人の人数>> などとして管理。候補となる $X$ の昇順に $X$ 未満の体重の子供と大人、$X$ 以上の体重の子供と大人の人数をそれぞれ更新しながら全部試せばよい。難しい。

D問題。答えで二分探索。上限に気をつけないといけないが、3WA した。$S$ を決め打った後は愚直にグラフを構築し bfs などで愚直に判定しても余裕で通る。

E問題。桁数が分かる。最も安い値段でその桁数を稼ぐとして、余った予算で上の桁から貪欲に大きくしていけばよい。

F問題。テレポーターと言えば超頂点。超頂点 $A,B$ を用意する。$(0,v)$ の辺は $v\rightarrow A, B\rightarrow v$ の辺を張ることにする。未確定のテレポーターの行き先が $k$ だとすると、構築したグラフにさらに $A\rightarrow k,k\rightarrow B$ の辺を張ったグラフの最短経路問題になる。これは $1\rightarrow N,1\rightarrow A\rightarrow k\rightarrow N,1\rightarrow k\rightarrow B\rightarrow N,1\rightarrow A\rightarrow k\rightarrow B\rightarrow N$ の $4$ 通りの経路を考えればよく、始点を $1,N,B$ とした各頂点への最短経路を前計算することで任意の $k$ に対して $\Theta (1)$ で求められる。

G問題。後ろから見るDPを考えると、任意の $t$ の suffix に対して $s$ との lcp(longest-common-prefix) を求めたい気がする。ACLのz-algorithmをよく読むと $s+t$ に対して適用すればよさそう。あとは区間最小値一点更新のセグ木を用いて高速化。文字列にあまり慣れていないが通せてよかった。

Ex問題。とりかかった時点でのAC数があまりにも少なくペナもたくさん積んでいたため絶望。問題文を読むと $2$ 乗和の期待値の話をしていて、期待値への苦手意識もあって厳しい気持ちに。結局分からず。

AtCoder Beginner Contest 256 参加記

oooooo--

A問題。1<<Nでok。

B問題。後ろから見た累積和が4以上の個数。

C問題。左上 $2\times 2$ マスを全探索。

D問題。imos法の要領で $0$ とそれ以外が切り替わる位置を管理。

E問題。連結成分ごとにループはちょうど $1$ つ存在するので、それを atcoder::dsu で検出して、ループに沿って最小値を求める。はじめ全体が連結だと思っていてループに沿う手順を $\Theta ($ ループの長さ $)$ ではなく $\Theta (N)$ で雑に処理していたため TLE した。修正して AC したが 2WA はつらい。

F問題。$C$ を持って区間等差数列加算区間和取得の遅延セグ木を書いた。頭をバグらせたのでかなり時間をつかった上、嘘考察もして 2WA 。寄与を考えると $i,i^2$ が出てきて嫌な気持ちになってしまったが、よく考えれば $iA_i,i^2 A_i$ を別物と見てそれぞれの区間和セグ木を書けば十分だと分かる。

G問題。漸化式を立てることを一瞬思いついたが、実験コードからのエスパーに迷走。$N=3$ のとき oeis に怪しげな式 $\displaystyle\sum_{k=0}^{D} {{}_D\mathrm{C}_k }^3$ があるので $3$ を $N$ に読み替えて実装すると $N\neq 3$ で破滅。ここでまだ諦めずに実験して何かいい性質を...とか思ったのが敗因。コンテスト終了後、丁寧に漸化式を立てると行列累乗になるので実装して AC 。悔しみの舞。

Ex問題。見ていません。見ます。