Codeforces Round 998 (Div. 3)

　Eまで。Div. 3なのにFから難しい……。

コンテストへのリンク

F. Multiplicative Arrays

　こたつがめさんの放送の振り返りを見てAC。理解した後でも難しい気がするが……。

　二項係数でどうにかする問題というのは分かるが、そこで止まってしまった。

　たとえば、k=6でn=4のときの場合の数は、2を入れる位置と3を入れる位置を考えて、4*4となる。なので、n以下のを足し合わせる場合、4*4+3*3+2*2+1*1＝30となる。

　……のように考えて、上手くいかなかった。

　このように考えるのではなく、数字を入れる箇所を何個にするか？　と考えると二項係数の和になり高速化できる。

　先程の6の場合だと、[6], [2, 3], [3, 2]の三通りがある。

　[2, 3]の順で入れるとすると、Combi(4, 2)通り。n=3, 2, 1の場合を考えると、Combi(3, 2), Combi(2, 2), 0通りとなり、その和は（公式により）Combi(5, 2)と計算できる。

　単純に素因数分解するのではなく、何をどういう順番で掛け合わせてkにしたか？　と考えなくてはいけなかった。

ALGO ARTIS プログラミングコンテスト2025 冬（AtCoder Heuristic Contest 041）

　413位という苦しい成績。

コンテストへのリンク

コンテスト後のツイート

ALGO ARTIS プログラミングコンテスト2025 冬（AtCoder Heuristic Contest 041） 400位にも入れず厳しい。
・葉が全体にいきわたるようrootとそこから出ている芽を決め、高さ10の葉の集合が減らないように高さ9,8,7,..の頂点を固定。あとは貪欲に、できるだけ高い高さで頂点を埋めていく、という方針。

— titia (@titia_til) January 19, 2025

　高さ10の頂点をできる限り増やしたい、というのは分かるのだけれど、どうすれば実現できるか分からず上手くいかなかった。

　山登りなども考えた（し、どうやらそれをやった方が良いスコアが出たらしい）が、子たちも一斉に変えなくてはならないず、高さが10より大きいものが出た場合どうすれば良いのか？　というあたりで躊躇してしまった。

