脳log[2020-11-21～]

最終更新: 2020-11-22T08:26+0900

♪ [AtCoder] AtCoder Regular Contest 108／C 問題 Keep Graph Connected

コンテスト中に問題文は理解していたと思う。文は。問題まで理解していたかは知らない。

1. 頂点対抗で辺の奪い合いをする。
2. 各頂点は自身に繋がる辺からこれはと思うグループをひとつ選び、それら辺に共通する番号を名乗る。
3. このときその頂点に直接繋がる他の頂点は同じ番号を名乗ることができなくなる。
4. そうして全頂点がちょうどひとつの番号と辺(のグループ)を選び取ったとき、選ばれた辺で全体がひとつに繋がっていればそれが答え。

これを DFS で探索しようとした。だめな選択に早々に見切りをつけて手戻りを減らすために、選択肢の少ない頂点に優先して選ばせようとした。

あとで提出して確かめる。TLE になるならさらに考えないといけない。WA になるなら問題文を読み直さないといけない。

あ、選ばなくていい頂点もあるのか。木の根に相当する頂点。選ばれる辺の数は N-1 以上になるから必ずなにがしかの木＋余分な辺になるわけだけど、それがどういう意味を持つのか。最後の頂点だけ選べなくてもいいってだけ？ わからなくなってきた。

最終更新: 2021-02-20T23:02+0900

♪ [AtCoder] 第四回 アルゴリズム実技検定

自分の提出。第一回、第二回、第三回。

今回は K 問題までたどり着けなくて、J 問題で詰まった。まだ解けていない。特定のカテゴリの入力が全滅しているから、見落としているパターンがあるし、それを除いてもまだ AC は遠そう。だけど ABC184の E 問題 Third Avenue は解けてるんですよ>20201122p01.03。不思議だなあ。

その後 K 問題は解けたし、なんなら L 問題も解けたけど、時間はかけた。そして M 問題。

 M 問題 筆塗り

まだ３つの TLE に阻まれている。

何について繰り返すか、その通りがかりに素早く答えを出すためにどんな最適化されたデータが準備できるか、というのが考えどころ。

実行時間の制限が長めの４秒ではあるけど、制約上の上限がどれもこれも 10^5 だから、何かについて繰り返しているあいだに探索やら配列埋めやら時間がかかる処理をするわけにはいかない。

たとえばクエリごとに色記録配列を埋めるとか、辺(=頂点集合を左右に分ける)ごとに関与するクエリを逆順に検索するとかは間に合わない。Ruby では間違いなく。

 提出 #18035280 (TLE×18 / AC×16 / 4419 ms / 234280 KB)

Array にはない ^ メソッドが使いたくて require 'set'; した。「対称差」を求めるメソッドらしい。しかし遅い。

 提出 #18036165 (TLE×9 / AC×25 / 4445 ms / 1224160 KB)

３つの演算子(+, -, &)を使って自分で Array#^ メソッドを実装した。+ の代わりに | メソッドを使うこともできるが速くなる気がしない。まだ遅い。

 提出 #18053537 (TLE×3 / AC×31 / 4416 ms / 210696 KB)

bsearch_index と concat で Array#^ メソッドを実装した。演算子を使ったシンプル実装より必ずしも速くなるわけではないが、遅くなるのは TLE になるほどではない小さいケースだし、直線に近い(色リストが長くなりやすい)木では有利になるためか TLE が減った。しかし残った３つの TLE (random_17.txt, random_19.txt, random_28.txt) はどの提出に対しても実行時間が上限に張り付いたままで、打開するヒントが見えない。どういう形の木なのか。

 方針

1. 根を１つ決めて、木全体を葉から根へ遡るように処理する(なぜか根が上)。
2. ノードは色リストを持っている。色は z-order で識別する。z-order は 1 から Q の範囲の値をとる。
3. 子が持つ色リストを親のものにマージしていく。マージする過程でペアができればリストから取り除く。
4. ノードが持つ色リストのうちもっとも手前にある(z-order が大きい)色が、そのノードと親を結ぶ辺の色となる。

N 個のノードについて繰り返しながらソート列(色リスト)のマージを繰り返すのが、時間的にもメモリ的にも厳しい。だけどこれが嘘のように時間制限をクリアできる魔法があるとも思えない。十分にストレートで迷いのないコードだと思う。この方針のままなんとか滑り込みたい。

「打開するヒントが見えない。どういう形の木なのか」と書いたけど、直線の反対ということで子供が 100, 1000 あるような木を用意したらてきめんに遅くなった。どうしようかな。

 提出 #18059514 (TLE×2 / AC×32 / 4418 ms / 201508 KB)

変更点はソート済み配列から最大値を取り出すのに max メソッドを使っていたうっかりの訂正と、子の色リストを得るのにランダムアクセスをやめてスタックから連続する領域を取り出すようにしたこと。これで１減って残る TLE は２個。

4400 ms が 4200 ms になったりするとあとちょっとだとわかるんだけど……。

あるノードに合流してきた色リストは LCA と z-order がともに昇順になるように並べ替えることができて、そこから外れる色は色塗りの出番がなくて無視できるんだけど(※)、それで良くなるものか……。

