最終更新: 2020-12-03T19:37+0900
先月28日土曜日の振り返り。ARC なので A 問題が 300 点からスタートする。２問解けたらまあまあという感じ。配点が同じ 300 点、400 点でも、ABC のと比べるとちょっと手強い印象を持っている。
時間は長めの２時間。ABC と違って C、D、E、F 問題にはだいたい取り付く島さえないので、時間が足りなくなるということはまずない。簡単すぎるテストと難しすぎるテストは時間が余るという点で共通する。
上の階に上がるのに階段と廊下の２種類の手段があるというのが不思議な設定だが、床の高さが半階分ずれた２棟が上りと下りのスロープで結ばれていると解釈するツイートを読んだ。なるほど。ところですべてのフロアが渡り廊下で連結されているなら、それも水平１本ではなく三角形で繋がっているなら、２棟は一体の構造物として設計されているのでは？ そのとき「廊下」はどのような形態になりますか？
11分ちょっとで提出している。こうだったらこうだな、こうだったらああだなと考えながらとりあえず書き出してみてそれをそのまま提出した。
考えたこと。
節約する本数 k から n (の下限)を求める式が n ≧ Σ(k+1) = k+k*(k+1)/2 だということはすぐにわかったけど、n が与えられたときに k の最大がいくつになるのかを求めるのに、sqrt を使ってずっと考えていた。B 問題に取りかかってから最初の提出まで 46 分。
n の制約上限は 10^{18} であり、(10**18).bit_length は 60。なんだ探索すればいいじゃないと気がついたらもう問題は残っていなかった。
RPS って Rock, Paper, Scissors なんだな、たぶん。本番中はよく考えなかったけど。
k の上限は高々 100 ではあるけれど、2^k 通りの勝敗を考えるには大きすぎる数だ。まあ頭の中で考える分にはあまり関係がないので、トーナメントをシミュレーションして、その際に文字列 s のどの部分を参照するのかを確かめていた。優勝者の手、準優勝者の手、準々優勝者の手……がどこからやってくるのか、逆方向のシミュレーションもした。
最初の提出まで 30 分。C 問題という段階で解けなくてもともとなので、あせる理由はどこにもない。
残り時間は 30 分だったけど考えるだけ考えた。
四角形の座標移動をまず考えた。
ここまで考えたが、この安定した移動に入る前と出るときに何手かかるのか数え切れなかった。B 問題のことを思い出して探索すればいいじゃない、ということには気がついたが、その探索がどういう形になるのかおぼろにも想像ができなかった。
というわけで D 問題はひとつの提出も用意できないまま放置している。
あ、３通りじゃないや、５通りある。じゃあいろいろ変わってきちゃうね。
え？ ７通りある？ だから最初から最後まで機械に数えさせるべきなんだな。
最終更新: 2021-05-07T14:51+0900
超竜馬の移動ルールを読み解くのが難しすぎると思うんだ。数学の言葉が通じない人のことを考えてほしい。なんとか解読した結果は、マンハッタン距離が３までの菱形の中と傾きが ±1 の直線上を移動できる、だと思った。
これ以上ない可読性を誉めてほしい。可読性とはこういうことだ。(他人が言う、ただの手癖レベルの)可読性なんぞいらない(どうして自分が書いたコードを、あなたにとって読みやすく自分にとってはそうではないように書き直さなければいけないのですか？)。この提出の可読性も認めてもらわなくて全然構わない。
先の AC 提出と全く同じ内容だが after_contest_01.txt という入力だけ WA になった。テストケースが弱かったので追加されたらしいのだが、みごとそれに甘えた嘘解答だったことが明らかになったということ。
after_contest_01.txt を通して本当の AC。可読性は維持している。
もちろん誇大表現は話半分に受け取らなければいけない。数学の言葉が通じない人向けに日本語で移動ルールを書けば曖昧さが入り込む余地が大きくなる。同じように、定義式を見て理解できることに日本語のラベルを付けたところで、ラベルの妥当性には疑問の余地がある。可読性(ラベル)は誰のためのものか。正確な理解ができない人間のためではない。時間がなくて式を読む時間を省略したい人に向けた補助である。時間があれば定義式を読むべきだし、時間がなくても即座に読み解ければそれに越したことがない。
異なる可読性もあると思う。読者を惑わせる無駄や回り道、曖昧さがなく目的に直結する、論理的で考え抜かれたシンプルなコードだ。そちらは追求していきたい。考え抜かれた結晶を、目で字をなぞっただけで読み解けるはずがない。読みやすさとは密度の薄さのことではない。一行を読むのにかける時間を変えればいいだけのこと。薄い内容をいっぱい読むだけ読んでも理解ができていなければ意味がない。理解するには知識と考える頭が必要だ。その時の対象はごく小さく限られている方が集中できて良い、というのが自分の考えであり性質。読むときも書くときもそちらを追求していきたい。
期待値？ 定義しかわかりません。試行回数が不定？ 一瞬で放り投げかけたが踏みとどまった。
A, B, C ３つも変数があると頭がパニックなので A*10000+B*100+C と１変数にエンコードしてみたらやや落ち着いた。試行を繰り返す遷移を書いて計算して足し合わせたら答えになった。求めたのではなく「なった」のである。
ただし += とすべき確率を = で上書きしていたためになぜかサンプル４だけ答えが合わなかった。「なぜか」はサンプル１から３の答えが合ったことに対する疑問。これのデバッグに30分ちかく溶かした。
同じ Ruby で 300 ms 台の提出があるのと比べると 867 ms はかなり遅い。しかしもう考えたくない。
10分しか残っていなかったのでコンテスト時間中の提出は適わなかった。ただやるだけだと思ったけど、それを手早く正確にやる能力がなかった。多少の時間の余裕があってもダメだったろう。
TLE はいいけど WA はいただけない。今日は寝る。
はい、やるだけでした(だがそれができなかった)。TLE まであと 5 ms なのは改善の余地があるだろう。
WA の原因は再訪防止のマーキングを、行こうとするときにチェックを付けるか、着いたときにチェックを付けるかの差だと思う。効率を優先して先走ると間違える。過去に何度も同じやらかしをしているので多分そうだと思う(今ここでよく考えないから次もまた同じミスをするんじゃないか？)。
30% あまり速くなったがあまり本質的ではない改善要因(予想)が５つあるだけである。
再訪防止フラグ(配列 T)のインデックスを誤って使用していた。
問題として与えられるグリッド文字列に番兵として１行１列を加えていたのだけど、再訪防止フラグはそうではなかった。それにもかかわらず番兵込みのインデックスを使って(予防的な)再訪チェックをしていた。
訪れるべき所を訪れ損なっていなかったのは運が良かっただけだし、訪れなくてもいいところを無駄に再訪していたと思われる。
テレポーターの前処理をする際に正規表現を引数にした String#index を使っていたのだけど、パターンを /[Sa-z]/ から /[a-z]+/ にした。
S の有無は関係なくて、連続するテレポーターをひとまとめに処理対象にした。
String#each_char で１文字ずつ文字種をテストするのにくらべて正規表現という仰々しい道具を持ち出した String#index が有利になる条件は、テレポーターが疎に配置されていて処理対象外の文字を大きくスキップできる場合だと思う。
逆に言えば、テレポーターが密に配置されていて index が１ずつしか増加しないとき、ただの文字種比較とパターンマッチングを伴うメソッド呼び出しの１回あたりのコスト差が顕在化する。
index メソッドの呼び出し回数を減らすためのパターン変更。
使用済みのテレポーターの処理に関して、空の配列を concat しないように事前にチェックするようにした。結果が同じでも、記述が煩わしくても、パフォーマンスのためには事前にチェックする方が良い。
インクルードガードにも内部インクルードガードと冗長インクルードガードの２種類があって、冗長でもインクルードそのものをスキップするように書けばファイルを開いて閉じる手間が省略できてコンパイル時間が短くなる。最新のコンパイラ、プリプロセッサがそんな愚直なやり方をしていると信じる理由はないけども、原理的にはそういう差がある。
もう 20 % ほど速くなった。
それから、１つだけの WA の原因はよくわからなくなった。少なくとも再訪防止フラグをセットするタイミングが必ずしも理由になるわけではない(今回の提出では移動しようとする先のフラグを立てるようにしたから)。何かをミスればそれを咎めるテストケースがちゃんと用意されているというだけ。別の提出では別のケースが１つだけ WA になった。
最終更新: 2020-11-22T08:26+0900
コンテスト中に問題文は理解していたと思う。文は。問題まで理解していたかは知らない。
これを DFS で探索しようとした。だめな選択に早々に見切りをつけて手戻りを減らすために、選択肢の少ない頂点に優先して選ばせようとした。
あとで提出して確かめる。TLE になるならさらに考えないといけない。WA になるなら問題文を読み直さないといけない。
あ、選ばなくていい頂点もあるのか。木の根に相当する頂点。選ばれる辺の数は N-1 以上になるから必ずなにがしかの木＋余分な辺になるわけだけど、それがどういう意味を持つのか。最後の頂点だけ選べなくてもいいってだけ？ わからなくなってきた。
最終更新: 2021-02-20T23:02+0900
今回は K 問題までたどり着けなくて、J 問題で詰まった。まだ解けていない。特定のカテゴリの入力が全滅しているから、見落としているパターンがあるし、それを除いてもまだ AC は遠そう。だけど ABC184の E 問題 Third Avenue は解けてるんですよ>20201122p01.03。不思議だなあ。
その後 K 問題は解けたし、なんなら L 問題も解けたけど、時間はかけた。そして M 問題。
まだ３つの TLE に阻まれている。
何について繰り返すか、その通りがかりに素早く答えを出すためにどんな最適化されたデータが準備できるか、というのが考えどころ。
実行時間の制限が長めの４秒ではあるけど、制約上の上限がどれもこれも 10^5 だから、何かについて繰り返しているあいだに探索やら配列埋めやら時間がかかる処理をするわけにはいかない。
たとえばクエリごとに色記録配列を埋めるとか、辺(=頂点集合を左右に分ける)ごとに関与するクエリを逆順に検索するとかは間に合わない。Ruby では間違いなく。
Array にはない ^ メソッドが使いたくて require 'set'; した。「対称差」を求めるメソッドらしい。しかし遅い。
３つの演算子(+, -, &)を使って自分で Array#^ メソッドを実装した。+ の代わりに | メソッドを使うこともできるが速くなる気がしない。まだ遅い。
bsearch_index と concat で Array#^ メソッドを実装した。演算子を使ったシンプル実装より必ずしも速くなるわけではないが、遅くなるのは TLE になるほどではない小さいケースだし、直線に近い(色リストが長くなりやすい)木では有利になるためか TLE が減った。しかし残った３つの TLE (random_17.txt, random_19.txt, random_28.txt) はどの提出に対しても実行時間が上限に張り付いたままで、打開するヒントが見えない。どういう形の木なのか。
N 個のノードについて繰り返しながらソート列(色リスト)のマージを繰り返すのが、時間的にもメモリ的にも厳しい。だけどこれが嘘のように時間制限をクリアできる魔法があるとも思えない。十分にストレートで迷いのないコードだと思う。この方針のままなんとか滑り込みたい。
「打開するヒントが見えない。どういう形の木なのか」と書いたけど、直線の反対ということで子供が 100, 1000 あるような木を用意したらてきめんに遅くなった。どうしようかな。
変更点はソート済み配列から最大値を取り出すのに max メソッドを使っていたうっかりの訂正と、子の色リストを得るのにランダムアクセスをやめてスタックから連続する領域を取り出すようにしたこと。これで１減って残る TLE は２個。
4400 ms が 4200 ms になったりするとあとちょっとだとわかるんだけど……。
あるノードに合流してきた色リストは LCA と z-order がともに昇順になるように並べ替えることができて、そこから外れる色は色塗りの出番がなくて無視できるんだけど(※)、それで良くなるものか……。
※ z-order が大きければ他の色より前に出られる。LCA が小さければ前にある色が LCA に到達して退場するのを待てる。どちらでもなければ前に出る前に退場させられる。
やった！！！
LCA が正解だったみたい。木を遡りながら色リストをマージするのは同じだけど、LCA を利用してリストを短くしたら TLE が解消した。
うれしい。とってもうれしい。ここ２、３日トイレでもお風呂でもふとんの中でも考えていた。あっさり AC されているとやる気が萎えるので見ないようにしていたが、Ruby で AC 一番乗り。
ところで PyPy3 のこのシンプルかつ Python 系で一番速い提出 #18047488 (819 ms) はなんの魔法だろう。半分以上が入力の処理で、残りでヒープの出し入れをしているだけ。
JIT で速いから余計な手をかけないで済むということなら Ruby には関係のないことだけど、考察が足りていなくて自分のアルゴリズムがヘボだというなら、学ばなければいけない。
それはそれとして、LCAの確定を待つ色のリストはソート済み配列をやめてプライオリティキューにすべきだし、lambda M の中の Array#slice! と Array#insert は配列に相応しいメソッドではない。配列を酷使しすぎている２点に改善の余地がある。
初めて Crystal を書いた。色々言いたい。
delete_if と inject メソッドがない。reject! と delete_if は完全に同じではないし、reduce と inject がただのエイリアスなら用意しないのは罠でしかない。
inject は配列の各要素のあいだに演算子を挿入するイメージのメソッドらしい。それを読んでから inject の仕様に悩んだことはない。
lambda メソッドがない。テキトーに Proc.new と書いてみたけどダメだったので -> () {} と書いた。アロー記法は好きではない。
パラメータには型注釈が必須だったけどコロンの前か後ろか両方にスペースが必要だったらしい。詰めて書いたら「ダメだ。我は ) を所望する」と怒られ、素直に ) を書いたら型注釈を付けろと怒られる無限ループ。
後付けするなら記号は選ばなければいけない。Ruby の仕様(メソッド名と文字リテラル)なら条件演算子はむしろないほうがいいし、だけど条件演算子とシンボルリテラルは現実に存在しているし、記号は選ばなければいけない。
_ が使えない。なぜ？定数と変数が同じスコープ、見た目通りの実行軸にないように思う。
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.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 のソースコードではなく、そのような入力を与えた外部にある。事の決定権はコンパイラにはない。
&. によるメソッド呼び出しに対応していれば話は違った。
[] とか {} とか書けない。とりあえず領域を確保するために [nil]*N と書くのもタイプミスマッチで都合が悪い。すべてドキュメントの不足が悪い。スペックしか頼れるものがなかった。
俺は人類の手には多少余るとしても、プログラマを信頼し、力を与えてくれる言語が好きだ。安全のためと称して枷をはめようとする言語は選ばない。安全な
では Ruby の切れ味は？ Ruby はプログラマがやりたいことの邪魔をしないのがいい。Ruby がコードゴルフに向いているということとも関連する。キーワードやら形式やら、本筋の処理と無関係でありながら書かなければいけないお約束が少ないということ。
Crystal の型はどうか。プログラマに力を与えるためではなく、処理系が力を得るためにプログラマが受け入れる枷だというのが、少し触っての印象。枷を受け入れるなら C++ が選択肢に入る。
const 教の信者というのは最も“const と書きたくない”人種のことだと自認している。const という当たり前のことを、どうしてあちこちそちこちに書いて回らなければいけないのか。所有権も魅力的だけど、const と書かなくてもいいという１点でまず、Rust の評価が高い。
C++ も Ruby も好きだけど弱点がある。Rust には期待ができる。でもコンパイラが起動できないんだよなあ。「rustc.exe - エントリ ポイントが見つかりません。プロシージャ エントリ ポイント K32EnumProcessModules がダイナミック リンク ライブラリ KERNEL32.dll から見つかりませんでした。
」 本でも読むか。
#18069462 と比べて、-1016 Byte / -313 ms / -33108 KB。短くて速くて省メモリ。
先に書いたように、「クエリごとに色記録配列を埋めるとか、辺(=頂点集合を左右に分ける)ごとに関与するクエリを逆順に検索するとかは間に合わない」のはたぶん間違いないけども、２つを混ぜてクエリの逆順に効率良く色記録配列を埋めるところまでは考えが及んでいなかった。
時間軸を反転することで、一度塗ったところを再度塗らないでスキップしたい
その方針でやってみれば、前半はほとんど同じことをやってるんだけど、下準備を終えたあとのメインループでは、ソート済み配列をマージする代わりにスキップしながら親をたどっていた。親をたどる方が短く書けて簡単！
最終更新: 2021-05-07T15:06+0900
DP の基本形といっていいほど典型的な DP。見え見えの誘いに乗りたくなくて他の解法を考えてみたけど思い付かなかった。それに心配しなくても Ruby ならではのお楽しみポイントがちゃんとあった。
実行時間の変遷が見どころ。
N×K×W のループは上限が2500万回であり、Ruby で TLE を避けようと思ったら桁を１つ減らさないといけない。予想された結果。
N のループが K 回に達するまでは K のループを K 回まわす必要がないよねっていう節約作戦で AC になった。制約は K <= N <= 50。
提出一覧が 1000 ms を超えるグループと超えないグループに分かれていたので中を見たら、添字と値が入れ違っていた。
B の値域が(W にくらべて)かなり狭い範囲に限定されているのがポイントで、速い方はループで走査する DP 配列のサイズがおよそ半分で済む。
２番手以降の集団をダブルスコアで突き放す zazaboon さんの提出 #11417636 (150 ms) を調べた結果。
以上の点を真似したのに加えて、考えられるこちらのアドバンテージが
a = [a,b].min と書くより a = b if b < a と書いて代入を省略できる方が速い。(だけど本当は宣言的な変数定義がしたい。操作ではなく結果について書きたい)前後のリストを比べると後ろは問題と関係のない比較的どうでもいい内容が並んでいるね。
いまのところの Python 最速。AB 配列を幅対重要度比でソートしてからの DFS なんだけど、すごいのが _greedy_by_width と _greedy_by_num という先読み関数で探索の打ち切りを判断しているところ。それでペイするんだってところと、１枚のスクリーンショットを刻む発想が(だって刻んだ画像の価値はゼロですよ。常考)。
使う使わないの二択だと比率がちょっと悪くても残った隙間にぴったり収まる方が重要度を高められることがある。先読みでその可能性を取りこぼしては答えを誤る。だからあくまでも比率のいいスクリーンショットから使う。ぴったり収まらないなら切り取って収まる分だけ使う。そういう考え。
最近別の問題を自分が DFS で解いたときのことだけど、「さっきの TLE 提出を微修正したら AC になった。事前に XY 配列をソートするだけ。二択による手戻りを最小限にするために、選択肢の優劣が明らかで覆りにくいものを最初に選ぶようにした」なんてぬるいやり方よりずっと突き詰めている。すごいなあ。
最終更新: 2020-11-06T01:42+0900
ほんの一瞬、1,10,100,1000,10000,... を８で割った余りに与えられた数字を掛け合わせて８の倍数を作るゲームかと思ったけど、組み合わせが膨大で無理そうだった。
こういうのって８の倍数が千とか万とかキリのいい数字になったらそれより上の桁の数字が何であっても千とか万の倍数であり８の倍数だから無視していいんだよねってことで irb で実験したら、４桁目から上はもう無視していいみたいだった。1000 = 8×125。３桁で８の倍数が作れれば良し。
物量に頼った雑なやり方で TLE を食らった。
お留守だった脳みそをなんとか働かせて tally メソッドで集計をすることにした。
とくに悩むところはなかった。全体にペアの差を最小にしたいならソートして隣同士で組み合わせるしかないと思った。あとは妖怪先生(え？わたし？)をどこに潜り込ませるかだけ。
データ構造も悩まなかった。右の人と組む場合と左の人と組む場合の２種類の階差数列が必要だな、定数時間である範囲の数列の和を求めるには累積和だな、と。
惜しむらくは提出時刻がコンテスト終了の６分後だということ。
こうなってみると B 問題 Trapezoid Sum で等差数列の和の式を悠長に組み立てていたのが悔やまれる。何回やっても全然答えが合わねーの！ いま検索したら Wikipedia に n(a1+an)/2 みたいな、自分が考えてたのよりずっと簡単な式が書いてあったりして、あほくさくなってくる。ちがう、お前があほなんだ。この式に16分かけた>#17793713。展開して整理する時間も惜しかった。最後なんて式はもう合ってるのにサンプル入力のコピペに失敗して答えが合わないせいで式の検討をやり直したからね。
次の C 問題 Collinearity ではさっさと２点を通る直線の式(軸に平行な直線にも対応したもの)を検索している>#17796631。７分かかってるのはタイピングとサンプルを使ったテストの時間。
こういうコードをゴルフ的だと考えるとしたら、それは考え違いだと言いたい(誰に向かって言っているのか謎だが)。
puts %w(White Black)[gets.to_i&1]
比較対象は例えばこんな感じ。
if gets.to_i.even? puts 'White' else puts 'Black' end
２番目のようなスクリプトを書く前に自分が考えること……
もし～ならこうする、さもなければこうする、という構成はあまりに手続き的。もうすこし進んだパラダイムを学んでも良い頃合いでは？
そうする理由はかっこいいからとか新しいからとかではなく、変更に強くなるのとコードの複雑化を抑えることができるから。
何度かこの日記に書いてるけど、バリエーションを表現するのにコードではなくデータを使うということ>20150514、20181029。
データ(Black と White の文字列配列)が用意できたらあとは入力(gets.to_i)と出力を最短で結ぶシンプルで無駄のないコードを書くだけ。２の剰余を添字にすればよい。あえて迂遠な書き方をする普遍的な理由なんてない(バカと可読性は個人の属性)。これまで if (a == b) return true; else return false; などと書いてきたなら今すぐ悔い改めよ。
ま、それは極端だとしても、コアとなるコードは「何かを出力する」となるべきであり、その何かを作るのに if 文を書いたり、if 文を含んだ関数を一度だけ呼び出したり、事前に用意しておいたデータファイルを読み込んだりするのが良い。
「もし～ならこうする、さもなければこうする」という型のコードは２つの「こうする」に無制限に無関係な処理が書けるし、何もしないこともできるし、目的に対して自由度が高すぎる。もっと制限の強い型にはめれば読み手にいらぬ想定を強いることがない。
だけどアクセス制限にしろ型にしろ、制限を強める方向で書くには頭を使うのだな。おつむが弱いとカオスをばらまくことが避けられないのだな。
最終更新: 2020-11-05T19:41+0900
コンテストは終了しているので落ち着いて考えた。
2^{100}(=約126穣)通りになって大変。ダメでした。まあね、優先度を付けても裏をかくような難しいケースが良くなるわけじゃないからね。
Python の提出一覧を見たら２桁 ms の AC 提出がいっぱいあった。これはコードを書く前にもうちょっと考えなければいけないな。
F問題は、直感的に「釘と直線をグラフの頂点として、ユークリッド距離をコストにして辺を貼り、パスのコストを「通る辺のコストの最大値」としたときに直線から直線への最短距離÷2」が答えだと感じたので、それをダイクストラで実装したら通った。
ええっとですね、まずそれが直感的にわからないし、そのわかったことを読ませてもらってもそれがどういうことなのかわからないのですね。(そもそもユークリッド距離の概念が曖昧。名前だけ知ってる編集距離なんかと比べて一番普通の距離だと思うけど、そう思うだけ)。
前半はまあまあ想像できる。全頂点を一筆書きして通路を左右に分ける線を引いたとき、最も広い点と点のあいだに円を通すということだろう。だけど第３の点が邪魔をして最も広い点間を通れないことがあると思う。そこから後半の「最短距離÷2が答え
」につなげられない。
邪魔をしている第３の点が最も広い点間を挟むどちらかの点と直接繋がる経路というのが、より小さいコストを持つ経路なのであり、(でないと邪魔できない)、最短経路というのはそういう邪魔が入らない経路のことなのだろう。たぶんね。
答えが示されているからこそ、こうしてこじつけ気味にでも納得のいく解釈がひねり出せたけど、これが「直感的に
」ねえ……(遠い目)。
@kyopro_friends「アライグマ「F問題は……「半径rの円が通れる」っていうのは、「円の中心が障害物からr以内にならない」ってことだから、逆に障害物の方を半径rの円にしちゃえばいいのだ！」
@kyopro_friends「アライグマ「道がふさがったらダメだから、障害物同士の距離を全部計算しておいて、距離が短いところから順にくっつけていって、上の壁と下の壁がくっつくときが答えなのだ！」
これはわかる気がする(図もあるし)。でも逆にこのツイートを読んでもダイクストラ法で実装することがわからないね。
上のツイートとは関係なくさっきの TLE 提出を微修正したら AC になった。事前に XY 配列をソートするだけ。二択による手戻りを最小限にするために、選択肢の優劣が明らかで覆りにくいものを最初に選ぶようにした。
いつの間にか Ruby でも AC をとっている人がいて、しかも実行時間が２桁 ms なんだけど、UnionFind を使っているみたいだった。どういうこと？
あ、連結成分の管理か。コストの低い辺からつないで最小全域木ができあがったときに最後につないだ辺のコストがそのまま答えになる。へー、クラスカル法と UnionFind が今初めてつながった。UnionFind とグラフに関連があるらしいのを今まで見て見ぬふりをして考えてこなかったツケであるな。こういう問題(「Reachable Towns」「Line++」)が全然グラフの問題に見えないんだよなあ。
そうしてみると問題文中で(N 本の)釘とされているものを Silver Woods と表現した問題名は、「木だよ、森だよ、グラフだよ」というヒントだったのだな。おしゃれ。
ところで、自分の提出も２つのケースが 819 ms と 170 ms なのを除けば２桁 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
よく考えたら AC 提出とランダム入力で答え合わせができるのだった。
$$ はダメだったので(#17866997)、１バイト増えて 220 バイト。Windows ではプロセス ID は４桁だったんだけど。
まあしかし、これだけ長いとこのスクリプトひとつとっても、いくらでも縮めどころが見つかりそうではある。
３文字減。ちなみに、変更に伴って入れ替わった２数を、どっちでもいいだろうとそのままにした結果は 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 がグラフアルゴリズムだっていう認識も実は全然持っていない。見えないんだよなあ。
* while/until などの条件節で初登場する変数が、なぜか後置修飾される本体処理で利用できないのが不思議で不満。条件式はループに先立って必ず評価されているはずなのに。begin ～ end while ～; とは違うのに。
最終更新: 2020-10-31T00:45+0900
数弱さんには頭が痛い問題だった。
経験値１を加算して増える強さを 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 にて)
コンテストが終わってから問題文を読んだ。イメージが湧きやすくていい問題名だと思う>Aerial。
2**17*17*17(=約3800万)回のループであり、サンプルですら TLE になるのがわかっていたが、ビギナーはワーシャルフロイド法が書けただけで満足なのです。これ以上は解らないのです。
以前解けなかった問題で参考にした提出。「後半はワーシャル-フロイド法に見える３重ループ。ただし街と街を結ぶ中継地点(一番外側のループ)は街ではなく経由地のリスト」。これをチラ見しながら書いた。
ダイクストラ法でコスト順に点を繋いでも時間がかかりすぎるのは確かめていた。問題に合わせたチューニングが何かできないか、そもそも総当たりのワーシャルフロイド法で可能なチューニングがあるのだろうか、と考えていたが思い付かない。コードを眺めてみよう。
という感じの苦肉の策で 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[都市１][無] でも関係はないかな。
「スタートが 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 が取り得る値の最小が１だとばかり思っていたから、０にしたい場合を例外扱いしていた。活用したい仕様。
「同じ都市を２度以上訪れて得することはない
」、という考察を何か所かで読んだので、next if 0 < v[f-1] という条件を真ん中のループに足してみたら、1283 ms が 852 ms になった。わーお。
ちなみに Integer#[] である桁のビット(0,1)が得られるのだけど、最下位(右端)のビットが０番目になっている。負の添字は必ず０が返るっぽいので、今度は意図してこの仕様を利用した。
「負の添字は必ず０が返るっぽいので、今度は意図してこの仕様を利用した
」とか書いたけど、０は望ましい結果ではなく、結果的にスタート地点である都市１だけは何度も発着を繰り返していた。
真ん中のループの繰り返しから都市１の分を引いて N 回を N-1 回にしたら、852 ms が 769 ms になった。もうこれ以上は無理でしょ。
Integer#times の方が Range#each より速いようだったので Integer#times を使っている。そのせいで f(rom) と t(o) で都市番号への対応付けがずれているのが罠。
経由地を記録したビットフラグ(v)から０のビットを抽出して真ん中のループと一番内側のループに利用したら、769 ms が 627 ms になった。さすがにもうこれ以上はないでしょ。
TLE を初めての AC に変えた立役者である next if NP[0][-1] <= c0 が、変形を受けながらずっと残っていたのだけど、いつの間にか用無しになっていたことがわかったので消したら、627 ms が 583 ms になった。沼っぽくなってきたぞ。
メモ配列を見たら 0 番目の要素が 0 と Infinity に決まっていて無駄なので、長さ N の配列が N-1 にできるけど、ちょっとした省メモリにはなっても速くはならない感じ。
沼といえばゴルフ。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 に似たコンパイル型言語)で投稿するという手があるらしいが知らないので。
うん、沼だ。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]
整形すれば普通に読めるあたり変態度が足りないと思うんだよなあ。発想に飛躍がない。
|| が二重ループの内にあるけど、大差ないみたい。とりあえず大きな数としての初期値に 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-18T20:31+0900
D 問題をしばらく考えて、
完全に内 = lambda{|n,a|
next (1+(n-a).abs).pow(2,M)
}
はみだし = lambda{|n,a,y|
n,a = a,n if n < a
y = a-1 if a-1 < y
next [完全に内[n+y,a]-完全に内[n,a],0].max
}
みたいな関数を書いたりしていたんだけど、ここから詰め切れる見通しが立たなかったので E 問題に手を出した。
方針はすぐに決まった。逆に考える。照明の置き方が 2^k 通りを網羅しているのだから、照明の置き方を考える必要がない。あるマスを照らす照明の置き場所が何か所あるかを数えることにする。
もちろんグリッドを１マスずつ移動しながら４方向に探索を進めるようでは TLE を免れない。N の上限が 2000 の時に 2N^3 マスの走査は認められない。
lambda P が４方向の探索を省力化する工夫なんだけど、２回の P の合計が後半の N^2 のループと同じくらいの重さであり、N^2 の上限が 400 万だということはループの中身がごく簡単な処理でなければ Ruby は１秒２秒で終了しないので、N^2 ×２の結果は TLE だった。
TLE の山を見てわかる通り、Ruby にとってこれは実装をがんばる問題らしい。そうとわかれば考えるより先に手を動かすのみ。
構造はほとんど同じ。lambda P の代わりの lambda F が４、５倍速いおかげで AC になった模様。スクリプト言語は自分で書いたスクリプトとランタイムライブラリの処理速度に雲泥の差があるので、プリミティブな処理を自分で書かずにいかに丸投げするかが肝要。
それと、２の冪乗を含む掛け算は展開すると一部がループの中身に関わらない定数になって外に出せる。２のＫ乗を１回だけ計算しておけば、ループの中の２の累乗計算は１回だけでいい。もちろんその計算結果は２回目３回目に備えてメモしている。
最終更新: 2020-10-17T17:20+0900
C 問題が解けなくて大爆死した回の ABC。「時間内に B 問題までしか解けなかったので今日の日記は C 問題」。F 問題が解けたら D と E も解けたつもりでいいんじゃないかな？
どういうデータであればクエリに答えが出せるか、どういうデータ構造であればひとつひとつのクエリに妥当な時間で答えが出せるか、とっても考えた。
「LOC (last occurrence of colors)」とか「QIR (q in range)」といった名前をとっかかりに部分的に形を作っていった結果、移動する終点に合わせて始点用のデータを(事前に用意するのではなく)継続的に発展させていくやり方に落ち着いていた。
色の列を空間としてではなく時間として処理すること*が振り返ってみての転換点。意識してではなく手探りで進めるなかでの変化だったけど。
でも TLE。ソート列やハッシュ表といった素朴な構造ではダメみたいだ。
BIT を持ち出しても TLE とは恐れ入りました。ソースコードが長くなるのが仰々しくて嫌だとか言っていられない。
TLE の山と AC 提出の実行時間を見るに、Ruby にとってこれは実装をがんばる問題らしい。そうとわかれば(略)。
配列と BIT に余分な要素を付け加えて単項マイナス演算子と引き算の数を減らしたり、配列の初期値を工夫してループの中の if を取り除いたり、1-origin な入力値を 0-origin に加工するのをやめたり、i-=i&-i を i&=i-1 に代えて演算子を１つ減らしたり、といった泥臭い改善の成果で AC。
こういう脳筋的努力は考察不足の可能性がちらつくと身が入らないのだけど、その心配はなさそうなので心置きなく。
これが Ruby で一番速い(しかも Ruby で一番早い AC でもある)。速さの秘密はよくわからない。クラスやメソッドなしですべてが一体だからだろうか。 初めて見たのだけど BIT の初期化をするこの行……
b = (0..n).map{|x|x&-x}
BIT 実装のキーでもある LSB を蓄えるこれは公差１の等差数列を初期数列にしようとすると現れる。蟻本の図を見ていたのだけど、LSB は内部配列の要素が分担する重みに対応している。倍率(公差)は好きに決めたらいいだろう。
BIT の初期化が多少複雑になっても実行時間でペイするのは変数 u の存在がある。自分の提出で答えを設定する式は Ans[q] = r-l+1-Dup[N-l] (変数 Dup が BIT) だけど、BIT の初期値の工夫により -l が消せても +1 も N-l も残る。そもそも BIT を使用する向きが違っているのだ。BIT から２回値を参照するのを嫌って自分は向きを決めたけど(※BIT の操作が一番のホットスポット)、変数 u があれば参照が１回節約できる。参照が同じ１回なら他の部分の有利が生きるということなのだろう。
* この「空間」と「時間」はユニバーサルな表現ではなかったかもしれない。三次元に囚われた話者の感覚に根差した主観的な意味が込められていて、理解する前提条件になっていると思う。
最終更新: 2020-10-14T18:33+0900
ACL は ARC と AGC の中間あたりの位置づけだそうな。この A 問題は 300 点問題。１問目のこれしか解けそうにない。
移動可能な範囲が第Ⅰ象限と第Ⅲ象限に限られるが、移動先の点からさらに移動先を選ぶことができる。双方向に移動可能だし、X と Y の比率を変えながらジグザグに Y=-X 方向に移動することもできる。ともあれこの感じ(「友達の友達は友達」)は UnionFind だと思った。
問題は Union する点の選び方で、見境なく Union したら TLE になった。
見境なくとは言っても、相互に移動可能なら片方向だけを取り扱えば足りるわけで、X 座標の昇順に処理することで X 座標の大きい方から小さい方だけを見るようにしている。X 座標のソートに関してもこの問題で NlogN の時間をかけるのはもったいなくて、線形時間でソート列が手に入る。
Union した中で一番条件のいいものだけ代表として残すようにしたら AC。
よくわからないが UnionFind ではない。キーは12行目の if x + min_y == N+1: だと思う。UnionFind で形作られるグループが持つ幾何学的性質が何かあるのだろうか。
右上がりの対角線上に並ぶ場合と右下がりの対角線上に並ぶ場合を対極として、その中間の状態がうまく考えられない。
X 座標と Y 座標がともに 1..N の順列だということから導かれる論理的必然性を何か見落としてると思う。
検索してたら答えらしきものが見えちゃったんだよな、maspy さんのページは避けてたんだけど他の所で。
頂点をソートして x 座標が小さい順に見ます。
頂点 i と頂点 i+1 について、「y1, …, yi が (N,…, N−i+1) の順列」であるときのみ非連結であり、そうでないとき必ず連結になることがわかります（あとで証明かなんかできたらいいな、、）
「わかります
」(わかりません)
maspy さんの提出に沿って*理解したことをひとつひとつコメントにしながら書いた。完全にそのままではなく、「# ymin の最初期化が必要？」とコメントしたように、ループ中の代入をひとつ省略した。(あ、タイポ。最初期化→再初期化)
しかし、ガイドなしの独力でこの道筋が見つけられるとは思わん。
けんちょん(敬称略)のページにわかりやすい図があった。へー、そうだったのか(まだ見えていなかった)。
「ACL Contest 1 A - Reachable Towns (300 点) - けんちょんの競プロ精進記録」
でも図を見てみたらある意味わかって当然の図ではあった(それがわからなかった)。つまり、x + y = N+1 という X と Y の関係式を見て幾何学的性質について考えたのだし、であれば、その性質は y = -x + N+1 という直線に関わるものでしかありえない。答えを目の前にしながら「わからんなあ」と悩むふりをしていたのだった。下手の考え……。
* ～に沿って、というのはある意味嘘。こちらにゴールがある、という指針だけを手にして考えた結果の式が一致することを確かめただけ。結果が同じなのだから考えたことの軌跡をコメントとして残さなければ完全丸コピと見分けがつかない。コメントを書くのは必然だった。
最終更新: 2020-10-10T17:39+0900
コンテスト時間は D 問題で詰まっているうちに終わってしまった。計算過程で余りをとらないと一部の入力で TLE になってしまうのだが、余りがうまく計算できなかった。何を言っているのか自分でもよく解らない。
一日経ってみれば普通に AC できた。どこに詰まっていたのか解らない。
もうちょっと書く。方針。
移動可能地点ひとつひとつに対してメモしていては TLE になる>提出 #16879797。
S の要素数は N に準ずるが、S を定義する区間の数は幸いにも最大で 10 に制約されている。メモの仕方を工夫して、絶対値ではなく変化量を記録する。どうせ地点を端から端まで処理するつもりなので、変化量をつどつど加算していけば絶対値は得られる。これでループ１回の書き込み量が区間の両端の数(最大で20)まで減る>提出 #16883620。TLE なのは、途中で余りを求めなかったから多倍長整数の桁数に比例した計算量に押し負けた結果。
ここから途中過程で余りをうまく求められなかった(冒頭に戻る)。
D 問題で詰まったのでコンテスト中に問題文は読まなかった。色気を出せば解ける D 問題も解けなくなるので。
すんなり書き下してデバッグの必要もなかった。N の値が膨大だが M の値がそれなりなので、余りの種類もそれなり。となれば A 数列は途中から循環する。
D 問題で詰まったのでコンテスト中に問題文は読まなかった。色気を出せば解ける D 問題も解けなくなるので。
すんなり書き下してデバッグの必要もなかった。縦軸横軸それぞれにブロックラインが単調に前進していくだけなので、それを BIT に記録した。
@chokudai「F問題とても好きな問題なんだけど、データ構造でいくらでも殴れちゃうのが残念……O(N)で解いてみてね＞＜
BIT は読み書きともに対数時間なので、さっきの提出は O(NlogN) になる。O(N) で解くというチャレンジ課題がまだある！
N に比例したループの中で長さ N(-1) の配列に書き込むとしても、書き込む要素の総数が 2N 以下にとどまるなら O(N) なんじゃないかな。かな？
ひと工夫しないと配列への書き込み量が N×N になってしまう罠がある。変数 ii を介在させて書き込みタイミングを一拍遅らせたことが書き込み量削減のキモ。これには以前日記で触れた「Scintilla 方式」が参考になった。その要諦は……「メインのデータ構造はギャップバッファ。そこに張る行インデックスの更新コストの問題。更新が必要なインデックスのエリアはある点から始まり必ず末尾で終わる。ある点をひとつ記憶しておくことで更新範囲をある点とある点の差分にすることができる。
」
ゴルフをしながら Ruby の中で最速タイムを記録していたのだった。異次元過ぎてさっぱりわかりません。
お風呂でなんとなし思い付いた。
メインループのイテレーションごとに X 軸と Y 軸が参照軸と更新軸のどちらかの役割を受け持つ。参照軸更新軸それぞれが N-2 要素のメモを持つ。メインループの中で……
前回の提出では更新軸のメモが更新の対象だったが、今度の提出では更新の一部が参照軸の参照時に分散している。その結果ループの中がストレートになり、値の大小関係によってあっちの値を参照したりこっちの値を参照したりという場合分けが不要になっている。しかし変わらないタイム差(たぶん配列参照のコストが大きい)。
メインループの中に２つの対称的な書き込みループがあるあたりが kotatsugame さんの提出と共通だと思ったけど、あちらでは一回に片方のループしか実行していなかった。たぶん参照軸のメモだけ更新しているのではないか。もはやこの軸の命名が意味不明であるが……。
更新軸が更新軸である所以はそれが「ブロックライン」をメモする軸であり、今後のスコア(何枚の黒石を裏返せるか)に影響するから必要があって書き込むからなんだけど、何枚の黒石を裏返すことができるかを知るために見る参照軸のメモだけが更新の対象でいいなんて、どうして想像できる？
参照軸のメモは「何枚裏返すことができたか」の記録として捉え直すことができるんだろうな、きっと。それだけわかれば十分だということの理解はまだ。
更新軸の更新部分に当たる１行を削除してみたが AC のまま。たしかに参照軸のメモだけ更新していれば十分みたいだ。
「ある座標より後ろは何枚裏返せたかの記録がまだない」というのが、参照軸のメモから読み取るべきもうひとつの情報であり、これは変数 ii の意味とほぼ同じ。だから十分。
最終更新: 2020-10-09T18:36+0900
精進ですよ。今日*こういうものを読んだ。
「【Python】平衡二分木が必要な時に代わりに何とかするテク【競プロ】 - Qiita
」
この前の日記(20200907p01)で散々 TLE に苦しめられた問題も、C++ なら変数 r を map に、変数 nmin を multiset にすることで、ある範囲のキーを二分探索で検索することも、小さい方からキーを取り出すことも、STL 任せで妥当な時間で行える。適当に速くて短い提出を選んだけどこんな感じ>「提出 #16578878」。トリックは必要ない。
Qiita の記事で題材にされているのが今日の E 問題 Roadwork で、記事をよく理解するためにまず解きたいと思った。
とってもくやしい。
最悪の場合に 200k 要素の配列に 200k 回書き込みを行うのが良くないのかなと思う。掛けて 40G×単位サイズの書き込み量。あ、これはやべーわ。
遅延更新と区間更新が可能なセグメントツリーがあればこのアホな書き込み量はなんとかなる気がするなあ。
ループの中でがっつり二分探索して配列のスプライシングをしても通るあたり、この前の F 問題(前掲)より易しい。
二分探索がしたい、線形よりましな時間で挿入がしたい、というときに平衡二分探索木が欲しくなるんだよね。
プライオリティキューを実装するときも、最大(最小)値を得るだけでなく、整列済みのキューにアクセスして操作したいときがある。でも内部構造がヒープだからできない。std::multiset とは違う。
２本目のキューに削除済みとマークした要素を入れておくの頭いい(Qiita の記事)。二分探索はできないけど、一度放り込んだ値を後から取り消したいときが、たしかに以前あった。
Ruby のバージョンが違うので一概に比較できないけど、他の AC はどれもヒープを使用していて 1000 ms 以上かかっているところが共通している。配列のスプライスよりヒープの方が賢いよね。
でもスクリプトで手の込んだことをするよりインタープリタに丸投げした方が速いこともある。Python は汎用スクリプト言語でありながらそういうバッチファイル的、グルー言語的なあり方も板についている。
たとえば、ダイクストラ法、ワーシャルフロイド法などのアルゴリズムが名前で利用できる。ヒープ構造もある。二分探索も、比較式をブロックで与えられる汎用性が Ruby にはあるが、それが遅さに繋がってしまう。実は lower_bound, upper_bound だけでほぼ足りる。オブジェクトの形が不定だとしても、key 配列と value 配列を持てば解決する。
Ruby に範囲を指定する Array#fill があるのを、しかも古くからあるのを知ったときは嬉しかったし、同時に自分の不明も明らかになった。Ruby は汎用スクリプト言語だからループやイテレータを使って Array#fill 相当の処理は自在に書ける。書いてきた。でも書かずに fill を１回だけ呼び出すのが賢い(が、実は Ruby で実装されています、という可能性もなくはない)。
* 日記を書いている今日は10日。
最終更新: 2021-03-12T19:59+0900
まだ AC してない。(←その後 AC)
前回の日記(20200905p01)で解いた問題と構造は同じ。一番大きな違いはグリッドの大きさで、こちらは制約上の上限が 200000×200000 だから１マスずつの処理では間に合わない。
そこは何とかなって今は上限20万回のループの中で、上限20万要素からの二分探索が２回と、上限20万要素からの最小値検索を１回行っている。配列からの最小値検索が線形時間なのが明らかにまずいんだよなあ。実はループの中で配列のスプライシングをやってるのもまずくて、まずいのが２つ組み合わさって手がつけられないんだなあ。
問題のイメージが掴めてきた(今です)。H 枚の板が上から順にやや右下がりで設置されていて、最上段では横一列に並んだ W 個の蛇口から水が流れている。k 段目で注目すべきは水が落下している位置(複数)と、そこに流れ込む水流のうち落下点に最も近い蛇口がどれか。蛇口と落下点を結ぶ線はどれも交わらない。
蛇口と落下点の距離が最小となるものを効率的に見つけるデータ構造がわからんのだよなあ。
あ、TLE が２つ減ったのは nmin, rmin の導入効果。「蛇口と落下点の距離」ごとに数を数えておいて、数がゼロではない距離を小さい順に検索する。距離は増加する一方だから検索範囲は狭まっていく。
今回のポイントは r を可変長から固定長にしたこと。可変長のときの r のサイズは W から減っていく一方だったのだけど、固定長だと最初から最後まで W(+1)。それでどうして速くなるのか。
r の中身について。これまでは落下点と落下点までの横移動コストを記録していた。今回は落下点は(固定長)配列の添字となり、配列の中身に蛇口の位置を記録した。落下点までの移動コストは計算で求まる。
ここでトリック。落下点と蛇口の位置関係は「蛇口<=落下点」で決まってるので、「添字<中身」の場合を、落下点を見落とさずに配列のスキャンを安全にスキップするための情報とした。
Ruby で提出してると AtCoder Problems で確認できる Shortest Code の数がいつの間にか増えている現象がある。この提出が(いまのところ)そうだし、巨大企業(20200607p01)もそう。
AC 一番乗りである。C++ は甘え。まあ、Python は普通に AC がいくつもあるんだけど>「Python によるすべての提出」
見事なまでに変わらず。スキップ情報を UnionFind と同じように深さ優先探索で貪欲に求めて書き込むようにしても、やっぱり変わらないだろうなと思ってる。
最終更新: 2020-12-01T21:25+0900
今週は ABC がないようなので精進である。D 問題が「コンテスト時間中には解けなかった」ので E 問題は問題文を読みさえしなかった。
一行ずつ左から処理するにあたり保持するデータを vs = [0]*4 と定めたあとは、特に詰まるところはなかった。つまりそこで詰まったということであり、一番のお楽しみポイントだったということ。あるマスにおける状態と、状態から状態への遷移が、４要素の配列でまかなえることの発見が。
今のところ２番目の提出より倍くらい速いみたい。だけど書き方による違いかもしれないね。
この人の名前は AtCoder を初めて日記に書いた 20190907 のこの部分(20190907p01.05)で初めて目にした。このときも Python で一、二を争うくらい速くて、同じくらい速い他の複数の提出から参考にしたと参照されていた。
参考にできるところがあるだろうか。
自分のスクリプトで気になっているのが r0[c] = vs.max と書いた部分で、長さ 4 の vs 配列のうち 1,2,3 番目は基本的に昇順ソート済みなのだけど、0 番目にイレギュラーが飛び込んでくるせいで vs[3] や vs[-1] とは書けずに vs.max と(４要素とはいえ)配列を走査するほかなくなっている。
up = dp[i - 1][j][3] for w in range(4): dp[i][j][w] = max(dp[i][j - 1][w], up)
上のように、隣の行から値を引っぱってくるときに最大４要素を更新すればすべてソート済みであるとして末尾の要素を最大値として取り出すことができるんだけど……
もうわからぬ。
違いは入力 RCV を配列に記録するかハッシュテーブルに記録するかだけ。速くてメモリ食いが配列。遅い方がハッシュテーブル。要素数が少ないときはメモリ食いなのもハッシュテーブルの方なのであって、(メモリと GC が気にならない限り)いつでも配列を使っていきたいんだけど、この問題について言えば、R×C に比べて K がかなり少ないみたい。制約が「1 ≤ K ≤ min(2×10^5, R×C)」だから、最悪の場合が 900 万になるか 20 万になるかという違い。
ところで、いくつか見た感想なんだけど、作業配列は C+4 要素で十分だと思うんですよ。C×4 でも C×4×2 でもなく。入力を記録する R×C サイズの配列の前では霞んでしまう違いだけども、numpy の場合のパフォーマンス特性はわからないけども、要素の更新量は確実に減る。
Python で一番速い提出 #16084621 を読んだ。コンパイル済みのバイナリを書き出して実行するなら Python である理由がないじゃん、と思ったんだけど、元になった Python のソースをちゃんと読めるようにしてくれている。コンパイル前のソースが Python なのだった。
長さ C の作業配列が昇順ソート済みだという特性が活用できていなかったことがわかったので、それを踏まえたコードに。あまり速くはならず。結局 R×C 回配列を更新するところは変わりがないから。
配列を昇順ソート済みにするための書き込みを省いて、配列の重複のない範囲から最大値を抽出するだけにすれば良くなると思った。倍遅くなってメモリ消費も激増した。むしろ逆で、予想外のメモリ消費がスローダウンを招いた？ Array#[] か Array#max に何かある？
vs[0] = [vs[0],r0[c0..c].max].max # r0 に関わらない処理 r0[c] = vs.max
だったものを
vs[0] = [vs[0],r0[(c0..c).max_by{|i|r0[i]}]].max
# r0 に関わらない処理
r0[c] = vs.max
に書き換えたところ、１つ前の異常なメモリ消費、異常な実行時間だったものが、２つ前よりメモリも時間もやや悪いという、予想の範囲内の結果に収まった。
いや、悪くなってるのはがっかりなんだけど、１つ前の悪くなり方はやはり尋常じゃなかった。配列に最大値を聞くのではなく、添字の範囲を使って配列の最大値を求めるという回りくどいやり方より遙かに遅かったのだから。
素直なやり方で予測可能な結果が出るなら速かったりしないかなあ。
困ったときのセグメントツリー。もう３回目の実装なので空で書いてバグも無し(でも一応内部データを目視するテストはした)(１回目と２回目は空で書いてバグだらけ)。メモリ参照の局所性なんて関係ないハードウェアから遠い言語でできる悪あがき。今のところのベスト。こんな作業ってアルゴリズムひとつで桁違いの差をつけて置いて行かれる類のものだ。楽しくはあるけどこれで終わり。
@l の利用場所すべてで @l+1 って書いてるから @l の定義から -1 を削っておけば良かった。
* コンパイル済みのバイナリ展開とか。