要復習キュー
主に本番中に問題に取り組み、ACできなかったものたち。
ABC252-G
ABC253-G
ABC254-G
ABC254-Ex
ARC140-E
ARC141-D
yukicoder contest 343 開催記
2022/05/13/21:20~23:20 に行われた yukicoder contest 343 の単独 Writer をしました。 134 人の方々が参加してくださいました。ありがとうございました！！！
全体感想
傾斜がとてもきれいになりました。
傾斜が完璧ですか？？？ https://t.co/hsNffCuZNX
— Noya2 (@noya2ruler) May 13, 2022
B 問題は丁寧な考察を求められ、コーナーケースでの WA が続出しました。E 問題がかなり解かれた印象です。全問題の FA は 00:23:33 までに出ました。最速全完は hos.lyric さんで 00:58:14 でした。 想定解法が簡潔にかける、意外なコーナーケースが存在する、数学的考察によって時間計算量を大幅に改善できる、などといった驚きを与えられるような問題セットにしました。いかがだったでしょうか？
高度な数学的考察を要する問題を tassei903 さんと共に考察し、C,E,F 問題の tester をしていただきました。ありがとうございました！
また、全体 tester を tatyam さんにしていただきました。ありがとうございました！
A 問題
FA : SSRS さん (00:00:31)
2019 年日本数学オリンピック予選の 9 番の問題から着想を得ました。xor で表せるというのは驚きです。
kotatsugame さんに tester をしていただきました。多言語での shortest 解の実装をお願いしました。ありがとうございました！
B 問題
FA : SSRS さん (00:04:29)
鳩ノ巣原理と周期性の相性はとても良いので問題にしました。「同じ状態が現れ、その後は周期性をもって遷移する」という方針で良いですが、何を「同じ状態」だと見るかをよく考えないといけません。 $n\bmod 4$ を持たない解法で大量の WA が出ていました。上位陣にも WA が多く出た印象です。
NatsubiSogan さんに tester をしていただきました。ありがとうございました！
C 問題
FA : SSRSさん (00:11:22)
有理数を分母を小さくして評価することを考えていたら衝撃的な事実に気づいてしまったので問題にしました。$P+Q$ ですって、すごくないですか？。とはいえギャグなので拡張ユークリッドの互除法で AC することも想定しています。ファレー数列というものがあるらしく（出題するまで知りませんでした...）、それを知っていればかなり有利だったのかもしれません。
SSRS さんが強すぎた。
kotatsugame さんに tester をしていただきました。こちらも多言語での shortest 解の実装をお願いしました。ありがとうございました！
D 問題
FA : googol_S0 さん (00:14:46)
実装が比較的重めの枠です。分割統治的な概念を学んだときに作った問題です。bitDP でも解くことができるみたいです。ただ、計算量に関してはかなり注意が必要です (TLE が量産されていました)。
chineristAC さんに tester をしていただきました。ありがとうございました！
E 問題
FA : hos.lyric さん (00:13:00)
ラグランジュ補間のラグランジュ補間みたいな概念を考えたくて問題にしました。解説では丁寧な式変形により共分散の形に帰着しています。どういう解釈をすればよいのかわからず困っていますが、とにかく形があまりにもきれいになりすぎたのでお気に入りです。$N^2$ 回の $\bmod$ 割り算を落とすための制約でした。ところで多点評価というものがあるらしく、$\Theta (N (\log N)^2)$ で解けるみたいです。
hos.lyric さん、解くのが早すぎませんか？(正直、1h くらい耐えると思っていました)
nok0 さんに tester をしていただきました。ありがとうございました！
F 問題
FA : hos.lyric さん (00:23:33)
ラグランジュの反転公式を ABC 222 で学んだとき、ちょうど括弧列と二分木の対応を知りました。括弧の概念を拡張すれば同じ方法でもっと強そうな問題が解けるということに気づいて問題にしました。反転公式、まるで魔法のようですね 。ところで $\Theta (N\log N)$ で解けるみたいです。
hos.lyric さん、解くのが早すぎませんか？(正直、1h くらい耐えると思っていました)2
hamamu さんに tester をしていただきました。ありがとうございました！
AtCoder Beginner Contest 250 参加記
ooooo---
A 問題。場合分けをするのは厳しそう。四方のマスが存在するかをそれぞれ調べればよい。
B 問題。丁寧にループを回す。チェック柄は $($ 列番号 $+$ 行番号 $)$ の偶奇で色分けすればよい。
C 問題。$B[A[i]]=i$ となる配列を用意すると、クエリで動かすべき場所が分かる。右端のときは左端と swap すると思ってしまい時間をかけた。
D 問題。$q\le 10^6$ が言えるので $q$ を固定して全探索。$q$ の昇順に調べれば $p$ は今までに出てきた素数すべてが適するので、素数の個数も数えておけばよい。素数判定には atcoder::internal::is_prime_constexpr が便利。
E 問題。これ、hash 使わずに解けるのか？？と思っていた。解けるらしい。hash をいくつか考えて、hack されたら嫌なのですべて実装。結局 sum,product,xor を管理した。区間の左端が固定されているので、$2$ 回目以降に出てきた要素は無視してよいことに注意。任意の区間に対する hash 解が存在するらしいが、要素の重複を回避する方法が分からない。
F 問題。PCK 本選の過去問に 同様の問題 がある。しゃくとり解法はすぐに思いついたがバグを埋め込んで破滅。$2$ 本のベクトルが作る三角形の面積を計算するのに $10^{32}$ を超える精度が必要な方法を選択してしまい、$\sqrt{*}$ の精度のために自前二分探索を書いて TLE もいくらか出た。その後の upsolve でなんとか AC。
G 問題。ちょっとだけ見た。見たことのある雰囲気の問題だった。priority_queue が使えそう。
Ex 問題。見てません。
AGC057 参加記
ox----
AGC057 に Rated 参加しました。惨敗しました。
A 問題。部分列の包含関係が DAG になっていることから上からとる貪欲が可能。$L,R$ の桁数が違うときは $R$ より $1$ 桁小さい $R$ の部分列の最大値を考えればよい。
B 問題。答えを $W$ 以下にできるかどうかで二分探索を試みる。$A_i$ の操作による変化先は区間になるので、両端を考える。このとき、片端だけ $+W$ することで「$A$ をすべて同じ値にできるか」を imos 法で管理できる。これによって時間計算量 $\Theta (N\log N\log 10^{18})$ が達成できるが TLE する。改善案も思いつかずそのまま終了。
C 問題以降。ほぼ見ていません。自分ではとてもかなわないと思った。ただ、C 問題で $\oplus$ と $+$ について似た処理が可能であるという知見を得たので、あとで考察したい。
yukicoder contest 342 参加記
oo-oo---
A 問題。余りの余りの $\ldots$ と考えてしまうと難しく感じた。$ m $ で割った余りをとると $ m $ 未満になるので嬉しい。
B 問題。A と B のあいだ、C と D のあいだに仕切りがあるみたいなことを考えたがうまくいかず。 不変量を考えるとABだけで見た順番とCDだけで見た順番が不変に保たれることに気づく。逆に順番さえ保てばよいので二項係数。
C 問題。マージテクの計算量と実装法が分からなかった。正当性も証明できていない気がするので飛ばした。
D 問題。すべての可能性を調べるのはサンプル4で触れられているように難しいことが分かる。$a=2$ のときに $30$ 個くらいの選択肢があって $30^4=8.1\times 10^5$ なので半分全列挙ができそう。特に複雑なことはせず一般的な実装で済んだ。
E 問題。$i+j=A$ として $A$ を固定したとき、$A$ を与える $(i,j)$ がいくつあるかを数える。偶数回なら無視できることに注意する。$A=2L,2L+1,2L+4,2L+5,\dots$ のときに奇数回となるが、$(2x)\oplus (2x+1)=1$ (これは二進表記を考えると分かりやすい) に注意すればあとは $(R-L)\bmod 8$ による丁寧な場合分け。
F 問題。見てません...
G 問題。AC数を見てこちらに専念することに。ある点における回転たちをうまくまとめる問題。セグ木に乗るのか分からず、というか乗らないと思っていた。回転によって任意の $2$ 点間の距離は変わらないことに注目。操作前に適当に $3$ 点 $A,B,C$ を取って、各操作後にどこに移るかを記録しておく。操作 $s$ の直前の $3$ 点の位置($a,b,c$)と操作 $t$ の直後の $3$ 点の位置 $(a^\prime,b^\prime,c^\prime)$ について、点 $P$ の移動前の位置 $p$ と移動後の位置 $p^\prime$ が $ap=a^\prime p^\prime,bp=b^\prime p^\prime,cp=c^\prime p^\prime$ を満たすことから $p^\prime$ を計算できる。実装が分からず時間切れ。
H 問題。見てません...