※ z-order が大きければ他の色より前に出られる。LCA が小さければ前にある色が LCA に到達して退場するのを待てる。どちらでもなければ前に出る前に退場させられる。

 提出 #18069462 (AC / 1394 ms / 106192 KB)

やった！！！

LCA が正解だったみたい。木を遡りながら色リストをマージするのは同じだけど、LCA を利用してリストを短くしたら TLE が解消した。

うれしい。とってもうれしい。ここ２、３日トイレでもお風呂でもふとんの中でも考えていた。あっさり AC されているとやる気が萎えるので見ないようにしていたが、Ruby で AC 一番乗り。

ところで PyPy3 のこのシンプルかつ Python 系で一番速い提出 #18047488 (819 ms) はなんの魔法だろう。半分以上が入力の処理で、残りでヒープの出し入れをしているだけ。

JIT で速いから余計な手をかけないで済むということなら Ruby には関係のないことだけど、考察が足りていなくて自分のアルゴリズムがヘボだというなら、学ばなければいけない。

それはそれとして、LCAの確定を待つ色のリストはソート済み配列をやめてプライオリティキューにすべきだし、lambda M の中の Array#slice! と Array#insert は配列に相応しいメソッドではない。配列を酷使しすぎている２点に改善の余地がある。

 提出 #18102965 (Crystal / 559 ms / 56432 KB)

初めて Crystal を書いた。色々言いたい。

• Web で見られるランゲージリファレンスがない。ドキュメントがあることとアクセスしやすいことは必須。リファレンスだけあればいい。getting started はいらない。
• Ruby を知っているからこそ罠が多い。

  • delete_if と inject メソッドがない。reject! と delete_if は完全に同じではないし、reduce と inject がただのエイリアスなら用意しないのは罠でしかない。

    inject は配列の各要素のあいだに演算子を挿入するイメージのメソッドらしい。それを読んでから inject の仕様に悩んだことはない。

  • lambda メソッドがない。テキトーに Proc.new と書いてみたけどダメだったので -> () {} と書いた。アロー記法は好きではない。

    パラメータには型注釈が必須だったけどコロンの前か後ろか両方にスペースが必要だったらしい。詰めて書いたら「ダメだ。我は ) を所望する」と怒られ、素直に ) を書いたら型注釈を付けろと怒られる無限ループ。

    後付けするなら記号は選ばなければいけない。Ruby の仕様(メソッド名と文字リテラル)なら条件演算子はむしろないほうがいいし、だけど条件演算子とシンボルリテラルは現実に存在しているし、記号は選ばなければいけない。

  • each メソッドが self を返さない。なぜ？
  • ブロック変数名に _ が使えない。なぜ？
  • 定数に多重代入ができない。なぜ？

  • 定数と変数が同じスコープ、見た目通りの実行軸にないように思う。

    n,q = gets.split.map(&.to_i)
    N = n; Q = q

    これは変数 n が定義されていないというエラーになった。

    (追記：下の方で答えを書いてたかも。「map が遅延評価？ .to_a を付けないと期待したタイミングで副作用が起こらない。」 map が遅延評価であることと代入が行われないことは別だと思うのだが違うのか。違う(別ではない)なら大変に興味深い Crystal の特徴だと思う)

  • &:to_i と書いていたものを &.to_i と書かせる。

    .to_i が Crystal という言語を構成する部分として定義されており、プログラマが操作可能な対象であるなら評価は変わるけど、単に & という目印のバリエーションとして &. を追加したなら、ただの好き嫌いでただの罠。

  • ブロックパラメータは必ず１つ？ {|i,|} とか {|i,j|} とかできない雰囲気。それとも StaticArray だったから？
  • map が遅延評価？ .to_a を付けないと期待したタイミングで副作用が起こらない。
  • Enumerator のチェインができない。具体的には map.with_index と書くと map にブロックパラメータが必須だというエラーになった。スペックを読んだら map_with_index というメソッドがあったので使ったが、map だけ？

  • nil が非常に煩わしい。Ruby はすべての変数が Nullable だし、偽と評価される値が nil と false だけなのもあってあらゆる部分に nil が現れる。そのすべての nil に対応を迫られる。一例が gets.to_i とは書けなくて gets.to_s.to_i と書かされるところ。たぶん (gets||"").to_i でもいいとは思う。

    実行時エラーをコンパイルエラーにしたいのだとしよう。だけど視野が狭い。こちらは gets が nil を返すかどうか、そのような入力が与えられるかどうかに関する知識を持っており、nil が返るような入力が仕様違反であることを知っている。バグがあったときに修正すべき対象は Crystal のソースコードではなく、そのような入力を与えた外部にある。事の決定権はコンパイラにはない。

    &. によるメソッド呼び出しに対応していれば話は違った。

  • 空の配列から pop できない。空の配列を reduce できない。これらも nil がらみであろう。
  • 空の配列、空の Hash の作成がめんどくさい。[] とか {} とか書けない。とりあえず領域を確保するために [nil]*N と書くのもタイプミスマッチで都合が悪い。
  • "1(スペース)2".to_i がエラーになった。1 を期待していた。0 をデフォルトとして解釈できるところまで解釈することを .to_i には期待している。

