/ 最近 .rdf 追記設定本棚

脳log[2021-11-30～]

最近ひとつ現在へひとつ過去へ

2021年11月30日 (火) [AtCoder] 昨日あった ARC130。C 問題「Digit Sum Minimization」。制約が貪欲しか許さないと告げている。繰り上がりが起こった場合にしか和が減らないのはわかった。繰り上がりがある前提で繰り上がりを連鎖させるために桁の和が 9 から 18 になる組み合わせをこの優先順位で作っていくのが良さそう。ただし最初に繰り上がりを起こす和(10 から 18)の作り方がまずいとサンプルの２が合わない。敗因は、単独で繰り上がりを起こす１桁目を全探索しても許されると解らなかったこと。今日の提出 #27603786 (AC / 782 Byte / 712 ms)。数字の操作ではなく配列の操作を繰り返していて間に合ってるんだもんなあ。■あ、昨日じゃねーや。消えた月曜日。

ツッコミを入れる

2021年11月26日 (金) [AtCoder] 精進。JOI 2020/2021 本選過去問 C「集合写真 (Group Photo)」。少し考えると、許される並びは一直線に右下がりの並びを基本として、何か所かでちょん切った右下がりを逆順に配置したギザギザ右下がりしか許されないとわかる。それを制約上限 5000 を４秒以内で求める手順とは。DP ですね。１以下の H をいい感じに並べる手数から始めて２以下、３以下……をいい感じに並べていくと最後に答えが出る。■提出 #27502421 (64/100 点 / TLE×15)。制約が異なる小課題のうち最後の小課題５がすべて TLE だった。アルゴリズムのオーダーが間違っている。N の二乗に BIT 由来の log をくっつけたのが良くなかった。■提出 #27509632 (TLE×15)。同じ TLE とはいえ実行時間は 44xx ms から 40xx ms に改善している。ここからは定数倍の改善で 100 ms を稼げばなんとかなる。この提出では二重ループの内側で BIT を利用するのをやめて N^2 のループで前処理をした。処理を１か所にまとめようとしてループを重ねて計算量のオーダーを悪化させるより、同じオーダーのループを２つ並べる方が速いということが盲点になっている。Maximize GCD のときも気がつけなかった>20210919p01.03。今回のメインループは N^2 なのだから、大概のことが前処理でできる。BIT の代わりになる N 個の累積和(配列)を用意しても許される。■提出 #27510644 (AC / 3120 ms)。前処理で扱う配列の長さを必要な分だけに切り詰めた。要素数の合計が NN から N(N+1)/2 に減ったと思う。あとは配列参照を減らしたり数字の微調整をなくしたり reverse_each をなくすために最初から逆向きの配列を用意したりという爪に火をともす努力。そういうの好き。結果として AC 提出が一番短くなって 277 Byte。

ツッコミを入れる

2021年11月25日 (木) [AtCoder] 精進。ARC124-D「Yet Another Sorting Problem」(ギリギリ黄 diff。そんなアホな)。これは Swaps の仲間なのかな>20200826p01、20211022p01。３つの中でこれが一番頭が爆発した問題だった。実際にソートして数を数えても許されるあたりは厳しくはないんだけど、添字と値が入れ替わって入り交じるスワップ操作で頭がこんがらかる。そして最後の最後にも罠があった>`(gn-gm).abs`。提出 #27485094 (AC / 515 Byte / 188 ms)。ほぼ一日かかった。■考え方はいろいろあるのかな。自分はまず反対側の領域にもぐりこんでいる要素を探した。そしてそこに本来収まるべき要素を探し、探した要素があった場所に本来収まるべき要素……を芋づる式に探してグループとした。ただしグループは前半領域、後半領域のどちらかの中にだけ作って、領域をまたぐグループは考えなかった。こうやって１つずつ反対側に移動している要素の位置を移動しながらついでにソートもしていくと、最終的に反対側に移動している要素はなくなり、前半後半のどちらかに閉じて位置を交換していてソートされなかったグループが残る。反対側の未ソートグループが利用できる場合は利用して互いに交換回数を節約しながら全グループをソートする。この、手続きに基づいた解法がどのような考えからひねり出されてきたかというと、必ず行わなければいけない操作を無駄なく行う、というところから。貪欲法？

ツッコミを入れる

