/ 最近 .rdf 追記 設定 本棚

脳log[2020-12-06~]



2020年12月06日 (日)

最終更新: 2020-12-08T16:28+0900

[AtCoder] 鹿島建設プログラミングコンテスト2020(AtCoder Regular Contest 110)/A,B,C

ARC 級の企業コンであることがわかりやすい表記になった。企業コンだけどいつもの ARC と同じ気構えで挑戦してもいいことがわかりやすい表記になった。

鹿島の名前はブルーバックスの『図解 超高層ビルのしくみ 建設から解体までの全技術』の編者としてと2冊の SD 選書『近代建築の失敗(著:ピーター ブレイク)』『建物のあいだのアクティビティ(著:ヤン ゲール)』の出版社(鹿島出版会)としてだけ目にしたことがある。ジャンルが同じだから関連があるのでは?

 A 問題 Redundant Redundancy

題意を満たすような数のうち脳死で求められるものはすべての数の積+1なんだけど、答えに制約があって N 以上 10^{13} 以下のものを出力しなさいと。

2 から N の数を素因数分解してマージする。素因数がそれぞれいくつあれば 2 から N の数を表現するのに足りるのか。16 なら 2 が 4 つ必要だし、27 なら 3 が 3 つ必要。6 や 18 など複数の素因数を持つ数はとくに考えなくていいかな。

 提出 #18579266 (AC)

ひょっとして求めたものを最小公倍数と呼ぶのだろうか。Integer#prime? なんて便利メソッドを使ってごにょごにょするくらいなら Integer#lcm を使うのが直接的だったんだろうか。

 B 問題 Many 110

入力例1の解説を注意深く読めばわかるはずですが、注意すべき点があります。110 を 100 個連結した文字列の中に、110110 という部分文字列は 99 個見つけることができます。決して 50 個ではありません。

この勘違いを正すのに多大な時間を要した。難しい問題ではないとわかるのに答えが全然合わなくて、神経衰弱になりそうだった。

 提出 #18593923 (AC)

とりあえず答えは出た。

 C 問題 Exoswap

前回より悪くて(20201202p01.04)、3問目にして 20 分しか時間が残っていなかったけど、考えるだけ考えた。

  1. 同じ操作が高々1度しか許されていないので、ある数を適正な位置に移動するのに冗長な操作は許されない。
  2. まずは数ごとに必要な操作の列を作った。
  3. すべての数を満足させるよう操作の順番がひっくり返らないようにしながら、すべての操作列を一列にマージすれば良さそう。
  4. 行きすぎて戻るということはできないから、操作が少なくて済む場合は即座に NG。
  5. 同じ操作を要求する3つ目の数があれば、それも即 NG。
 提出 #18611107 (TLE×6 / AC×56)

TLE です。メモリの使用量に比例した時間がかかっているような雰囲気。testcase_10.txt は提出によっては TLE にならないことがあり、TLE といえども 22xx ms ではなく 20xx ms であるあたりちょうどボーダーライン上のケースだといえる。そのメモリ使用量が 560 MB。その他の TLE は 570 MB から 632 MB のメモリを使用している。全然ダメって感じではなくて何割か改善したら AC になりそうな期待が、ないかなあ。

特に頭の悪いことをしている部分があるとは思わないんだけど、だからこそ、根本から発想の転換が必要だと言われたら困るなあ。

大量のメモリって、前半の操作列の列挙部分で使ってるのかなあ。見え見えのダメケースを前半部分で拒絶するべきなのかなあ。さっき書いた「同じ操作を要求する3つ目の数があれば、それも即 NG。」とか、今考えたけど「i,i+1 という操作と i+1,i という操作を要求する2数があれば、操作列のマージが不可能なので NG。」とか。

前半部分の列挙について考えていると、後半部分のキューが不要にできそうな気がしてくるなあ。問題の制約って想像よりかなり厳しくて、可能なケースが限られるし、可能な操作列もいくつか考えられる中から一番簡単なものを出力するのに手間はかからなそう。

つまり、数列に対応した(※)配列に右向き左向きをメモして、山と谷があって、高いところ(流れの発するところ)から低いところ(流れの集まるところ)へ向かってテキトーな順番で列挙するだけなのではないかという……。

※数に対応させるのか数と数の間に対応させるのかで迷ってコードにならない。今は「間」かなという気がしている。

 提出 #18639675 (AC / 424 ms)

