脳log[20240317]

2024年03月17日 (日) [AtCoder] 昨日はモノグサプログラミングコンテスト2024（AtCoder Beginner Contest 345）があった。22:40 になったら結果も他の人の提出も見ないですぐに離れてしまったんだけど(面白くないことがあったのです)、なんだかすごいことになっていたみたい。EF がどちらも黄 diff だったんだって。恐ろしい大虐殺があったということだ。コンテスト成績証。「早解き大成功で棚ぼた青パフォの回だった」と書いた前回より解いた問題が１問少なくて、順位とパフォーマンスは逆に少し上なのだから、ぼた餅のありがたみが増量している。まあ、お前はいつまで崖を見上げる立場でいるんだって話ではある。あんまりふりかえって書くことはないかな。D 問題みたいなのは箱入り娘ソルバーとかカレンダーパズルに似ている(20210121、20210527)。テキトーに計算量を見積もって最大限に手抜き実装をしたら 25 ms だけオーバーしてペナルティを食らってやんの(#51311820)。条件式をループの外に出して AC (#51314164)。■@2024-03-21 E 問題「Colorful Subsequence」。Ruby でがんばったけどこれが限界。提出 #51483115 (TLE×20 / AC×18)。今のところ TLE しかないよ>Ruby によるすべての提出。制約による暴力はやめてください。■■■[AtCoder] 今日は AtCoder Regular Contest 174 があった。自分のすべての提出。結果はまだ。AB は早かったけど C がさっぱりで、早々に見切りをつけて D に集中するも１時間以上かかった。■A 問題「A Multiply」。累積和の問題。ABC338-G「evall」の部分問題みたいなもので、「範囲の両端が + の内側にある場合の寄与は、これは累積和の問題として単独で D 問題あたりにでもなりそうな難易度の問題」と書いていた部分。ABC-D ではなく ARC-A として出てきた。他所でいろいろ読んで場合分けをしているケースがほとんどみたいだったので、自分のやり方を書く。ある要素 A[i] が範囲に含まれるとき、全体の和をどれだけ増減させるかは C*A[i]-A[i] で計算される。これの部分累積和が最大になる範囲を求める。場合分けはしない。判断をすれば判断ミスをするし、分岐すれば分岐した先それぞれでミスをするので。部分累積和の最大を求める方法だけど、名前が付いているらしかった。「Kadane's Algorithm | 最大部分配列 問題 - Ark's Blog」。名前で特定するより自分でひねりだすほうが簡単では？ ダイクストラ法もね、優先順位付き(重み付き) BFS という、実態に即した命名の方が理解を促す面があると思うんだよね、固有名詞で特定するよりもね。■B 問題「Bought Review」。星は増やすことしかできない。星を水増しして総数を増やすことに意味はない。それを確認すると無駄な情報が見えてくる。星３の数はいらない。星１２３を増やす選択肢もいらない。星１と星２を星４と星５で打ち消すための配分を考える問題。二分探索が頭をよぎって線形性を探したけど、実は星４を２つ増やすコストと星５を１つ増やすコストの大小で即座に優先すべき選択が決定する。ぴったり打ち消すのがいいか、１つ星を余らせた方が効率的にも絶対的にも得かは、条件次第で判断が分かれるところ。最適な式を探るより候補を３つ並べる方が簡単。■D 問題「Digit vs Square Root」。小さい N に対して答えを列挙してみると、答えが見つかる範囲が 10 の冪乗とそこからいくつか下った狭い範囲に偏っていることがわかる。1、10、9、8、100、99、98、1000、999、……といった具合。あとはがんばる。ランダム入力に対して愚直解法と答えを突き合わせて１時間20分かかった。つらい。実装しながら Project Euler の Problem 63 Powerful Digit Counts に似ているなと思っていた(20110308p01.02)。■日記を書いているあいだに結果が出た。コンテスト成績証。ARC にはレートを吸われるばかりなので、微増は勝ち。