人手があればできるから、先に実装したやつが偉い」には異なる読みも可能だと思う。つまり、「誰でもできるなら誰がやったかには意味がない。何に価値があるか。何をやり何をやらないかの判断こそ重要。」 ここでは「実装する」に「価値あるものを～」が含意されている。このような暗黙の前提を忘れて「ただ手を動かす」ことに価値を置くと評価と行動を誤る。貢献ではなく迷惑なだけの功名争いになる。実装能力、判断能力に劣り、誰でもできることが当たり前にできない者は、否応なく前提を無視してただ手を動かすことに価値を置く。そこにしか拠り所がない。だから前提は暗黙のままにしておけない。
このメソッドは、たとえば 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 以上になるから必ずなにがしかの木＋余分な辺になるわけだけど、それがどういう意味を持つのか。最後の頂点だけ選べなくてもいいってだけ？ わからなくなってきた。