脳log[20220722]

2022年07月22日 (金) [AtCoder] 精進１。ABC260-F「Find 4-cycle」(青 diff)。２か所で「鳩の巣原理」のヒントを見てすぐに目を逸らすということをしていた。それが２、３日前。ヒントがあっても今日までかかった。■提出 #33392687 (AC / 335 Byte / 1597 ms)。一方の独立集合(V2)のサイズが意図的に小さく制限されているのはすぐに気がつく。これは要素でペアを作って１つ１つ調べても間に合うサイズ。つまり鳩の巣というのは V2 の要素のペアであり、ここに何かを詰め込んでいってあふれるのを待つ。それが何か。V1 の要素しかないんだけど、V1 の要素と V2 のペアを結びつけるものがしばらくわからなかった。目の前にきちんとお膳立てされていないとわからないんですね。辺をグループ化してグループ内で組み合わせる。■■■精進２。ABC132-E「Hopscotch Addict」(ギリギリ青 diff)。気がつけばなんてことのない問題。BFS をケン、ケン、パで３倍頑張るだけ。提出 #33383061 (AC) ■■■精進３。精進１の関連ツイート「アライグマ「F問題は鳩の巣原理なのだ！　類題は第一回最強コン決勝A問題『Equal Weight』なのだ！ https://t.co/3KBTMkCrt1」から第一回日本最強プログラマー学生選手権決勝-A「Equal Weight」。制約を見てびびる。ネタもシャリも最大 20 万種類あるから、ネタとシャリの組み合わせも、ネタとネタ、シャリとシャリの組み合わせも１つ１つ取り上げるわけにはいかない。これが 300 点問題？■提出 #33398275 (AC / 238 Byte / 498 ms)。がんばって鳩の巣を探しました。重さの散らばりが 1 から 100 万のあいだだから、組み合わせた結果(ふたつの和)は 2 から 200 万のあいだに収まる。ネタとシャリを組み合わせて重さをキーにして記録していくと、最大で 200 万回書き込むまでには重複が見つかる。■掛け算の組み合わせだと 20 万は大きすぎる上限だけど、足し算だと 100 万でも現実的な数字だというのが、見た目通りではなくて意外性があった。ヒント無しでは解けなかっただろうね。■■■精進４。ABC254-D「Together Square」(緑 diff)。自分の頭からは TLE 解しか出てこないので見ました。「AtCoder Beginner Contest 254 D - inamori’s diary」 わっかりやっすーい。■提出 #33413694 (AC / 1545 ms)。prime_division を使った愚直解。遅いけど制限時間内ではある。■提出 #33414040 (AC / 190 ms)。さっきの提出は 1 から N の数について独立した処理をしていた。処理の連続性をいかして、配列をメモに使って、時間コストをケチると 8 倍速くなった。■Ruby によるすべての提出を見ると最速は 62 ms だから、まだ削れるはずなんだよね。わからんけど。しかも 62 ms のうちほとんどがインタープリタ起動にかかるオーバーヘッドだから、見かけ上の３倍差よりずっと効率が違う。