このメソッドは、たとえば rb_ary_replace において、配列のスナップショットがとられて、それから変更が加えられたかどうかのチェックに使われる。スナップショットは安いがスナップショットに変更を加えたときにはコピーのコストが発生する。pop, shift を呼ぶかぎりにおいては配列の共有は維持される。」みたいな。■Array#dup の実体がどれだかちょっと曖昧だけど、配列の全体なり部分なりを共有してコピーを先送りする仕組みがあるのは間違いない。
最終更新: 2020-12-08T16:28+0900
ARC 級の企業コンであることがわかりやすい表記になった。企業コンだけどいつもの ARC と同じ気構えで挑戦してもいいことがわかりやすい表記になった。
鹿島の名前はブルーバックスの『図解 超高層ビルのしくみ 建設から解体までの全技術』の編者としてと２冊の SD 選書『近代建築の失敗(著：ピーター ブレイク)』『建物のあいだのアクティビティ(著：ヤン ゲール)』の出版社(鹿島出版会)としてだけ目にしたことがある。ジャンルが同じだから関連があるのでは？
題意を満たすような数のうち脳死で求められるものはすべての数の積+1なんだけど、答えに制約があって N 以上 10^{13} 以下のものを出力しなさいと。
2 から N の数を素因数分解してマージする。素因数がそれぞれいくつあれば 2 から N の数を表現するのに足りるのか。16 なら 2 が 4 つ必要だし、27 なら 3 が 3 つ必要。6 や 18 など複数の素因数を持つ数はとくに考えなくていいかな。
ひょっとして求めたものを最小公倍数と呼ぶのだろうか。Integer#prime? なんて便利メソッドを使ってごにょごにょするくらいなら Integer#lcm を使うのが直接的だったんだろうか。
入力例１の解説を注意深く読めばわかるはずですが、注意すべき点があります。110 を 100 個連結した文字列の中に、110110 という部分文字列は 99 個見つけることができます。決して 50 個ではありません。
この勘違いを正すのに多大な時間を要した。難しい問題ではないとわかるのに答えが全然合わなくて、神経衰弱になりそうだった。
とりあえず答えは出た。
前回より悪くて(20201202p01.04)、３問目にして 20 分しか時間が残っていなかったけど、考えるだけ考えた。
TLE です。メモリの使用量に比例した時間がかかっているような雰囲気。testcase_10.txt は提出によっては TLE にならないことがあり、TLE といえども 22xx ms ではなく 20xx ms であるあたりちょうどボーダーライン上のケースだといえる。そのメモリ使用量が 560 MB。その他の TLE は 570 MB から 632 MB のメモリを使用している。全然ダメって感じではなくて何割か改善したら AC になりそうな期待が、ないかなあ。
特に頭の悪いことをしている部分があるとは思わないんだけど、だからこそ、根本から発想の転換が必要だと言われたら困るなあ。
大量のメモリって、前半の操作列の列挙部分で使ってるのかなあ。見え見えのダメケースを前半部分で拒絶するべきなのかなあ。さっき書いた「同じ操作を要求する３つ目の数があれば、それも即 NG。
」とか、今考えたけど「i,i+1 という操作と i+1,i という操作を要求する２数があれば、操作列のマージが不可能なので NG。」とか。
前半部分の列挙について考えていると、後半部分のキューが不要にできそうな気がしてくるなあ。問題の制約って想像よりかなり厳しくて、可能なケースが限られるし、可能な操作列もいくつか考えられる中から一番簡単なものを出力するのに手間はかからなそう。
つまり、数列に対応した(※)配列に右向き左向きをメモして、山と谷があって、高いところ(流れの発するところ)から低いところ(流れの集まるところ)へ向かってテキトーな順番で列挙するだけなのではないかという……。
※数に対応させるのか数と数の間に対応させるのかで迷ってコードにならない。今は「間」かなという気がしている。
とりとめなくいろいろ書いたけど、結局、前半部で見え見えのダメケースを拒絶して AC になった。
もっと鮮やかに解けるはずなんだけど、当面のモチベーションは消えてしまった。
最終更新: 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-01-05T18:27+0900
やっとである。2012年と2015年と2017年に SSD 化の思惑を書いてるけど(20121112、20150812p01)、今や2020年の末である。500GBで6500円である。
2007年に買ったHDDが丸13年間もった。いや、実はもっていない。最近になって不良セクタが見つかって名前も知らないファイルがいくつかロストしたのだけど、ケーブルを抜き差しして問題はなかったことにしていた。それから、ちょくちょくプログラムが一時的に停止するような状況が続いていて、IO 待ちなのかなと。ディスクがお隠れになってるのかなと。ファイルバックアップが正常に終了することが珍しくなったし、３回ほど 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 のインストールはした。総容量の４分の１しか埋まっていないしデータディスクは別にあるからここから大きく増えることもない。空き容量に任せてどうとでもなるんじゃないかな(なったらいいな)。
最終更新: 2020-12-08T00:48+0900
４月に「多重代入は遅くて時々評価順が難しい」と書いたけど、さらに難しいケースを考えた。クイズです。
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 の結果を確認してから予想してカンマを付けたら予想通りの結果になったので驚きはないけど、やっぱり普通の代入とは違うんだなあと、それが遅くなる理由かなあと、思いました。
ゴルファーしかこんなコードを書こうとはしない？ その通り。
最終更新: 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 配列をソートするだけ。二択による手戻りを最小限にするために、選択肢の優劣が明らかで覆りにくいものを最初に選ぶようにした」なんてぬるいやり方よりずっと突き詰めている。すごいなあ。