とりとめなくいろいろ書いたけど、結局、前半部で見え見えのダメケースを拒絶して AC になった。

もっと鮮やかに解けるはずなんだけど、当面のモチベーションは消えてしまった。


2020年12月02日 (水)

最終更新: 2020-12-03T19:37+0900

[AtCoder] AtCoder Regular Contest 109/A,B,C,D

先月28日土曜日の振り返り。ARC なので A 問題が 300 点からスタートする。2問解けたらまあまあという感じ。配点が同じ 300 点、400 点でも、ABC のと比べるとちょっと手強い印象を持っている。

時間は長めの2時間。ABC と違って C、D、E、F 問題にはだいたい取り付く島さえないので、時間が足りなくなるということはまずない。簡単すぎるテストと難しすぎるテストは時間が余るという点で共通する。

 A 問題 Hands

上の階に上がるのに階段と廊下の2種類の手段があるというのが不思議な設定だが、床の高さが半階分ずれた2棟が上りと下りのスロープで結ばれていると解釈するツイートを読んだ。なるほど。ところですべてのフロアが渡り廊下で連結されているなら、それも水平1本ではなく三角形で繋がっているなら、2棟は一体の構造物として設計されているのでは? そのとき「廊下」はどのような形態になりますか?

 提出 #18452990 (AC)

11分ちょっとで提出している。こうだったらこうだな、こうだったらああだなと考えながらとりあえず書き出してみてそれをそのまま提出した。

 B 問題 log

考えたこと。

  • 長さによらずコストが同じであるし、切れ端を捨ててもいいのだから、とりあえず長い方から買えば良い。
  • そしてもちろん、長い丸太から切り出して買うのを節約する丸太は、短い方から順に揃える。
  • n がいくつのとき、何本分の節約ができるかが問題。
    • 順番に書き出してみれば、長さ1を1本分節約するのに1本の購入が必要。(n=2)
    • そこからもう1本節約するには長さ2を1本用意しなければいけないので、追加で2本の購入が必要。(n=2+3=5)

節約する本数 k から n (の下限)を求める式が n ≧ Σ(k+1) = k+k*(k+1)/2 だということはすぐにわかったけど、n が与えられたときに k の最大がいくつになるのかを求めるのに、sqrt を使ってずっと考えていた。B 問題に取りかかってから最初の提出まで 46 分。

 提出 #18463725 (AC)

n の制約上限は 10^{18} であり、(10**18).bit_length は 60。なんだ探索すればいいじゃないと気がついたらもう問題は残っていなかった。

 C 問題 Large RPS Tournament

RPS って Rock, Paper, Scissors なんだな、たぶん。本番中はよく考えなかったけど。

k の上限は高々 100 ではあるけれど、2^k 通りの勝敗を考えるには大きすぎる数だ。まあ頭の中で考える分にはあまり関係がないので、トーナメントをシミュレーションして、その際に文字列 s のどの部分を参照するのかを確かめていた。優勝者の手、準優勝者の手、準々優勝者の手……がどこからやってくるのか、逆方向のシミュレーションもした。

 提出 #18467915 (AC)

最初の提出まで 30 分。C 問題という段階で解けなくてもともとなので、あせる理由はどこにもない。

 D 問題 く

残り時間は 30 分だったけど考えるだけ考えた。

  • 移動方法は3通り。軸となる2つの石を選べば決まる。
  • 石の配置は単位正方形を基準にして分類できる。すなわち、ある一角(たとえば左上)の座標と、くの字の折れ曲がり部分の位置(左上、右上、左下、右下)の組み合わせで決まる。
  • さて最小の移動回数は?

四角形の座標移動をまず考えた。

  • 水平方向、垂直方向に1移動するには2手かかって、くの字の向きが変わる。
  • 水平垂直同時に1ずつ移動するには3手かかって、くの字の向きはそのまま。

ここまで考えたが、この安定した移動に入る前と出るときに何手かかるのか数え切れなかった。B 問題のことを思い出して探索すればいいじゃない、ということには気がついたが、その探索がどういう形になるのかおぼろにも想像ができなかった。

というわけで D 問題はひとつの提出も用意できないまま放置している。


あ、3通りじゃないや、5通りある。じゃあいろいろ変わってきちゃうね。

え? 7通りある? だから最初から最後まで機械に数えさせるべきなんだな。