これで76,108,082点出た。
ちょっと書いてある事をストレートに解釈できなかったんだけど、以下のやり方にした。
①根(高さ=0)を決めるため、美しさAの小さい順に頂点を選択し、全頂点が根から距離10以内に入る組合せを全通り求める。
②(続 https://t.co/PtKxMCVioz pic.twitter.com/VBlif4LMPb

— ツカモ (@tsukammo) January 19, 2025

　このツカモさんのツイートを参考に、コンテスト後に話題になった貪欲を実装してみた。

　根にできるだけ小さい値を割り当てたい、という気持ちは良いのだが、そのために、「Aを小さい順に見て、全点にいきわたるよう必要なだけ取る」、というのではなく、「Aを大きい順に見て、その点がなくても全点にいきわたるようなら除く」としているのが技巧的に感じた。

　ただ、その方法にさえ気付けば後は自然ともいえるか……。

　コンテスト中どうすべきだったかは悩ましい。

　自分がコンテスト中考えていた方とこの貪欲解法は結構似ているので、そこへ辿り着けたら良かったのだが、上手くいかなかった。

　DFSを試すべきだったとは思うけど、普段再帰でのDFSを書いていないため、解説放送にあるようなDFSにはちょっと慣れていないんだよね……。解説放送のDFSを再現するのに時間がかかってしまった。それだとあまり良いスコアが出なかったので、DFSの良さに気付くのもそんなに容易でなかった気がする。

　シンプルな解法を考えて、山登り/焼きなましなり、ビームサーチなりを試す、という方針の方が良かったのかなぁ。

IAEPC Preliminary Contest (Codeforces Round 999, Div. 1 + Div. 2)

　Eまで。

コンテストへのリンク

コンテスト後のツイート

D Bの分け方は一意
E 各aについてm個のうちいくつかを使ったときの減少分を全探索。x個で減少させられる量の最大値は、x-1個で減少させられる量の最大値より小さいので、減少量をソートして貪欲。
F1 左から貪欲でいいのでは？→WA

— titia (@titia_til) January 20, 2025

F1. Kevin and Binary String (Easy Version)

　端から貪欲で良いという情報を目にしてAC。

　ツイートにも書いた通り、コンテスト中も端から貪欲で良いのでは？　と思ったのだけれど、「SとTで端に同じ文字があったら消去する」という処理を入れていたためWAになっていました。

　いやこれ、まずいかも、とは思ったのだけど、検討したら大丈夫に思えたため、実装の都合で入れたんですよね。実際はそれほど実装が楽になるわけでもないのに、無駄な処理を入れたためWAになったのは悲しい。ACしなくてはいけない問題でした。

yukicoder contest 300

　ABの二完で終わってしまった。

コンテストへのリンク

No.1552 Simple Dice Game

　Writer解説とほぼ同じことを考えていたのに詰められなかった。

　解説中の、

　ベン図を考えれば、最小値が $L$ 、最大値が $R$ の数列の個数は、

・$(R-L+1)^N-2(R-L)^N+(R-L-1)^N$

　と求まります。

　という部分。この式がもっと複雑な包除原理の式になる気がして悩んでいた。

　（今回は二つの集合だけの単純な場合だけど）包除原理を使う問題は苦手なんだと思う。包除原理を疑ったらまずベン図を描いてみると改善するかな……。

No.1554 array_and_me

　自力AC。作者さんが、ABCで似た問題が出たとツイートしていたのを見て挑戦、無事ACした。あまり似ている気はしなかったけれど……。

　heapqに入れて貪欲という解法はすぐに見えたのに、heapqに詰めるものを間違えて実装に時間がかかったのは反省。

　

yukicoder contest 455

　Bまで。A,Bは制約の違う同じ問題なので、実質一完でした。

コンテストへのリンク

No.3004 ヤング図形

　自力AC。

　二項係数と階乗の数の積で表すところまでは問題ない。問題は、制約が大きいため、それを愚直に計算しては間に合わないところ。階乗たち（F[i]とする）を陽に持っては間に合わないため、どのようなF[i]を何個かければ良いか、または何個割れば良いか？　を持てば良い、というところまでは分かったが、これでもTLEだった。

　コンテスト後、冷静になれば、どのような入力でTLEするかに気付ける。

1

2 5

　を、Combi(10,8)*Combi(8,6)*Combi(6,4)*Combi(4,2)*Combi(2,0)を計算し、5!で割る、と計算しようとしていたが、これだとm（この入力だと5）が大きいとき間に合わない。

　この積が実は、10!を2=で5回割ったものだ、と気付きAC。

　うーん、コンテスト中にACできなくてはいけない問題でした。

No.3005 トレミーの問題

　トレミーの定理（覚えていなかった）の逆を使ってAC。

　解説を見ると、整数だけで解く方法があるらしくびっくり。

No.3006 ベイカーの問題

　自力ACだけど、タグに「行列」とあったのを見てしまったから自力とは言えないね……。

　行列累乗だと気付ければ解ける。漸化式を考えるのだから行列を考えるのは自然ですね。

AtCoder Regular Contest 190 (Div. 1)

　A一完。

コンテストへのリンク

コンテスト後のツイート

AtCoder Regular Contest 190 (Div. 1) Aはまあまあ速かったものの、Aしか解けず。
A 三回あれば操作可能。二回以下でできるか丁寧に場合分け。
B メモ化再帰でN^3程度の計算量にはなったが高速化できず。(a,b)が固定されているのをどう使えば良いのか……。

— titia (@titia_til) January 12, 2025

A - Inside or Outside

　ACしましたが、after contestでWAが出ました。

　ソートの仕方がまずくて、[a,b],[a,c]と、左端が同じものがあるとき、包含関係の判定がおかしかったのが原因でした。

　本番中にWAが出ていたら気付くのに非常に苦労した気がする……。運が良かった。

　

B - L Partition

　解説AC。解説放送も見ました。

　コンテスト中に考えていた再帰では間に合わなそう、ということで、何か方針転換しなくてはいけなかったのだけど、そういうとき、二項係数を考えるのは定石の一つ。考えなくてはいけない方針でした。ただ、解法ツイートなどを見てそう言われても全然思い浮かばなかったので、解くのは厳しかったかもしれない。

　また、二項係数の和を順に求めていくところも、（多分やったことはあると思うのだけど）記憶にありませんでした。

C - Basic Grid Problem with Updates 

　解説放送を見てAC。

　コンテスト中、スタートとゴールからDPして、差分計算をどうにかすれば良い……というところまでは考えていた。

　あとは、それらを用いて答えがどう表せるかが分かれば良かった。ただ、各クエリごとにmin(H, W)使って良いということにも気付いていなかったので、正解に近かったという感じではないが。

　ただ、Bよりは惜しかった気がするので、こっちに集中すべきだったかもしれない。

D - Matrix Pow Sum

　解説AC。解説放送も見ました。

　難問に思えた。実験すればある程度分かるという意見も見たけど、あまり思いつきそうにないなぁ……。

　ただ、解説放送で言及していたように、行列をグラフの経路数と見て行列の累乗をn歩進むときの行き方と捉える（たとえば、ここが参考になる）という考え方は身に着けておきたい。

　特に、「隣接行列をn乗してできる行列の各要素は、その行番号から列番号への頂点までを、そのグラフの辺をちょうどn回使うルートの総数」である。

HHKBプログラミングコンテスト2025(AtCoder Beginner Contest 388)

　Eまで五完。

コンテストへのリンク

コンテスト後のツイート

F いける場所を区間の和で表し、各区間がどこへ遷移できるかを調べる。（A==Bのときは別に実装するとして）いける場所が[x,y]のみで、y-x>=Bならば、次の障害物直前まで進んでいいことを利用して実装した。コンテスト中に終わらず、非常に苦労してACしたけど、この方針はあまり良くなかった？

— titia (@titia_til) January 11, 2025

F - Dangerous Sugoroku

　コンテスト中の方針でACしたが、実装に非常に苦労した。というか、自力じゃデバッグできず、ACしているコードとランダムテストで比較した……。

　区間で管理する方針が良くなかったのだろう。

　どこへいけるかをlistで持った方が実装しやすかったようだ。

G - Simultaneous Kagamimochi 2

　Eの正しい解法を理解し、セグ木を使うと知れば後は難しくなかった（添え字で少し苦労したけど）。

　この問題がどうこうというより、Eで間違った考察をしていたのが敗因。