/ 最近 .rdf 追記 編集 設定 本棚

脳log[20240511]



2024年05月11日 (土) [AtCoder] 今日は AtCoder Beginner Contest 353 があった。コンテスト成績証自分のすべての提出。E までの問題を読んでから A から順番に書き始めた。A 問題の AC が9分30秒時点だから、だいたい9分くらい問題を読んでいた。それぞれの問題の実装時間が、A=30秒、B=4分、C=11分、D=5分、E=11分、F=36分(読解含む)。C 問題が難しかったよね。ではふりかえり。■A 問題「Buildings」。ループを回せますかという問題。Ruby を使っているなら、ループという汎用的で原始的な道具ではなく、ループを使って何がしたいかという目的別に特化したメソッドを選んで使う。意図が明らかなコードを書く。C++ でも <algorithm> の中に何があるかひと通り調べておいて、使う機会を常に窺っておくのがいい。■B 問題「AtCoder Amusement Park」。前から順番に K 人を超えない範囲でグループを作っていくといくつになりますかという問題。やるだけではあるんだけど、テストがないと不安がぬぐえない。祈って提出しました。K を超えた数を数えていた場合、最後のグループを数え忘れるというのが、考えられる罠かな。■C 問題「Sigma Problem」。CDE と続く Sigma Problem の第一弾。二重のシグマは見慣れていないとびっくりするけど、シグマのそれぞれの範囲を見れば、考えられるすべての組み合わせについて足し合わせるという意味だと読める。基本的には answer += a*A.size+A.sum while a = A.shift なんだけど、2要素の和が 10^8 を超えるときは 10^8 を引かなければいけない。A 数列の順番には意味がないので、予め A 数列をソートしておいて、何個の要素が 10^8 を超えるかを効率良く数えられるようにする。二分探索なら log が付くけど間に合うし、尺取りっぽい操作をするなら log は付かない。あっ。自分の提出 #53343786 で 10**8 に付けた名前が P(rime number) というのは嘘だ。■D 問題「Another Sigma Problem」。今度は2要素を文字列として連結してから数値として評価をする。順番に意味があるので並べ替えてはいけない。右側にある要素について、数の和と、下駄の和がわかればいい。下駄というのは、3桁の数字であれば 1000、4桁の数字であれば 10000 を計上する。これを全要素について数え上げておいて、更新しながら答えの計算に利用する。■E 問題「Yet Another Sigma Problem」。かかった時間だけ見れば C 問題と同じなんだけど、配点通り CD より難しかったと思う。自分は Ruby の記述力におんぶにだっこで効率の悪い解答を書いた。まず、N 個の要素について、先頭の文字を見ます。同じ文字だったもの同士をグループにして再帰的に次の文字を見ます。その過程で、グループの大きさを見ます。大きさが Z なら、作れるペアの数(Z*(Z-1)/2)がそのまま答えに寄与します。■F 問題「Tile Distance」。わかりやすい図が付いていてたいへん助かります。K=1 は簡単。マンハッタン距離が答え。それ以外はどうしましょう。最初はフラクタル的に考えてみようとした。スタート地点とゴール地点が隣接していると見なせるまで K を定数倍してみる。で、視点をズームインしながら移動コストを足していけないかと。できなかった。次は大きいタイルと大きいタイルのあいだの移動コストを数えようとした。横方向の移動コストだけを考えてみる。K が大きいなら、上下にあって頂点で接している大きいタイルを経由することで、必ずコスト4で真右にある大きいタイルへ移動できる。K=1 のケースはさっき除外した。K=2 の場合は小さいタイルをそのまま突っ切って移動する方がコスト3なので安い。そういう計算をしているうちに、斜めの移動コストが特に安いと気がついた。K マスを1と数える大きいタイルの座標系で考えてるよ。例えば右に2、下に2の位置にある大きいタイルに移動したいとする。右に移動してから下に移動するなら、さっき計算したコストを使って 3+3 (K=2 のとき) か 4+4 (K>2 のとき) になるけど、ありがたい図を使って数えてみると、たったの4で右下の右下にある大きいタイルに移動できることがわかる。というわけで、まずは斜めに移動して、それから縦もしくは横に移動すると考えると、最適な大きいタイル間の移動コストが求められる。あとは1または4通りと、1または4通りの総当たり(1x1 または 1x4 または 4x1 または 4x4 通り)でほぼ答えが出る。1と4が何かというと、スタート地点ゴール地点から最寄りの大きいタイルの数。「ほぼ」が何かっていうと、スタートとゴールが小さいマスにあってすぐ近くにある場合。これは K=1 の場合のマンハッタン距離と同じだから、提出 #53370051 では K=1 の場合を分けるのをやめて雑に一体化した。全部混ぜ混ぜして最小値を取れば自ずと答えが出てくる。■G 問題「Merchant Takahashi」。今日の G 問題は F 問題と配点が同じ。F 問題を通してから G 問題を読んで、することがなくなったので順位表を見たら F より G の方が通されていたね。自分は G 問題がさっぱりだったけど、データ構造で一発なぐるだけの典型だと仮定して眺めてみれば、移動コストによる報酬の減殺が組み込めるなら、セグメント木が使いたい形だと思った。もちろん組み込めないのだけど。■Highest を更新したけど、明日の ARC の参加費は何レートかな。何レート吸われるんだろう。3-4-5-(略) という配点は水色の自分向けド真ん中なので出ないわけにはいかないんだよな。■■■精進。G 問題。セグメント木を2つ持つんだと2か所で読んだ。それでどうやって距離による減殺を組み込めるかを考えた。左右の端、頂点1と頂点 N にいると仮定したときの所持金のポテンシャルをセグメント木の各要素の値とすると、イーブンな条件で大小比較ができて最大値が取り出せる。提出 #53408933 (AC / 849 Byte / 1999 ms)。2秒制限で 1999 ms は神がかっている。だめだったらセグメント木にブロックを渡す代わりに max メソッドの呼び出しを直に埋め込むだけ(手動インライン展開)。■実際の値の代わりにイコール条件のポテンシャルを扱うのは ARC120-C Swaps 2 でやったことがある。20211022p01。なんでそんな名前で呼んでるのかは自分でもわからない。なんとなくふさわしいような気がしただけ。