すべてドキュメントの不足が悪い。スペックしか頼れるものがなかった。

俺は人類の手には多少余るとしても、プログラマを信頼し、力を与えてくれる言語が好きだ。安全のためと称して枷をはめようとする言語は選ばない。安全な鈍(なまくら)は退屈だ。

では Ruby の切れ味は？ Ruby はプログラマがやりたいことの邪魔をしないのがいい。Ruby がコードゴルフに向いているということとも関連する。キーワードやら形式やら、本筋の処理と無関係でありながら書かなければいけないお約束が少ないということ。

Crystal の型はどうか。プログラマに力を与えるためではなく、処理系が力を得るためにプログラマが受け入れる枷だというのが、少し触っての印象。枷を受け入れるなら C++ が選択肢に入る。

const 教の信者というのは最も“const と書きたくない”人種のことだと自認している。const という当たり前のことを、どうしてあちこちそちこちに書いて回らなければいけないのか。所有権も魅力的だけど、const と書かなくてもいいという１点でまず、Rust の評価が高い。

C++ も Ruby も好きだけど弱点がある。Rust には期待ができる。でもコンパイラが起動できないんだよなあ。「rustc.exe - エントリ ポイントが見つかりません。プロシージャ エントリ ポイント K32EnumProcessModules がダイナミック リンク ライブラリ KERNEL32.dll から見つかりませんでした。」 本でも読むか。

 別解@2021-02-20 提出 #20275440 (AC / 1168 Byte / 1081 ms / 73084 KB)

#18069462 と比べて、-1016 Byte / -313 ms / -33108 KB。短くて速くて省メモリ。

先に書いたように、「クエリごとに色記録配列を埋めるとか、辺(=頂点集合を左右に分ける)ごとに関与するクエリを逆順に検索するとかは間に合わない」のはたぶん間違いないけども、２つを混ぜてクエリの逆順に効率良く色記録配列を埋めるところまでは考えが及んでいなかった。

時間軸を反転することで、一度塗ったところを再度塗らないでスキップしたい

その方針でやってみれば、前半はほとんど同じことをやってるんだけど、下準備を終えたあとのメインループでは、ソート済み配列をマージする代わりにスキップしながら親をたどっていた。親をたどる方が短く書けて簡単！

最終更新: 2021-05-07T15:06+0900

♪ [AtCoder] AtCoder Beginner Contest 015／D 問題 高橋くんの苦悩

DP の基本形といっていいほど典型的な DP。見え見えの誘いに乗りたくなくて他の解法を考えてみたけど思い付かなかった。それに心配しなくても Ruby ならではのお楽しみポイントがちゃんとあった。

実行時間の変遷が見どころ。

 提出 #17933561 (TLE×7 / AC×40)

N×K×W のループは上限が2500万回であり、Ruby で TLE を避けようと思ったら桁を１つ減らさないといけない。予想された結果。

 提出 #17934141 (AC / 1033 ms)

N のループが K 回に達するまでは K のループを K 回まわす必要がないよねっていう節約作戦で AC になった。制約は K <= N <= 50。

 提出 #17934762 (AC / 554 ms)

提出一覧が 1000 ms を超えるグループと超えないグループに分かれていたので中を見たら、添字と値が入れ違っていた。

• 遅い方 - Array[K][W] = sum of B (K<=50, W<=10000)
• 速い方 - Array[K][sum of B] = W (N<=50, B<=100, sum of B<=5000)

B の値域が(W にくらべて)かなり狭い範囲に限定されているのがポイントで、速い方はループで走査する DP 配列のサイズがおよそ半分で済む。

 提出 #17935118 (AC / 111 ms)

２番手以降の集団をダブルスコアで突き放す zazaboon さんの提出 #11417636 (150 ms) を調べた結果。

• DP 配列のサイズを制約上の上限ではなく、テストケースに応じた必要最小限のサイズにする。
• B を小さい順に処理することにより、ループの初期に更新する DP 配列の範囲を限定する。
• 答えを見つけたら即終了する。

以上の点を真似したのに加えて、考えられるこちらのアドバンテージが

• Ruby のバージョンが上がっている。(2.3 → 2.7)
• 最初に簡単なチェックで N を減らした。
• 初期値を整数にした。(「とりあえず大きな数としての初期値に Float::INFINITY を使うと、10**9 のような整数型を使うより比較にコストがかかる」)
• 演算子を極力書かないようにした。(vsum+1 は美意識とボキャブラリに起因する例外)
• 配列参照を極力書かないようにした。特に二重のものはひとつも書かなかった。
• 見た目がださくても a = [a,b].min と書くより a = b if b < a と書いて代入を省略できる方が速い。(だけど本当は宣言的な変数定義がしたい。操作ではなく結果について書きたい)
• よくわからない処理を真似しなかった。41 行目の if と 44 行目。

前後のリストを比べると後ろは問題と関係のない比較的どうでもいい内容が並んでいるね。

 Python のこの提出 #287540 (AC / 66 ms)