2021年11月22日 (月) [AtCoder] 精進。ARC112-D「Skate」(ギリギリ黄 diff)。初見ではない。グリッドだけど行列に見える。行と列を並べ替えて寄せていってもいいのかなと。島(#)がない行か列に足場(#)を作って連結していくことを考える。だけど足場が行と列の両方で孤立している場合には連結にならない。そこから連結しているもの同士が複数のグループに分かれて孤立している場合に想像が及ぶ。行で連結するのがいいか列で連結するのがいいか、両方のベストミックスを考える必要があるのか。いろいろ考えてしまって答えが出なかったのが初見のとき。今回は UnionFind でなんとかなりそうだと見当がついた。提出 #27452260 (AC / 471 Byte / 830 ms)。■青 diff の後ろの４問目でなければ水 diff だった可能性もあるのでは？こんなアンケートがあったよ。「ARC112 C(DFS Game)とD(Skate) どっちの方が難しいと感じましたか」結果は７対３で C。印象通りだけど C 問題の方は時をおかずに解けているのも事実>20210216p01。■「Ruby によるすべての提出」を見ると他の AC (３つ)はほぼ半分の 400 ms 前後で処理を終えている。どうやら行と列に分けて２回の UnionFind を行う必要はなかった。行と列の組み合わせを一意に識別する (縦×横) 通りの通し番号を使うことは考えていたのだけど、そもそも # がある場所について、ある行に対する列、ある列に対する行を識別する必要がなく、(縦+横) 通りを考えるだけで良かった。提出 #27452260 (AC / 467 Byte / 445 ms)。

ツッコミを入れる

2021年11月21日 (日) [AtCoder] コンテストの時に限って頭ヨワヨワの神経衰弱になること、あると思います。実は試される機会がないから気がつかないだけで、いつでも頭ヨワヨワで生きていること、あると思います。

ツッコミを入れる

2021年11月20日 (土) Excel すごいなあ。TSV/CSV ファイルをインポートしたら自動でコネクションが維持されて自動更新ができる。TSV/CSV ファイルのありかは http で始まる URL でもいい。なんでもできるね。それが罠なんだけどね。テーブル設計とか整然データとか学ばずに使えてしまうのが良くない。なんでもできる(その代わり無限の手間がかかる)せいでユーザーを教育する機会を逃している。

ツッコミを入れる

2021年11月19日 (金) [AtCoder] 精進。PAST202004-N「ビルの建設」。昔は TLE だった>提出 #14165065。まだ BIT を知らなかったのだ。とはいえ当時の日記(20200610p01)を読むと、L 問題を解くために BIT の上位互換であるセグメント木を初めて実装しているのだから、純粋に知らなかったとは言えない。ともあれ今日はささいな記述ミスをいくつか修正しただけで素直に実装完了。座標をゼロ以上にずらしたり圧縮したり、丁寧にやるだけ。提出 #27334595 (AC / 872 Byte / 1105 ms)。■ハッシュ表を使った疎で座圧不要の BIT のアイデアはこたつさんのツイートを通して知りましたよ。だから Y 座標は圧縮したけど X 座標はずらしただけ。元はこれかな>「ふつうの BIT / 要るところだけつくる BIT https://t.co/qcPsZFhhbq」

ツッコミを入れる

2021年11月18日 (木) [AtCoder] 精進。ARC107-C「Shuffle Permutation」(水 diff)。７か月前に「緑がほぼ埋まってきて残っているのは解けなかった問題ばかり。そこで水色下位に手を出すも下位とはいえ水色はぱっぱっと解ける雰囲気ではない。あれもこれも行列の問題で、問題のその操作で何ができるのかさっぱりわからない」と書いたとき念頭にあった問題の１つだけど、今日は特に詰まるところなく解けた。操作の前後が可換であること、行の操作と列の操作が独立していることを読み取ってから UnionFind を道具として選んで順列を計算するところまで。むしろ無効な交換を考えなくてもいい問題設定の優しさが目についたくらい(行や列のアイデンティティをどう定義すると効率がいいのか考えるのに一番時間を使っていたのだけど、不要だった)。成長しているのだなあ。提出 #27321607 (AC / 513 Byte / 66 ms)。■直近の ARC128 が茶 diff も緑 diff も解けないゼロ完だったとしても(成長しているのかなあ)。

ツッコミを入れる

2021年11月15日 (月) [AtCoder] 精進。PAST202107-H「折れ線グラフ」。配置的に茶～緑 diff だと思うんだけど初見では解けていなかった>20210721p01.08。特徴的な制約を見れば３乗の DP の臭いがプンプンするが、当時はそれも見えなかった。「Ruby によるすべての提出」。AC は２つ。工夫なしの４重ループ(N 個の点、残りの Y 座標、直前の Y 座標、今回の Y 座標)は通らないはず。目指すグラフの形はゆっくり平均値(のちょっと上？)まで上昇してゆっくりゼロまで下降する折れ線なので、そのあたりを織り込んで端折れる遷移がある。……というか、自然な延長として DP の必要すらないと思うんだけど、どうなんでしょうね。Math.sqrt(aa+1)+Math.sqrt(bb+1) と 1+Math.sqrt((a+b)*(a+b)+1) の大小関係は。何をどういう a と b に分割するのが最適かはやっぱり DP をせんとわからんのかな。■いろいろと半分にして答えが出るかと思ったけどなかなかうまくいかない。

ツッコミを入れる

2021年11月14日 (日) [AtCoder] 精進。ARC068-E「Snuke Line」(黄 diff)。たぶん調和級数がどうの計算量の見積もりがどうのという問題なのかな。調和級数が何か知りませんけども。とりあえず実装して実行してみる派ですけども。あるいはきっちり考察が詰められれば最終的な計算量は高がしれているのかな。■提出 #27263215 (AC / 1998 ms)。考察がへぼでも BIT で殴ると制限時間ギリギリセーフだった。Ruby で最初の AC であった>Ruby によるすべての提出。2.7 より古いバージョンでは不可能だったのかもしれないね。■ブログを読むとわりとみなさんと同じことを考えていたことがわかる。区間の幅を見たり、重複して数えてしまったり、BIT を使ったりというのが共通してる。案外あれは脳筋解答ではなかったのか。■昨日の ABC？ D 問題ダメでした。結果は見ていない。緑落ちあるで。□Twitter でちらっと二分探索のワードが見えた。１部署に人数が固まりすぎてると無駄、少なすぎると統合して人数をかさ増ししなければいけないなど、K 個のプロジェクトに平均的に分散させる必要があって、余ってる足りないの基準となるボーダーを二分探索する考えは頭の隅にあった。でも結局解法によらずどうやって均すのかがわからんかった。

ツッコミを入れる

2021年11月12日 (金) [AtCoder] 精進。ARC076-E「Connected?」(黄 diff)。こういう(特定のアルゴリズム、データ構造を知っていますかという知識問題ではなくて、ゼロからむにゃむにゃ考える)問題好き。もちろん解けたから言えることだけど。もちろん(LIS と UnionFind がそうだったように)アルゴリズムを再発明するのでもいいんだけど。解説を読んじゃうと台無しになる類の問題なので、ネタバレには注意。■提出 #27191350 (AC / 390 Byte)。制約が線形時間もしくは入力された個々の点に対して対数時間の処理しか許していないので、試行錯誤はできない。最初は、N 個の点を並べることを考えた。たとえば並び順はなんでもいいけど 1→2→……→N という交差のないひと筆書きが同じ向きで２つ平行に書けたなら、答えは YES。だけど N の順列も交差判定も処理が重い。結局のところ、ひと筆書きを制約するものは壁に張り付いた点なのだということに気がついたら、あとはなんとかなる。

ツッコミを入れる

2021年11月10日 (水) [AtCoder] 精進。ARC067-E「Grouping」(黄 diff)。初見では手が出なかったが２度目の今日はわかった。残り人数をキーにして場合の数を記録する DP で、グループの人数を変えて遷移した。提出 #27170288 (AC / 914 ms)。■あほな人間は根を詰めて考え続けても答えは出ないんだ。一旦離れて忘れるのが肝心。それだけで労なく考え続けているのと同じ効果が上がるのが、「下手」の取り柄なのだ。(もしかして：効果ゼロ)

ツッコミを入れる

2021年11月09日 (火) [AtCoder] 精進。ARC077-E「guruguru」(黄 diff)。それほど難しくはないかな。ABC-D＋α という感じ。プラスアルファで悉くつまずいて AC に辿り着けないのが自分ではあるが。ともあれ道具立てはコンテスト後にいつもいもす法だイベントソートだと話題になるあれ(よく知らないので自分では固有の名称に言及しないけど)。時間軸に沿って加速度と加速度の累積としての速度と速度の累積としての移動距離を記録して答えにする。■提出 #27154438。まずは入力された A 数列の隣接２要素(a,b)から情報を抽出する。a から b へ b-a 回のインクリメントを繰り返して移動するわけだけど、その途中にお気に入りがあると回数を節約できる。区間は [a+1,b] で節約幅は [0,b-a-1]。a+2 時点から節約効果が現れて、b がお気に入りのときに最高の b-a-1 回の節約になる。区間の左右端と節約回数の上下端が off-by-one エラーを誘発しやすい感じ(ドツボにはまった経験から書いています)。あとは区間を外れた b+1 の時点で節約効果をリセットするなど。時間軸は 1 から 2×M の２倍幅を扱うとループの境界を気にしなくて済む。■精進２。ARC035-C「アットコーダー王国の交通事情」(青 diff)。現在 Ruby での AC はなし>Ruby によるすべての提出。N^3 が想定解になる問題は定数倍のハンデも３乗で Ruby にはつらすぎる。提出 #27155496 (C++ / 88 ms)。C++ では一番速いぜ。■昨日の精進。ARC083-D「Restoring Road Network」(水 diff)。これも３乗だけど上限が 400 でなく 300 で、ループ内の処理もごく軽量なので、Ruby でも通る>Ruby によるすべての提出。

ツッコミを入れる

最近ひとつ現在へひとつ過去へ

ここをクリックしてカテゴリ一覧を表示