2020年11月28日 (土) 作業の待ち時間に Firefox の 22 (古い!) を使って時間潰しや情報収集をしたのだけど、その動作の(ESR 52.9と比較した)キビキビ具合は感動ものだった。SSD とかいらない。サーバーと暗号化方式で合意できなくて閲覧を拒絶される割合が半分を超えていた。チラシの裏に HTTPS はいらないとの考えのもと、この日記は HTTP で転送されています。いらないもののために何を捨てるのか。

最終更新: 2021-01-05T18:27+0900

[COSMOS] システムドライブを SSD に移した。(SSD 初体験)

やっとである。2012年と2015年と2017年に SSD 化の思惑を書いてるけど(2012111220150812p01)、今や2020年の末である。500GBで6500円である。

2007年に買ったHDDが丸13年間もった。いや、実はもっていない。最近になって不良セクタが見つかって名前も知らないファイルがいくつかロストしたのだけど、ケーブルを抜き差しして問題はなかったことにしていた。それから、ちょくちょくプログラムが一時的に停止するような状況が続いていて、IO 待ちなのかなと。ディスクがお隠れになってるのかなと。ファイルバックアップが正常に終了することが珍しくなったし、3回ほど INTERNAL_POWER_ERROR を理由とする BSoD を見たりもした。検索するとグラフィックスドライバが悪いとか、HDDが壊れてるとかで生じると書いてあるが、ドライバの再インストールとチェックディスクは不良セクタが見つかったときにもう済ませてある。処置無しである。完全な破局が訪れる前の今を限られた猶予として動かねばならぬ。

以前書いたとおり、まずは Complete PC バックアップをシステムドライブが入っているのとは別の HDD にとった。バックアップは毎月やっていることなのだけど、直前にまたとろうとしたら罠があった。少し前にとあるボリュームの容量を拡張しようとして、それは HDD の末尾に配置されていて後ろに空き領域がなかったものだから、拡張するにはベーシックディスクからダイナミックディスクへの変換が必要だという。誘われるままに変換したのが罠だった。ベーシックディスク上のボリュームである C ドライブのバックアップをダイナミックディスク上のボリュームに保存することはできないらしい。ダイナミックディスクをベーシックディスクに戻すにはボリュームをすべて削除する必要があるらしい。罠である。よりによってこのタイミングで。

ともあれバックアップを保存した HDD とフォーマットもしていない新しい SSD だけを接続した状態で Windows のインストール DVD から起動した。インストールは選ばずにその他のオプションから Complete PC バックアップからの復元を選んだのだけど、警告された。復元するとディスクはフォーマットされすべてのデータが失われると。それでも実行するかと。困ったのは、どのディスクがフォーマットされるのか全く示されなかったこと。画面上にはどのバックアップから復元するかを選ばせるリストがあり、T ドライブを選択したのだけど、それをどこに復元するのか、どのディスクがフォーマットされるのか、選ばなかったし提示されなかった。考えてみれば10年以上前にプレスされた DVD が昨日買ってきた SSD のメーカーや型番を知っているはずがないし、フォーマットしていないからドライブレターの割り当てもないし、どういう識別情報が提示できたかわからなくはある、……ような気がしたが、EFI でブートドライブの優先順位を決めるときに型番が利用できるのだから、デバイスに刻まれた文字列が利用できるはずでは? なんにせよ、いちかばちかで実行したらちゃんと SSD に C ドライブ(と Y ドライブも含めていた)が復元されていた。

さっきから C とか Y とか T とか、その他にもドライブレターの割り当てはないけど特定のパスに接合されたボリュームがいくつか存在しているように、細かくパーティションを分けている。NTFS ではそういうことは一度もないんだけど、ファイルシステムが FAT32 だったときはファイルの全ロストが何度もあった。BSoD もしょっちゅうだったし、そこからのコンボが現実の恐怖だった。失われるのはパーティション単位だから、巻き添えを少なくするために分けている。マウスを使ったファイル移動の既定がボリュームをまたぐ場合に(名前の変更だけで済まないからか)コピーになったりするけど、それだけ。Shift キーを押すか後で削除するだけの手間。

アイコンや文字のサイズなどデスクトップの設定がリセットされていたり、復元された Y ドライブ(まさしく自分の設定(レジストリ)が保存されている場所)が壊れているからチェックディスクを実行しろとファイルシステムからの鬼のような催促がイベントビューアに記録されていたりしたけど他は何も変わらず。もちろんレスポンスは速い。M.2 スロットなんてしゃれたものは 2011 年発売の MSI 990FXA-GD80 には付いていないし NVMe にも対応しないので転送速度は SATA3(実効転送速度 600MB/s)に律速される。500 MB/s 台が出ていたので大変満足です。HDD だとシーケンシャルでも 80 MB/s いけばいいところ。