いまのところの Python 最速。AB 配列を幅対重要度比でソートしてからの DFS なんだけど、すごいのが _greedy_by_width と _greedy_by_num という先読み関数で探索の打ち切りを判断しているところ。それでペイするんだってところと、１枚のスクリーンショットを刻む発想が(だって刻んだ画像の価値はゼロですよ。常考)。

使う使わないの二択だと比率がちょっと悪くても残った隙間にぴったり収まる方が重要度を高められることがある。先読みでその可能性を取りこぼしては答えを誤る。だからあくまでも比率のいいスクリーンショットから使う。ぴったり収まらないなら切り取って収まる分だけ使う。そういう考え。

最近別の問題を自分が DFS で解いたときのことだけど、「さっきの TLE 提出を微修正したら AC になった。事前に XY 配列をソートするだけ。二択による手戻りを最小限にするために、選択肢の優劣が明らかで覆りにくいものを最初に選ぶようにした」なんてぬるいやり方よりずっと突き詰めている。すごいなあ。

最終更新: 2020-11-06T01:42+0900

♪ [AtCoder] AtCoder Beginner Contest 181／D,E,A

 D 問題 Hachi

ほんの一瞬、1,10,100,1000,10000,... を８で割った余りに与えられた数字を掛け合わせて８の倍数を作るゲームかと思ったけど、組み合わせが膨大で無理そうだった。

こういうのって８の倍数が千とか万とかキリのいい数字になったらそれより上の桁の数字が何であっても千とか万の倍数であり８の倍数だから無視していいんだよねってことで irb で実験したら、４桁目から上はもう無視していいみたいだった。1000 = 8×125。３桁で８の倍数が作れれば良し。

 提出 #17805410 (TLE)

物量に頼った雑なやり方で TLE を食らった。

 提出 #17808009 (AC)

お留守だった脳みそをなんとか働かせて tally メソッドで集計をすることにした。

 E 問題 Transformable Teacher

とくに悩むところはなかった。全体にペアの差を最小にしたいならソートして隣同士で組み合わせるしかないと思った。あとは妖怪先生(え？わたし？)をどこに潜り込ませるかだけ。

データ構造も悩まなかった。右の人と組む場合と左の人と組む場合の２種類の階差数列が必要だな、定数時間である範囲の数列の和を求めるには累積和だな、と。

 提出 #17820870 (AC)

惜しむらくは提出時刻がコンテスト終了の６分後だということ。

こうなってみると B 問題 Trapezoid Sum で等差数列の和の式を悠長に組み立てていたのが悔やまれる。何回やっても全然答えが合わねーの！ いま検索したら Wikipedia に n(a1+an)/2 みたいな、自分が考えてたのよりずっと簡単な式が書いてあったりして、あほくさくなってくる。ちがう、お前があほなんだ。この式に16分かけた>#17793713。展開して整理する時間も惜しかった。最後なんて式はもう合ってるのにサンプル入力のコピペに失敗して答えが合わないせいで式の検討をやり直したからね。

次の C 問題 Collinearity ではさっさと２点を通る直線の式(軸に平行な直線にも対応したもの)を検索している>#17796631。７分かかってるのはタイピングとサンプルを使ったテストの時間。

 A 問題 Heavy Rotation

こういうコードをゴルフ的だと考えるとしたら、それは考え違いだと言いたい(誰に向かって言っているのか謎だが)。

puts %w(White Black)[gets.to_i&1]

比較対象は例えばこんな感じ。

if gets.to_i.even?
	puts 'White' 
else
	puts 'Black'
end

２番目のようなスクリプトを書く前に自分が考えること……

• 出力は１回１行だけしか行われないのに puts が２つ見えるのは読み手にやさしくない。

• もし～ならこうする、さもなければこうする、という構成はあまりに手続き的。もうすこし進んだパラダイムを学んでも良い頃合いでは？

  そうする理由はかっこいいからとか新しいからとかではなく、変更に強くなるのとコードの複雑化を抑えることができるから。

  何度かこの日記に書いてるけど、バリエーションを表現するのにコードではなくデータを使うということ>20150514、20181029。

• データ(Black と White の文字列配列)が用意できたらあとは入力(gets.to_i)と出力を最短で結ぶシンプルで無駄のないコードを書くだけ。２の剰余を添字にすればよい。あえて迂遠な書き方をする普遍的な理由なんてない(バカと可読性は個人の属性)。これまで if (a == b) return true; else return false; などと書いてきたなら今すぐ悔い改めよ。

  ま、それは極端だとしても、コアとなるコードは「何かを出力する」となるべきであり、その何かを作るのに if 文を書いたり、if 文を含んだ関数を一度だけ呼び出したり、事前に用意しておいたデータファイルを読み込んだりするのが良い。

• 「もし～ならこうする、さもなければこうする」という型のコードは２つの「こうする」に無制限に無関係な処理が書けるし、何もしないこともできるし、目的に対して自由度が高すぎる。もっと制限の強い型にはめれば読み手にいらぬ想定を強いることがない。

  だけどアクセス制限にしろ型にしろ、制限を強める方向で書くには頭を使うのだな。おつむが弱いとカオスをばらまくことが避けられないのだな。

