直前の要素から連続するのかそうでないのかでコスト計算が変わってくる」ことがわかっていても「
直前の要素を使用しているかをフラグとして持ってあげるとよい」と明示されることが問題解決のヒントになるのだなあ。■提出 #36122711 (TLE×4 / 2191 ms) のち 提出 #36123362 (AC / 1864 ms / 107396 KB)。Ruby によるすべての提出を見ると他の２つの AC 提出と比べてメモリ使用量が５倍以上ある。なんか違うことをやってんだろか。■提出 #36124108 (AC / 1452 ms / 45264 KB)。メモリ使用量の差は Hash か Array かの違いだと思ってまねしてみたけど、時間もメモリもなんか違う。それに AC 提出の片方のメモリ使用量を１桁読み間違っていたこともわかった。18 メガじゃなくて 180 メガだから自分のと大差なかった。だいたい同じことをやってるよ。
オリジン間 HTTP リクエストのリスクの緩和に役立てています」とはどういう皮肉か。■きっかけはこのツイートだったんだけど、「@chokudai AtCoder の API に Access-Control-Allow-Origin など CORS 指定がないのにはなにか理由があるのでしょうか？ これがあれば、有志ウェブサイトが AtCoder の API を叩くためだけに Heroku などに依存する必要がなく、GitHub Pages などでの静的ホスティングが可能になると思うんですが…」、Heroku を利用することで何がどう可能になるのかがまだわかっていない。難しいね。Heroku の無料プランがなくなるんだっけ？ そうすると有志ウェブサイトは何ができる？
t = (A+dx).fdiv dv。これは「追いつく」関係のときに追い越してしまって幅 A の区間から出てしまうタイミングを計算する式。正しくは t = dx.fdiv dv。２つめは 11 行目と 19 行目 でハッシュのキーに 0 を使っているところ。0 と 0.0 をソートしたら結果が不定になった(Ruby 2.7 の場合)。それではハッシュを入る方と出る方の２つに分けた甲斐がない。実数で閉区間は扱いにくいんよ(どうして区間を x+A 未満にしてくれなかったのか)。キーが 0 であれ 0.0 であれ入る方を必ず先に加算しなければいけないのにできていなかった。３つめは「追いつかれる」ケースの処理を忘れていたこと。■提出 #35903826 (AC / 712 Byte / 2942 ms)。これだけミスがあって時間もかかるなら解けた喜びしかない。なんにも惜しくない。■■■精進２。同じ ABC174-E 問題「Booster」(水 diff)。時間中は F 問題にかかりきりで読まなかった。ブースターを使う使わないを総当たりしてダイクストラ法かなと考えたりもしたけど、どうにもはまらない。むしろ巡回セールスマン問題(TSP)だった。■提出 #35902406 (AC / 674 Byte / 1847 ms)。これまで２問くらい TSP(roblem) を解いてるけど久しぶりすぎて忘れていた。ワーシャルフロイド法と同じ見た目をしていることを思い出すのに時間がかかり、何とか書き上げても TLE を２回食らった。以前にタイムを詰めに詰めてこれが決定版と言えるものを作ったんだけど、内容を覚えていないしどの問題かも思い出せなかった(そのときに競ってアイデアを提供してくれたアカウントは覚えている。精進中に見かけた名前を最近またコンテストで見るのは嬉しいものだけど、逆もあって寂しい)。唯一思い出したのが 12 行目の １,０ = (N+M).times.partition{|b| 0<vs[b] }。これで TLE が解消した。big |= 1<<k とか big ^= 1<<k になる。|= や ^= が =、|、^ を使ったシンタックスシュガーだとしたらそれも残念だけど(でもそうだよね？)、1 ビットに作用させるためだけに Bignum の一時インスタンスを作成して、桁数に比例したビット演算をさせているのが(たぶん)、もったいなくて仕方がない。リファレンスを漁るけど flip メソッドが見つからない。bitset みたいな特別な道具としてではなく普通の整数で多倍長のビット演算ができるところが、速度で不利になりがちな Ruby が強みにできるところであるので、機会を逃さず Bignum を酷使していきたいと思っている。これは昨日の日記(20221019)への言及。R[r1] = [c1,c2,c3] Ruby の AC 提出を順番に見ていったけど、独特な例外を除いてほぼそういう、自分と逆の命名なのがおもしろいなと思った。どう読むんだろう。walls_of_row[r1] という感じで、添字の r1 が変数名の row を修飾すると読むのだろうか。それは良い。でもそれを縮めたときに何を残すのか。R[r1] や row[r1] にすると、「行 r1 (のデータ)」しか読み取れない。すべてがワーキングメモリに収まる競プロではそれで十分ではある。しかし……。自分が C[r1] = [c1,c2,c2] という名前を付ける気持ちは、C(olumns) of r1 = c1,c2,c3 というもの。利用するときは cs = C[r1] という形で名前が揃う。名前を揃えるのが「間違ったコードは間違って見えるようにする」原則に沿うと思うからそうしている。行に対して列以外の別次元の情報が１種類か２種類付け加わったときにどうするかを考えてみてもいいと思う。■E 問題「Notebook」。４つの操作を読んでデータがどういう形に育つかを考える。必要なのは末尾の１字。ただし ADD の履歴が必要。DELETE & ADD により分岐して先が分かれる。ノートはポインタ。ノートの存在によりすべての履歴が最後まで参照できなければいけない(データを使い捨てにできない)。自分は逆向きのリンクリストだと思ったけど、Git のデータ構造を連想した人はさすが。2009 年出版で今ではもう古い部分もあるかもだけど根幹は変わらないだろう、『入門 Git』(著：濱野 純(Junio C Hamano))にそういうことも書いてある。Git は名前の変更を追跡していないヒューリスティクスでやっているということは書いてなかったかな。その疑問にはっきり答えてくれたのは GitHub ブログ「コミットはスナップショットであり差分ではない」。コミットがスナップショットなら名前の変更(スナップショット間の関係)のありかが気になるというもの。きちんと答えてくれていた。■F 問題「Hammer 2」は DP かなと思ったけど頭のいいことが思いつかないのでプライオリティキューで素直にシミュレーションをした(そもそも頭の良さは思いつきの良さではないという説)。結果は (TLE×28／AC×74)。まあそうでしょう。後日>20221019■解説放送「パナソニックグループプログラミングコンテスト2022（AtCoder Beginner Contest 273） - YouTube」で E 問題に関連して木構造の Undo/Redo の話題が出ていた。それは TATEditor のことか。履歴の見せ方が難しいだろうなあとは思う。(B+Y)=(A+X)*M の X と M のどちらかを全探索すればいいと読んだ。当日は X だけを全探索する TLE 解を書いていた>提出 #35546704。M を探索すればいいというけれど、いつ M を探索すべきなのか、M の範囲をどこに限れるのか、M を決め打ってから X と Y を求めるプロセスは、どれもよくわからない。■提出 #35646915 (AC / 276 Byte / 108 ms)。M の範囲は Y が B を超えないように選んだつもり。X と Y の求め方については、A*M が B 以上の時は X=0 として Y=B-A*M。A*M が B 未満の時は不足分を X*M で補って B を超えた分が Y とした。答え合わせをしながらたどりついたのであって、ヒントがあってさえよくわからなかった。株式市場では近年、指数に連動した投資手法が拡大。金融機関では個人投資家ら向けに、TOPIX の値動きに連動するように幅広い株式に投資する上場投資信託(ETF)などが売られている。ETF を通して、国際的には緩い基準で選ばれた企業にも資金が入ることになり、投資家からは「企業努力に関わらず投資してもらえるのはいかがなものか」「株価形成にゆがみが出かねない」との指摘が出ていた。」 不可解なのは投資家のコメント。発言者の姿が見えない。最初のコメントからは、努力をしていない企業が投資を受けるのはけしからん、という主張が窺えるけど、自分はそれが無批判に受け入れるべき真理だとは思えないし(「じゃあトップ１社が総取りすべきですか？」「あなた自身の投資先は誰から見ても妥当なものですか？ そもそも妥当さの基準とは？」)、だから他人の投資行動を批判するその投資家の姿と立ち位置が見たくなるが見えない。２番目のコメントはナイーブすぎると思う。歪みのない株価の形成要因ってなんですか。IR 情報ですか。それだけですか。日銀と年金はどうですか。戦争はどちらですか。誰かが選ぶ主要 500 銘柄はいいけど、誰かが選ばずにまとめただけの 2168 銘柄はダメなんですか。(株価を歪める力が低すぎるという意味で)ダメかもしれないけどそれを心配するのは東証であって投資家のあなたではないのではありませんか。指標にする場合でもしない場合でも、自分にとって都合がいいだけの TOPIX が欲しいという主張と違いますか。そういう主張を載せる朝日新聞は誰の代弁者をしているんですか。自分は金融にあるのは利害の調整だけであり「べき論」があるとは思ってないから、投資家の口を借りていながら人間不在で書かれた記事のこの部分は、利害を隠したおためごかしの垂れ流しにしか見えなかった。TOPIX の変更に関係づけて日本経済の利害を書いてくれ。いちプレイヤーはどうでもいい。そこにしか興味がない。
0 で切って 1? だけからなる文字列について考える。長さ K 未満の文字列が 1 を含んでいたら 0 通りだから No。長さ K 以上の複数の文字列が 1 を含んでいたら 0 通りだから No。1 を含む文字列が 0 個のとき、? からなる長さが K より大きな文字列が存在してはならず、長さが K の文字列が１つだけ存在するときに限り答えは Yes。1 を含む長さ K 以上の文字列が 1 個だけあるとき、それの長さが K なら答えは Yes。K より大きいときは 1 の左右端の位置を調べてその幅が K より大きければ No。K ならば Yes。K 未満で左右に ? が存在していれば No。さもなければ Yes。これで全部。複数考えられる場合と１つも考えられない場合をどちらも除外しなければいけないのだけど、意識の切り替えがうまくいかないときに間違えると思う。■地獄の場合分けといえば ABC160-D「Line++」(緑 diff) を思い出す。他に解法がいくつもあって全然場合分け地獄に入り込む理由がないんだけど、時間内に AC にたどりつけない人間が解法を選べるわけもなく>20200701p01。