2022年03月06日 (日)[AtCoder] 精進。昨日あった ABC242-F「Black and White Rooks」(黄 diff)。求めるものは読めばすぐわかる。盤面の行と列を白と黒(と中立)で分け合う場合の数。ただ、白でも黒でもいいのだけど、片方の色が何行何列を占めている場合の数が求めにくい。テキトーに配置すると想定より少ない行、少ない列の範囲内に収まってしまう。本城裕二。参考問題を知っている。ABC003-D「AtCoder社の冬」(黄 diff)。これを４か月前に解いていた>20211222。求める場合の数が一筋縄で求まらないことがわかったなら、DP で漸進的に求めていく方針も立てやすい。■提出 #29926956 (AC / 537 Byte / 715 ms)。けっこう制約が優しくて、ループ内で愚直にスキャンして掛けて足し合わせても間に合いそうではある。一応簡単にまとめられる掛け算はまとめたけども。見直していたらまとめ忘れてるところを見つけたけども。□他の提出を見て書くのだけど、ぼかしても Ruby に限るとそれは１つしか存在しないのだけど、DP を白と黒の２回やると TLE になるみたい。１回でいい理由は、白か黒の片方がきっちり X 行 Y 列を占めている場合の数が求まったなら、他方の色は N-X 行、M-Y 列の範囲にテキトーに散らしていいので、それはただのコンビネーション１つで求まる。□あと実は同じ DP だと思っていたのだけど式が違っていた。自分は包除原理の足したり引いたりを理解していないので、ある色を X 行 Y 列にテキトーに配置する場合の数から、X 未満の行、Y 未満の列に収まってしまう場合の数を引いて、X 行 Y 列をきっちり占める場合の数としている。X と Y を徐々に増やして過去の計算結果を再利用しながら求めている。解説を読んだらこちらが DP としてあちらが包除原理として両方ともが紹介されていた。■ところで昨日の結果は？ 自分のすべての提出。終了３分前に D 問題に滑り込み AC して４完最遅パフォでレートは微減。４完だけど６問解けたのでヨシ！ 前々回も似たようなことを……「３完だけど５問解けたのでヨシ！」 ABC242 は D 問題と E 問題が脳みそを絞られるような「きっつい」問題で(３回口に出た)、F 問題だけがとっても ABC らしい問題だった。D と E みたいなのは出し惜しみして ARC にまわしてくれると、ゼロ完が回避できて喜びますよ。ABC に出ても嬉しくない。