2026年10月25日日曜日

SMBCプログラミングコンテスト #2(AtCoder Beginner Contest 481)

 Eが解けずABCDFの五完。

コンテスト後のツイート

E - Most Brilliant Starry Sky

 偏角ソートするだけの問題だった。
 このときの提出の偏角ソートを使って書いたらWAは取れた。が、PyPyだとTLEし、Python(CPython 3.13.7)でギリギリAC。

 偏角ソートが原因じゃないと思った原因は、atan2で書いたコードでsampleすら合わなかったせいなのだけど、これは、piを360度だと思って書いていたせいでした(正しくは180度)。これじゃ合うはずない。ひどい。
 最初に定義を確認すべきだったねぇ。

 TLE解消について。
 PyPyでcmp_to_keyを(何度も)使うときは、

A.sort(key=cmp_to_key(compare_items))

 のように書くと遅く、

ck=cmp_to_key(compare_items)
A.sort(key=ck)

 と書くと良いらしい。参考ツイート。
 このツイートは見た覚えがあるのだけど、忘れていた。






2026年10月22日木曜日

AtCoder Talent Quest 〜 今から28卒には脱出してもらいます〜予選 #2(AtCoder Beginner Contest 480)

 Fまで。

コンテスト後のツイート

G - Zonal Score Minimization

 解説放送を見てAC。

 MAXやMINをstackで持つ、ということを意識し、インラインDP。
 本質は難しくはない。多分、粘れば自力でもできた気がする。DPするしかないし、高速化するのならインラインDPくらいしかないので。

 しかし、解法の概要を理解した後も一時間くらい実装にかかっている。こういう添え字合わせとかどうすれば良いんだろう? 似た問題は結構たくさん解いてきたはずなのだけど。

2026年10月16日金曜日

オムロンプログラミングコンテスト2026 (AtCoder Beginner Contest 479)

 Eまで五完。

コンテスト後のツイート

F - Narrow Passage

 概ね自力でAC。解法ツイートは見たけど、それはあまり参考にせず解いた。
 結構時間がかかったので、Gに行かずFに集中していれば解けたかは微妙なところ。

 S[i]→T[i]へ線を結んだものを考える。
 基本的には、abs(S[i]-T[i])の和だが、交差している場合をどうするか。

・a→b(a<b)とc→d(c>d)が、逆向きに交わっている場合、答えを+1(交差するときの操作)し、a+1→bとc-1→dの操作と捉える。
・a→b(a<b)とc→d(c<d)が、c<a<b<dのように、抜かしている場合、答えを+1し、a-1→bとc+1→dの操作と捉える。

 のようにすれば良い。
 交差の回数はBITを使えば求めることができる。

2026年10月9日金曜日

Codeforces Round 1125 (Div. 3)

 Gまで。

コンテスト後のツイート

H. A Problem to Warm Up the Eyebrows

 解説AC。
 解説も自力では解読できず、ChatGPTに説明してもらってACした。

 解説は式変形で解こうとしているが、式変形から導出するのは難しい。
 主客転倒で解けないか? と疑わなくてはダメ。

 A[i][j]*A[x][y]が何個寄与するか? と考えると、そのbounding boxの上下左右に何個行や列があるか? を見れば答えが求まることが見えてくる。
 そう思えば、具体例を考えるとどれくらい寄与するかが見える。

 難しいが、主客転倒というアイディアさえ思え付けば無理な問題ではなかった。



2026年10月6日火曜日

AtCoder Regular Contest 231

 Bのみ一完。それも遅い。

コンテスト後のツイート

A - Two Dimensional Invader

 解説放送を見てAC。

 言われてみればなるほど。x座標とy座標を分けて考えるという発想はあったが、思いつけなかった。
 BITは「更新O(logN)区間取得O(logN)」ですが、これは普通にやった場合「更新O(1)取得O(N)」、累積和を使った場合「更新O(N)取得O(1)」の中間あたりを取っていると考えられる……みたいなのと似ている。

 O(N^2)をO(N)とO(N)に分解することもそこそこありそうなので典型的とは思うけど、一問目でパッと見て思いつけるものでもないねぇ。Bがスムーズに解けて、落ち着いて臨めたら違った可能性はあるかなぁ。