SSD を知らない OS (Windows Vista) を SSD にインストールしてどうなるかはよくわからない。買った SSD のメーカーであるサムスンのユーティリティに期待していたのだけど、Samsung Magician 6 は Windows 7 以降でないとインストールできないらしい。Magician 4 はインストールできたけど当然ながら最近の自社製 SSD を認識しないので役に立たない。デフラグのスケジュールからは外したけど、他は何も。Trim はどうする? TxBENCH のインストールはした。総容量の4分の1しか埋まっていないしデータディスクは別にあるからここから大きく増えることもない。空き容量に任せてどうとでもなるんじゃないかな(なったらいいな)。


2020年11月27日 (金) このところここ半年ほどとくらべてあまりおなかが減らないわりに食欲も減ってなくて、冬に向けて太る準備をしているな、という感じ。抜け目なく体重と体脂肪率の推移を注視していかねばならない、とそう思うのでした(思うだけ)。


2020年11月24日 (火)

最終更新: 2020-12-08T00:48+0900

[Ruby] 多重代入の難しさの一例。(Ruby 2.7 と Ruby 1.9 で確認)

4月に「多重代入は遅くて時々評価順が難しい」と書いたけど、さらに難しいケースを考えた。クイズです。

a = *0..5 #=> [0,1,2,3,4,5]
b = *0..5 #=> [0,1,2,3,4,5]
a[i=2] #=> 2
b[j=2] #=> 2

a[i+=1] = a[i] # a はどうなる?
b[j+=1],= b[j] # b はどうなる?

a #=> [0,1,2,3,4,5]
b #=> [0,1,2,2,4,5]

a の結果を確認してから予想してカンマを付けたら予想通りの結果になったので驚きはないけど、やっぱり普通の代入とは違うんだなあと、それが遅くなる理由かなあと、思いました。

ゴルファーしかこんなコードを書こうとはしない? その通り。


2020年11月23日 (月) KLX300 が日本で買えるようになるといいなあ。(アメリカ仕様で) 137 kg だって。DR も XR も WR も、そして KLX もなくなってるもんなあ。


2020年11月22日 (日)

最終更新: 2021-05-07T14:51+0900

[AtCoder] AtCoder Beginner Contest 184/C,D,E

 C 問題 Super Ryuma

超竜馬の移動ルールを読み解くのが難しすぎると思うんだ。数学の言葉が通じない人のことを考えてほしい。なんとか解読した結果は、マンハッタン距離が3までの菱形の中と傾きが ±1 の直線上を移動できる、だと思った。

 提出 #18323156 (AC)

これ以上ない可読性を誉めてほしい。可読性とはこういうことだ。(他人が言う、ただの手癖レベルの)可読性なんぞいらない(どうして自分が書いたコードを、あなたにとって読みやすく自分にとってはそうではないように書き直さなければいけないのですか?)。この提出の可読性も認めてもらわなくて全然構わない。

 提出 #18373736 (WA×1)

先の AC 提出と全く同じ内容だが after_contest_01.txt という入力だけ WA になった。テストケースが弱かったので追加されたらしいのだが、みごとそれに甘えた嘘解答だったことが明らかになったということ。

 提出 #18374012 (AC)

after_contest_01.txt を通して本当の AC。可読性は維持している。

もちろん誇大表現は話半分に受け取らなければいけない。数学の言葉が通じない人向けに日本語で移動ルールを書けば曖昧さが入り込む余地が大きくなる。同じように、定義式を見て理解できることに日本語のラベルを付けたところで、ラベルの妥当性には疑問の余地がある。可読性(ラベル)は誰のためのものか。正確な理解ができない人間のためではない。時間がなくて式を読む時間を省略したい人に向けた補助である。時間があれば定義式を読むべきだし、時間がなくても即座に読み解ければそれに越したことがない。

