A.all?(A[0]) でも A.uniq.size==1 でもお好きな方で。■B 問題「3-smooth Numbers」。素因数が２と３だけかどうか確かめる。２と３で割れるだけ割って１になるかどうかでわかる。■C 問題「Error Correction」。これ３つの問題がひとつになってるよね。強いて言えば２つは対称な問題だったので、２種３通りの解答を書くのがとても面倒でした。文字数が１つ多いときは、１度だけ比較をスキップできるということ。それで他の全ての文字が一致するなら可能性がある。文字数が１つ少ないときは、文字数が１つ多いということです。■D 問題「Square Permutation」。意外に Ruby での AC が少なかった問題。13 の階乗は数が多すぎるので、平方数の方から攻める。２乗して 13 桁を超えるのは数百万くらいの数からだったので列挙できる。ところでね、サンプルの２に「異なる並べ替え方でも、並べ替えた結果の数が同じなら 1 つと数えることに注意してください」と書いてある。そんな大事なことは本文に書いておけよと思って今読み返してみたら。本文には「
(1,…,N) の順列 P=(p1,p2,…,pN) によって i=1∑Nspi10N−i と書ける整数のうち、平方数であるようなものがいくつあるか求めてください」と書いてあった。うーん？ 順列ではなく順列によって表される整数を数えろって書いてあるのかな？ まあいいや。自分のこの提出(#46569450)には順列を数えた部分がコメントとして残っている。無駄な時間を使ったぜ。しかも最初の提出は WA×1 だった。ゼロは平方数に入りますか？ 入るみたい。式をよく見ると順列を数える場合でも答えに足すのは固定値なんだな。単に大きな固定値を足すか１を足すかの違いでしかなかったのに、つどつど無駄に数を数えていたのは自分が足りないせいだったな。■E 問題「Joint Two Strings」。これも最初は違う問題を解こうとしていた。この問題の部分文字列とは連続とは限らない部分文字列のことでした。問題文にちゃんと書いてあるんだから、読むだけでなく頭に入れてくださいね。制約が大事。「
S1,S2,…,SN の長さの総和は 5×10^5 以下」と書いてあるのだから、S をなめるような処理を書いてその中で T をスキャンしたりしなければ間に合う。S ごとに T を前から何文字カバーできるかを数え、同じように T を後ろから何文字カバーできるかを数え、足して T の長さより短くない組み合わせを数える。これは罠なんだけど、入力の N は T の長さではありません。今日の入力は、C 問題 と E 問題が共通して変則的だった。なぜ関連するわけでも同種でもない入力を１行にまとめるのか。(たとえ使わないにしても)今回に限って文字列長を先行して与えないのはなぜなのか。入力の処理が面倒だった。■F 問題「Beautiful Path」。比率は扱いが難しい。最終的に分子を最大化して分母を最小化したいんだけど、中間値についてたとえば比率が同じでも (美しさ)/(コスト) = 100/100 と 10/10 を同列に扱ってはいけない。100/100 を 10 % 改善するには美しさを 10 足す必要があるけど、10/10 を 10 % 改善するのには美しさを 1 足すだけでいい。以前に濃度の問題を２問解いている。「Sugar Water 2」(20230319) と「食塩水」(20220714)、それともうひとつ「おまかせ」。それでもやっぱり解法に悩むし 30 分はかかるんだね。途中で G 問題を読んだりなんかもして、でも F 問題の制約が「１アイデアで解けるよ」と訴えていたので F 問題に注力することにした。解法は以前の日記に書いたように、濃度を決め打てば溶質の過不足が具体的な値として求まるので、これを最大化するようにして最終的にゼロを上回ればいい。二分探索で。■コンテスト成績表。遅い６完だったけど青パフォでした。明日の ARC にはいくつのレートを捧げることになるのかな。■D 問題。提出 #46587508 (gmmtea さん / 971 ms)。他の Ruby の提出にほぼダブルスコアの差をつけて１番早い。列挙に工夫があるのかなと思うけど、よくわかんないことをしてる。すごい。■ちょっとお風呂で考えて Send More Money (20210412p01) と共通点があるかと思った。あれは DFS で無駄なく列挙することで４桁 ms が２桁 ms まで劇的に縮んだ問題だった。この問題も２乗する数を１桁ずつ確定できないかなと思った。確定済みの値が cba で次の桁が d のとき加算する値は d000 であり、２乗した数は (d000+cba)^2 = d000*d000+2*d000*cba+cba*cba になる。増分は d000*d000+2*d000*cba の部分。増分の末尾ゼロ３つが確定しているので平方数の下３桁には影響を与えられない。そんな感じで平方数の確定した桁と使える数字とを見比べて違反があれば即座に以降の列挙を打ち切れるのではないかなと。実際にやったけど答えが合わないしサンプルの３が却って遅くなったのでやめにした。