人生の時間あと5倍ほしいけど5倍もらったところで有意義には使えないんだなあ
コンテスト
UTPC
去年（UTPC2023）はContestantとして参加したが、今年から作問・運営の側に入った。
原案締め切りの前日に駆け込みで提案した問題が本採用された。運営陣からも気に入ってもらえたようで嬉しかった。
UTPC内ではCのWriterとEのTesterをした。
UTPC2024-C
実験からの行列推理で解けてしまうこともあり多めに解かれる想定であり、結果は40ACとセット内で5番目だった。推理で解いたという声も一定数あったようだが、是非理詰めで解いてほしい。
ポケモンカードの「マサキの転送」というカードの効果を見て思いついた。袋に入る集合としてありうるものの通り数を実験で求めたところ妙に規則的な値が現れ、考察を進めると組合せ的に解釈できた。
UTPC2024-E
元々第2Testerの予定だったが、事情により代わりに第1Testerを行うこととなった。ちょうどTesterをする時期がCPU実験の大詰めと被り、しかもメインのノートパソコンのPythonが古くWriter解を動かせないなど大量のトラブルに見舞われて大変なことになっていた。想定解の実装も重く作業が当日の午前4時半まで続いていた。その割に本番0ACだったので少し悲しい。
ABC397
oooooo- (3) 440位 Perf1903相当
Fがよくわからずゆっくり考えていたら実装がギリギリになってしまい、通ったのは終了1分前だった。 DEFどれもそこまで簡単じゃないと思う......
ABC398
oooooo- (2) 290位 Perf2025相当
Fは見たことがあったので考察が0秒で完了した。tRue君ありがとう...... Gは孤立点の存在に気付いていなかった時点でダメそう
https://mofecoder.com/contests/tsg_live_13/tasks/tsg_live_13_f
この速解きでレートが決まると思うとゾッとする
ARC195
ooo-- (5) 335位 Pef1863 2110→2088 (-22)
Aでchminを1ヶ所忘れて1ペナ。Bで $2000 \times 2000$ をmapで座圧しようとしたらTLEして、原因に気付かず4ペナ。 $O(N^{2} \log{N})$ は通るんじゃなかったのか？？？
Cでの必要条件の絞り込みは早々に完了し、構築もすぐに完了はしていた。実装に時間を取られ......
Dの条件までは出せておくべきだった
AGC071
o-x-- 278位 Perf1971 2088→2077 (-11)
chinerist先生
A: とりあえず手元で分割方法をいろいろ試してみる。分割の様子を木にして考えてみると、左右の子の偶奇によって下へ伝播される情報（「この区間全体に[A_L ... A_R] の総XORがかかっている」）が異なることに気付く。特に、分割の反対側が奇数の場合、上から伝播された情報は打ち消しあって消えてしまうことがわかる。さらに考えると、偶数を偶数2つに割る場合も最終的に奇数2つに割ることになるため上から情報を下ろさなくてよい。奇数を奇数と偶数に割る場合、奇数を分割してできた長さ1の区間に最初の区間全ての情報が渡り、それ以外の情報は打ち消しあう。偶数を奇数と奇数に割る場合も同様。
したがって、奇数長を偶数2つと1要素に割るか、偶数長を1要素2つと偶数長3つに割るか、偶数長を偶数長2つに割るかの選択肢を区間DPすれば残りは求まる。定数倍が軽く $O(N4)$ も通った。
これに2時間かかってるの遅すぎって感じ
C: 二部グラフがYesに必要なことは分かったが二重頂点連結成分分解は出て来ず......
パ研杯2024
A(100) D(25) G(7) 132点 62位
眠かったのでチョイ参戦
遅延セグ木をソラで書けなかったため、終了...... 残りの時間Gに粘着するが進捗無し
過去問
ネタバレ注意
AGC055-A (Diff 1348)
Submission #63733994 - AtCoder Grand Contest 055
長さ $3N$ の文字列を $N$ ずつに区切るのは見えた。Birkhoff-Von Neumannの定理を思い出すと、二重確率行列を置換行列の和で表すのと状況が似ていることに気付く。残りはHallの結婚定理よりマッチングを1個ずつ取れる。（離散数学で習ったパート）
AGC055-B (Diff 2059)
階段を引くのは典型 残りが「同じ文字3連続を選び、別の文字に変えてよい」になるのであとは不変量ガチャ
ARC105-D (Diff 1871)
4年間温めておいた 証明：AC
→解説読んだ N偶数かつ後手が真似っこ戦略をとれる場合のみ総XOR=0が達成可能、そうでない場合どれか1つに集めることで過半数のコインを1つの皿に集中できることから総XORを0以外にできる
ARC112-C (Diff 1913)
これも4年間温めていたやつ ゲーム系苦手......
「頂点 $v$ を先手が取った時の利益」を木DPで求める。部分木の頂点数が奇数ならば選んだあと手番交代、偶数ならば連続で部分木を選べる。選んだ部分木の利益は相手が取るので、相手は自分の利益が最小となる部分木を取らせてくることがわかる。
偶数の部分木について、損するものは自分が取ること確定。得するものは手番が最後の人、すなわち奇数の部分木が奇数個なら相手、偶数個なら自分が取ることになる。奇数の部分木については利益が小さい方から交互に取ることになる。
ARC114-C(Diff 2056)
解説チラ見AC 4年間温めてたやつ
基本的に数列1要素につきコストを1払わなければならず、 $A_{i}=A_{j}$かつ $i<k<j$ なる任意の $k$ について $A_{i} < A_{k}$ だったらコストを払わなくてよい。そのようなペアの個数を頑張って数え上げる。
ARC146-C (Diff 2428)
「$S$ の空でない任意の部分集合について、要素数が奇数か総XORが0でない」という条件を言い換える。前者の条件を削除するために、以下のように問題を言い換える。
$2^{N}$ 以上 $2^{N+1}$ 以下の整数からなる集合 $S'$ について、任意の空でない部分集合の総XORは0ではない。そのような選び方は何通りか。
さらに言い換えると、結局以下の問題を解けばいいことになる。
集合 $S'$ から基底を選ぶ方法は何通りか。
あとはこの記事を参考に数え上げる。サイズ $0$ , $1$ などの自明な場合は処理可能。サイズ $K$ の基底ができているとき、$K+1$ 番目の要素として追加していいものは 種類ある。 (集合から奇数個選ぶ方法と偶数個選ぶ方法は等しいことから、ちょうど半分はMSBが1で残りはMSBが0、MSBが1の方は $S'$ の要素に干渉する ) あとは適当に足していけばOK
Writer曰く簡単寄り600想定らしい マジで？
ARC123-D (Diff 2143)
まず、 $B$ と $C$ の両方を変化させることはないとしてよい。そうすると、offset分の変動を除いて $B,C$ がだいたい決まる。 $B$ 全体に $X$ を足し、$C$ 全体から $X$ を引いて絶対値の総和を最小化する。うまく変形すると $\sum |X-d _ {i} | $ の形の関数になるので、これは $d _ {i} $ の中央値が最適な $X$ を与える。
ARC125-C (Diff 1896)
1年塩漬けにされていた問題 LISと小さい順で交互に入れられるものを入れて頑張る
ARC137-C (Diff 2043)
実験をしまくると、通る（ぉぃ）