最終更新: 2020-11-05T19:41+0900

♪ [AtCoder] AtCoder Beginner Contest 181／F 問題 Silver Woods

コンテストは終了しているので落ち着いて考えた。

1. それぞれの点について、取り得る選択肢は上を通るか下を通るかの二択。
2. 上を通ることを選択した点と下を通ることを選択した点のペアについて考えれば、必ずその２点の間を通過している。
3. 総当たりだと最悪の場合に 2^{100}(=約126穣)通りになって大変。
4. 見込みのある選択肢を優先すればなんとかならんか？

 提出 #17835277 (TLE×11 / AC×49)

ダメでした。まあね、優先度を付けても裏をかくような難しいケースが良くなるわけじゃないからね。

Python の提出一覧を見たら２桁 ms の AC 提出がいっぱいあった。これはコードを書く前にもうちょっと考えなければいけないな。

F問題は、直感的に「釘と直線をグラフの頂点として、ユークリッド距離をコストにして辺を貼り、パスのコストを「通る辺のコストの最大値」としたときに直線から直線への最短距離÷2」が答えだと感じたので、それをダイクストラで実装したら通った。

ええっとですね、まずそれが直感的にわからないし、そのわかったことを読ませてもらってもそれがどういうことなのかわからないのですね。(そもそもユークリッド距離の概念が曖昧。名前だけ知ってる編集距離なんかと比べて一番普通の距離だと思うけど、そう思うだけ)。

前半はまあまあ想像できる。全頂点を一筆書きして通路を左右に分ける線を引いたとき、最も広い点と点のあいだに円を通すということだろう。だけど第３の点が邪魔をして最も広い点間を通れないことがあると思う。そこから後半の「最短距離÷2が答え」につなげられない。

 @2020-11-04

邪魔をしている第３の点が最も広い点間を挟むどちらかの点と直接繋がる経路というのが、より小さいコストを持つ経路なのであり、(でないと邪魔できない)、最短経路というのはそういう邪魔が入らない経路のことなのだろう。たぶんね。

答えが示されているからこそ、こうしてこじつけ気味にでも納得のいく解釈がひねり出せたけど、これが「直感的に」ねえ……(遠い目)。

@kyopro_friends「アライグマ「F問題は……「半径rの円が通れる」っていうのは、「円の中心が障害物からr以内にならない」ってことだから、逆に障害物の方を半径rの円にしちゃえばいいのだ！」

@kyopro_friends「アライグマ「道がふさがったらダメだから、障害物同士の距離を全部計算しておいて、距離が短いところから順にくっつけていって、上の壁と下の壁がくっつくときが答えなのだ！」

これはわかる気がする(図もあるし)。でも逆にこのツイートを読んでもダイクストラ法で実装することがわからないね。

 提出 #17842898 (AC / 819 ms)

上のツイートとは関係なくさっきの TLE 提出を微修正したら AC になった。事前に XY 配列をソートするだけ。二択による手戻りを最小限にするために、選択肢の優劣が明らかで覆りにくいものを最初に選ぶようにした。

いつの間にか Ruby でも AC をとっている人がいて、しかも実行時間が２桁 ms なんだけど、UnionFind を使っているみたいだった。どういうこと？

あ、連結成分の管理か。コストの低い辺からつないで最小全域木ができあがったときに最後につないだ辺のコストがそのまま答えになる。へー、クラスカル法と UnionFind が今初めてつながった。UnionFind とグラフに関連があるらしいのを今まで見て見ぬふりをして考えてこなかったツケであるな。こういう問題(「Reachable Towns」「Line++」)が全然グラフの問題に見えないんだよなあ。

そうしてみると問題文中で(N 本の)釘とされているものを Silver Woods と表現した問題名は、「木だよ、森だよ、グラフだよ」というヒントだったのだな。おしゃれ。

ところで、自分の提出も２つのケースが 819 ms と 170 ms なのを除けば２桁 ms で済んでいる。オーダーが劣ってもだいたい良好ってことでどうですか？

 提出 #17848105 (AC / 93 ms)

ソート方法でガチャを引いたら２桁 ms になった。オーダーは変わっていないので入力の引きとソート方法の組み合わせが悪いとやっぱり遅くなるはず。ランダム入力を使って実行時間を体感でテストしてるんだけど、逆順にするだけで十数秒が一瞬になったりする。

メインの処理で if-else-end を省いて２＋２行だったものを３行にまとめたけど、実は再帰呼び出しの回数が多少増える無駄がある。だけど事前のソートで無駄が生じにくいお膳立てはしてあるつもりだし、ストレートで整然とした文字の並びが他には代え難い。

メインの処理２行目の d2 変数への代入だって変数の使い回しで省略できるし*、３行目で再代入している d1 変数はそれから使っていない。しかしストレートで整然とした文字の並びが……。

たぶん通ると思う。265 バイト。$$ が 200 以上だったらいいなという運任せ(※多少小さくても入力次第で問題なし)。単に minify しただけで見るべきところがない。リテラルとか長いメソッド名とか多くの変数とか似たような型の処理とか、１個あればたくさんなものが多すぎるよね。