異なる可読性もあると思う。読者を惑わせる無駄や回り道、曖昧さがなく目的に直結する、論理的で考え抜かれたシンプルなコードだ。そちらは追求していきたい。考え抜かれた結晶を、目で字をなぞっただけで読み解けるはずがない。読みやすさとは密度の薄さのことではない。一行を読むのにかける時間を変えればいいだけのこと。薄い内容をいっぱい読むだけ読んでも理解ができていなければ意味がない。理解するには知識と考える頭が必要だ。その時の対象はごく小さく限られている方が集中できて良い、というのが自分の考えであり性質。読むときも書くときもそちらを追求していきたい。

 D 問題 increment of coins

期待値? 定義しかわかりません。試行回数が不定? 一瞬で放り投げかけたが踏みとどまった。

A, B, C 3つも変数があると頭がパニックなので A*10000+B*100+C と1変数にエンコードしてみたらやや落ち着いた。試行を繰り返す遷移を書いて計算して足し合わせたら答えになった。求めたのではなく「なった」のである。

ただし += とすべき確率を = で上書きしていたためになぜかサンプル4だけ答えが合わなかった。「なぜか」はサンプル1から3の答えが合ったことに対する疑問。これのデバッグに30分ちかく溶かした。

 提出 #18339328 (AC / 867 ms)

同じ Ruby で 300 ms 台の提出があるのと比べると 867 ms はかなり遅い。しかしもう考えたくない。

 E 問題 Third Avenue

10分しか残っていなかったのでコンテスト時間中の提出は適わなかった。ただやるだけだと思ったけど、それを手早く正確にやる能力がなかった。多少の時間の余裕があってもダメだったろう。

 提出 #18348009 (WA×1 / TLE×3)

TLE はいいけど WA はいただけない。今日は寝る。

 提出 #18371108 (AC / 2995 ms)

はい、やるだけでした(だがそれができなかった)。TLE まであと 5 ms なのは改善の余地があるだろう。

WA の原因は再訪防止のマーキングを、行こうとするときにチェックを付けるか、着いたときにチェックを付けるかの差だと思う。効率を優先して先走ると間違える。過去に何度も同じやらかしをしているので多分そうだと思う(今ここでよく考えないから次もまた同じミスをするんじゃないか?)。

 提出 #18397451 (AC / 1883 ms)

30% あまり速くなったがあまり本質的ではない改善要因(予想)が5つあるだけである。

  • 再訪防止フラグ(配列 T)のインデックスを誤って使用していた。

    問題として与えられるグリッド文字列に番兵として1行1列を加えていたのだけど、再訪防止フラグはそうではなかった。それにもかかわらず番兵込みのインデックスを使って(予防的な)再訪チェックをしていた。

    訪れるべき所を訪れ損なっていなかったのは運が良かっただけだし、訪れなくてもいいところを無駄に再訪していたと思われる。

  • 壁のあるマスにも再訪防止フラグをセットするようにして、予防的な再訪チェックに引っかかるようにした。
  • テレポーターの前処理をする際に正規表現を引数にした String#index を使っていたのだけど、パターンを /[Sa-z]/ から /[a-z]+/ にした。

    S の有無は関係なくて、連続するテレポーターをひとまとめに処理対象にした。

    String#each_char で1文字ずつ文字種をテストするのにくらべて正規表現という仰々しい道具を持ち出した String#index が有利になる条件は、テレポーターが疎に配置されていて処理対象外の文字を大きくスキップできる場合だと思う。

    逆に言えば、テレポーターが密に配置されていて index が1ずつしか増加しないとき、ただの文字種比較とパターンマッチングを伴うメソッド呼び出しの1回あたりのコスト差が顕在化する。

    index メソッドの呼び出し回数を減らすためのパターン変更。

  • 上下左右の移動先を処理する4要素の配列のイテレーションを展開してべた書きした。
  • 使用済みのテレポーターの処理に関して、空の配列を concat しないように事前にチェックするようにした。結果が同じでも、記述が煩わしくても、パフォーマンスのためには事前にチェックする方が良い。

    インクルードガードにも内部インクルードガードと冗長インクルードガードの2種類があって、冗長でもインクルードそのものをスキップするように書けばファイルを開いて閉じる手間が省略できてコンパイル時間が短くなる。最新のコンパイラ、プリプロセッサがそんな愚直なやり方をしていると信じる理由はないけども、原理的にはそういう差がある。

 提出 #18446644 (AC / 1490 ms)