_,*z=$<.map{_1.split.map &:to_f}
Y=z.sort!.map{|x,y|[y+100,*z.map{Math.hypot x-_1,y-_2},100-y]}
F=->i,d,a,b{
z=(t=Y[i])?(*c=i+=1
e=F[i,e,a+c,b]if z<e=[*t.values_at(*b),d].min
F[i,d,a,b+c]if z<d=[*t.values_at(*a),d].min
z<e&&F[i,e,a+c,b]
z):d}
p F[z=0,$$,[0],[-1]]/2

うーん、どうだろう。219 バイト。答えの確かなテストケースがないと自信ない。

e,*z=$<.map{_1.split.map &:to_f}
Y=z.sort!.map{|x,y|[*z.map{Math.hypot x-_1,y-_2},100-y,y+100]}
A=[-1],[-2]
F=->i,d{(t=Y[i])?[A,A.rotate].map{(_1<<i;F[i+1,e];_1.pop)if z<e=[*t.values_at(*_2),d].min}:z=d}
F[z=0,$$]
p z/2

 提出 #17867027 (AC / 220 Byte)

よく考えたら AC 提出とランダム入力で答え合わせができるのだった。

$$ はダメだったので(#17866997)、１バイト増えて 220 バイト。Windows ではプロセス ID は４桁だったんだけど。

まあしかし、これだけ長いとこのスクリプトひとつとっても、いくらでも縮めどころが見つかりそうではある。

 提出 #17868705 (AC / 217 Byte)

３文字減。ちなみに、変更に伴って入れ替わった２数を、どっちでもいいだろうとそのままにした結果は TLE だった>#17868682。「実は再帰呼び出しの回数が多少増える無駄がある。だけど事前のソートで無駄が生じにくいお膳立てはしてあるつもり」が裏目に出た当然の結果なんだけど、わからんもんかなあ。

３文字減った理由がなかなか味わい深い(と思う)。Ruby って C++ などと違ってあらかじめ配列のサイズを決めておいたり、あらかじめ読み込む行数を想定しておいたりせずに、いきなり入力を配列に読み込んで行数は配列のサイズで後から知ったりする。だから後続の行数を知らせる一行目は読み捨てても困らない。

この問題もそうだったんだけど一行目だけ列数が異なっていることも多くて、そうすると共通のルーチンで読み込めないせいで取り扱いに手がかかる(文字数を費やす)から、やっぱり読み捨てたくなったりする。

今回も一行目は読み捨てていて、ただそれにも gets やらプレースホルダとしての変数名が場所を取るわけなので、脚注に書いた不都合を回避するための変数の先行定義を兼ねさせていた。

そのプレースホルダであり先行定義である変数の、本来用のない中身(定数 N を唯一の要素とする配列)が役に立ったよ、という話。

ゴルフせずに普通に書くとこうなる(普通の定義が狂い気味)。

_,*XY = $<.map{|ln| ln.split.map(&:to_i) }
D = XY.sort!.map.with_index{|(x,y),i|
	[*XY[0,i].map{|x1,y1| Math.hypot(x-x1,y-y1) },1e2+y,1e2-y]
}
F = lambda{|x,d,i,up,dn|
	next d unless di = D[i]
	d1,a1 = [*di.values_at(*dn),d].min,up
	d2,a2 = [*di.values_at(*up),d].min,dn
	d1,a1,d2,a2 = d2,a2,d1,a1 if d1 < d2
	_,x, = a1<<i,F[x,d1,i+1,up,dn],a1.pop if x < d1
	_,x, = a2<<i,F[x,d2,i+1,up,dn],a2.pop if x < d2
	next x
}
p F[0,200,0,[-2],[-1]]*0.5

メインの処理が３行から２行へと、ゴルフをする過程で気がついた無駄が省いてあるのと、ゴルフをしていると省略せざるを得ない d1,a1 と d2,a2 のスワップが再帰呼び出しを多少減らす見込み。ゴルフをしているとまとめざるを得ない２つの似た処理は、並べた方が速い。しかし誤差程度にしか違わない。むしろ入力次第でひどく悪くなるのがクラスカル法とは違うところであり、覆せないオーダーの差。

深さ優先探索はひとつの経路に縛られるし、幅優先探索はひとつの深さに縛られる。辺に優劣がないならそういうひとつの決まりに従って網羅的に探索して咎められないとしても、そうでない場合は、もっと一般的なグラフアルゴリズムを使うのが効果的だということなんでしょう。さっきは UnionFind についてだけ触れたけど(「UnionFind とグラフに関連があるらしいのを今まで見て見ぬふりをして考えてこなかったツケであるな」)、DFS と BFS がグラフアルゴリズムだっていう認識も実は全然持っていない。見えないんだよなあ。

最終更新: 2020-10-31T00:45+0900

♪ [AtCoder] AtCoder Beginner Contest 180／D,E

 D 問題 Takahashi Unevolved

数弱さんには頭が痛い問題だった。

 提出 #17475334 (WA)

 提出 #17517315 (AC)

経験値１を加算して増える強さを A と B で比較する。

強さが増加するに従って必ず A を掛けた方が B を足すよりも強さの増加量が増える。(A が１より大きい整数だから)

対数を使って強さの増加量が逆転する境目を求めたのだけど、それは A,B,X の関数であって、Y による制限が考慮されない。

WA だった提出では Y を考慮して上限を定めていたのだけど、境目が負になる場合を考慮して下限を 0 に規正することができていなかった。

コンテストが終わってから問題を明らかにするテストケースが見つかってデバッグができたが、遅すぎた。

10^{18} という制約の大きさにびびって対数を持ち出したけど、A が最小の 2 であっても 10^{18} <= 2^{60} だから、A を使用した方が得する境目は高々 60 なのだった。頭痛の種を自分で作り出していた。

いや違う。比較対象は上限が 10^9 の B だから、境目の上限は高々 30 か 29 だ。

どちらにしろ簡単なループで求められたのだな。同じ手は食わない>#17612685 (翌週の ARC にて)

 E 問題 Traveling Salesman among Aerial Cities

コンテストが終わってから問題文を読んだ。イメージが湧きやすくていい問題名だと思う>Aerial。

 提出 #17485932 (TLE×13 / AC×13)

2**17*17*17(=約3800万)回のループであり、サンプルですら TLE になるのがわかっていたが、ビギナーはワーシャルフロイド法が書けただけで満足なのです。これ以上は解らないのです。

以前解けなかった問題で参考にした提出。「後半はワーシャル-フロイド法に見える３重ループ。ただし街と街を結ぶ中継地点(一番外側のループ)は街ではなく経由地のリスト」。これをチラ見しながら書いた。

 提出 #17516238 (AC / 1933 ms)

ダイクストラ法でコスト順に点を繋いでも時間がかかりすぎるのは確かめていた。問題に合わせたチューニングが何かできないか、そもそも総当たりのワーシャルフロイド法で可能なチューニングがあるのだろうか、と考えていたが思い付かない。コードを眺めてみよう。

1. 一番内側のループで変化しない配列参照をループの外に出せばちょっとは良くなるかも。
2. 一番内側のループで処理をスキップするための判断を加えるのは無駄。
3. 一番内側のループから真ん中のループに外出ししてきた変数を使って処理をスキップすれば最内ループが丸々スキップできておいしい。

という感じの苦肉の策で AC をもらった。E 問題だからこんなものかも(というのはコンテスト中に解いてから言おうね)。

集合 S をビット表記により 0,1,…,2N−1 までの自然数にエンコードしてしまうと、S=0,1,2,… 順にループするだけでトポロジカル順序が守られることなどから、実装が簡潔になります。

自分はこの条件を知らないままなんとなくでうまくいく方法を真似しているだけだなあ。

頂点0からスタートするが、訪問済み頂点集合を考える上で頂点0は最初は含めない

こうすることで「訪問済み頂点集合が全集合になった」時「頂点0に戻ってきた」ことを意味するので、戻り道も含めた問題条件に適用できる

これを考慮するなら自分の AC 提出の 10 行目を NP[0][0] = 0 としなければいけないが、実際にそうしなければいけないだろうか。

NP = Array.new(N){ [Float::INFINITY]*2**N }
NP[0][1] = 0

NP[現在地][経由地] = 移動コスト であり、ゴールは NP[都市１][全都市網羅]。ゴールに初期値以外のコストが設定されているとき、それは全都市を経由してから現在は都市１にいる(またそれにかかるコストがいくらか)ということなので、スタートが NP[都市１][都市１] でも NP[都市１][無] でも関係はないかな。

 提出 #17524559 (AC / 1283 ms)

「スタートが NP[都市１][都市１] でも NP[都市１][無] でも関係はない」ということと関係するのだけど、konayuki さんの提出 #17520925 のこの行……

dp[0][1] = 0
for i in 0..goal
  next if i&1 == 0

17 行目は、自分も全く同じように書いたが、スタート地点の初期化。だけど 19 行目のスキップが目新しい。これは経由地点にスタート地点を含まない場合を除外している。当然これに関わるコストを記録した配列の中身は初期値の Infinity で間違いない。

2^N が 2^{N-1} になるだけでループの回数が半分になるのだからこれはとてもうまい。これもひとつのケチビットだな、ということで、メモ配列からもループの繰り返しからも最初から除外しておけば条件分岐すら不要。

ところで、コストを記録するメモは Array[N][1<<N(-1)] よりも Array[1<<N(-1)][N] としている提出がほとんどだった(例外が自分と konayuki さん)。これは「一番内側のループで変化しない配列参照をループの外に出せばちょっとは良くなるかも」の発展として理解できる。行列計算ともたぶん関係する。多重ループの最内ループが多次元配列の何次元目をイテレートするかは性能と無関係ではない。スクリプトにおいても、途中までの配列参照をローカル変数にメモすることでコスト削減が期待できる。

この２点で 1933 ms が 1283 ms になった。

 左にマイナス１ビットシフトは右に１ビットシフト

負数を習う中学１年生らしい言い換え。

さっきの提出で意図せず -1 ビットシフトしている部分があったが、エラーにもならず正しい答えが出ていた。Ruby に助けられた怪我の功名。この仕様は特に明記されていないし知らなかった。

これまでは 1<<N が取り得る値の最小が１だとばかり思っていたから、０にしたい場合を例外扱いしていた。活用したい仕様。

 提出 #17557645 (AC / 852 ms)

「同じ都市を２度以上訪れて得することはない」、という考察を何か所かで読んだので、next if 0 < v[f-1] という条件を真ん中のループに足してみたら、1283 ms が 852 ms になった。わーお。

ちなみに Integer#[] である桁のビット(0,1)が得られるのだけど、最下位(右端)のビットが０番目になっている。負の添字は必ず０が返るっぽいので、今度は意図してこの仕様を利用した。

 提出 #17558093 (AC / 769 ms)

「負の添字は必ず０が返るっぽいので、今度は意図してこの仕様を利用した」とか書いたけど、０は望ましい結果ではなく、結果的にスタート地点である都市１だけは何度も発着を繰り返していた。

真ん中のループの繰り返しから都市１の分を引いて N 回を N-1 回にしたら、852 ms が 769 ms になった。もうこれ以上は無理でしょ。

Integer#times の方が Range#each より速いようだったので Integer#times を使っている。そのせいで f(rom) と t(o) で都市番号への対応付けがずれているのが罠。

 提出 #17563476 (AC / 627 ms)

経由地を記録したビットフラグ(v)から０のビットを抽出して真ん中のループと一番内側のループに利用したら、769 ms が 627 ms になった。さすがにもうこれ以上はないでしょ。

 提出 #17563659 (AC / 583 ms)

TLE を初めての AC に変えた立役者である next if NP[0][-1] <= c0 が、変形を受けながらずっと残っていたのだけど、いつの間にか用無しになっていたことがわかったので消したら、627 ms が 583 ms になった。沼っぽくなってきたぞ。

メモ配列を見たら 0 番目の要素が 0 と Infinity に決まっていて無駄なので、長さ N の配列が N-1 にできるけど、ちょっとした省メモリにはなっても速くはならない感じ。

 提出 #17575125 (AC / 217 Byte / 1731 ms)

沼といえばゴルフ。217 バイト。

(N,),*Z=$<.map{_1.split.map &:to_i}
V,=C=Z.map{|a,b,c|Z.map{(_1-a).abs+(_2-b).abs+[0,_3-c].max}}
V+=[9e9]*N*M=1<<N-1
M.times{|v|N.times{|f|g=N.*v|1<<f-1;w=V[v*N+f];N.times{|t|V[g+t]=[V[g+t],w+C[f][t]].min}}}
p V[-N-N]

TLE になったら元も子もないので削れない一時変数と -1 がある。そういうのは Crystal (Ruby に似たコンパイル型言語)で投稿するという手があるらしいが知らないので。

 提出 #17667397 (AC / 207 Byte / 1963 ms)

うん、沼だ。207 バイト。

配列の初期化を省いて || で初期値を補うようにしたら 10 文字短くなって 200 ms ほど遅くなった。

(N,),*Z=$<.map{_1.split.map &:to_i}
V,=C=Z.map{|a,b,c|Z.map{(_1-a).abs+(_2-b).abs+[0,_3-c].max}}
(1<<N-1).times{|v|N.times{|f|g=N.*v|1<<f-1;w=V[v*N+f];N.times{|t|V[g+t]=[V[g+t]||9e9,w+C[f][t]].min}}}
p V[-N]

整形すれば普通に読めるあたり変態度が足りないと思うんだよなあ。発想に飛躍がない。

 研究>提出 #17680607 (yamagiri さん / 556 ms)

• ループの回数が何パーセントか少ない。内側のループが 0(potentially 1) to 0 でなく 0 to 1 だから。そうしようとすると初期化にフラグが絡んできて手間がかかると思ったけど、実はそうでもなかった>提出 #17685423。手間を省いた代償として数万回のループの初回にしか関係しない || が二重ループの内にあるけど、大差ないみたい。

• とりあえず大きな数としての初期値に Float::INFINITY を使うと、10**9 のような整数型を使うより比較にコストがかかる。

  余計なコストがかかるはかかるんだけど、今の段階に至っては初期値は nil で構わないのだった。比較されない。

• こんな感じの配列を事前定義すると手元ではちょっと速いようだけど、スマートじゃないので却下。

  ０１ = [[[0],[]],[[],[0]]]
  (1...N1).each{|n|
  	０１.concat ０１.map{ next (_1<<n)[0,_1.size-1],_2+[n] }
  }

  (1<<N1).times{|v|
  	c = CV[v]
  	０,１ = ０１[v]
  	０.each{|f|
  		f2 = C[f]
  		CV[v|1<<f][f] = １.map{|t| f2[t]+c[t] }.min||s2[f]
  	}
  }

最終更新: 2020-10-16T23:56+0900

♪ [WR250R] バイク走行動画 (合計 6 分)

１号線を走るくらいならこういう道を選ぶよね。このルートに仮免許練習中の教習車を送り込むコースが存在している模様(よく見かける)。そんな教習うらやましいにも程がある。

音・サイズ(100 MiB 超)注意。