もう 20 % ほど速くなった。

  • 添字を使った文字列へのアクセスと配列へのアクセスは倍ちょっと速さが違う(Ruby 2.7)。添字の大きさは関係ないみたい。ちなみに Ruby 1.9 は 10 倍違った。
  • 再訪防止フラグを早めに立てるようにしたからキューが長くなりにくいと思う。予防的なチェックが本式のチェックになったからメインループでのチェックも不要になった。
  • 前処理に正規表現を使うのをやめて1文字ずつ細かく準備できるようになったから、再訪防止フラグを利用してメインループの when 節が1つ分減った。

それから、1つだけの WA の原因はよくわからなくなった。少なくとも再訪防止フラグをセットするタイミングが必ずしも理由になるわけではない(今回の提出では移動しようとする先のフラグを立てるようにしたから)。何かをミスればそれを咎めるテストケースがちゃんと用意されているというだけ。別の提出では別のケースが1つだけ WA になった。


2020年11月21日 (土)

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

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

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

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

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

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


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


2020年11月11日 (水)

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

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

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

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

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

 M 問題 筆塗り

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

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

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

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

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

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

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

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

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

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

 方針
  1. 根を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 メソッドを使っていたうっかりの訂正と、子の色リストを得るのにランダムアクセスをやめてスタックから連続する領域を取り出すようにしたこと。これで1減って残る TLE は2個。

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

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

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

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

やった!!!

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

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

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

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

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

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

    • ブロックパラメータは必ず1つ? {|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 と書かなくてもいいという1点でまず、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。短くて速くて省メモリ。

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

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

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


2020年11月08日 (日) [AtCoder] AtCoder Beginner Contest 182。なんか呪われていた。デバッグ出力を消し忘れて All WA を食らった。何度も。提出直前のささいな(!)修正によってサンプル入力すら通らなくなっているのに、気付かずに提出して WA を食らった。何度も。問題の読み損ねも複数あったし、サンプル出力が一致しているかどうかの判断ミスもあった(実行結果が1なのか0なのか読み取れていなかった)。コンテストが終了してから B 問題(!)に取りかかって3分後に初 AC が出た。その8分後に D 問題に初 AC が出た。その11分後に E 問題に初 AC が出た。つまりコンテスト中には A 問題と C 問題しか通っていなかった。B も D も時間をかけて通せていなかった。あと思い出した、1分前にスマホのアラームをセットしていたのに鳴る前に始まっていた。常時基地局とやりとりしていて2分も遅れるなんてことがある? なんの呪いなんだ。


2020年11月07日 (土)

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

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

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

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

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

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

 提出 #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)

2番手以降の集団をダブルスコアで突き放す 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 という先読み関数で探索の打ち切りを判断しているところ。それでペイするんだってところと、1枚のスクリーンショットを刻む発想が(だって刻んだ画像の価値はゼロですよ。常考)。

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

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


2020年11月01日 (日)

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

[AtCoder] AtCoder Beginner Contest 181/D,E,A

 D 問題 Hachi

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

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

 提出 #17805410 (TLE)

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

 提出 #17808009 (AC)

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

 E 問題 Transformable Teacher

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

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

 提出 #17820870 (AC)

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

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

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

 A 問題 Heavy Rotation

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

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

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

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

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

  • 出力は1回1行だけしか行われないのに puts が2つ見えるのは読み手にやさしくない。
  • もし~ならこうする、さもなければこうする、という構成はあまりに手続き的。もうすこし進んだパラダイムを学んでも良い頃合いでは?

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

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

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

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

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

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

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

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

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

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

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

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

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


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

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

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

 @2020-11-04

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

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


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

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

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

 提出 #17842898 (AC / 819 ms)

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

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

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

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

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

 提出 #17848105 (AC / 93 ms)

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

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

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


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

_,*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)、1バイト増えて 220 バイト。Windows ではプロセス ID は4桁だったんだけど。

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

 提出 #17868705 (AC / 217 Byte)

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

3文字減った理由がなかなか味わい深い(と思う)。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

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

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

* while/until などの条件節で初登場する変数が、なぜか後置修飾される本体処理で利用できないのが不思議で不満。条件式はループに先立って必ず評価されているはずなのに。begin ~ end while ~; とは違うのに。


2020年10月31日 (土) 過去を振り返ると「あの頃の俺は賢かったなあ」という感想がよく出てくる。例えば AtCoder を始めたばかりで ABC の E 問題の難しさ加減や ABC と AGC の違いがわからなかった頃。例えば高校生の頃。所詮自分なので高が知れているということはあるけど、それでも今となってはついていけない感じがする。集中の度合いが違うだけかな。だといいな。