+ で区切ってみる。+ の左にある数字の数と、+ の右にある数字の数がわかれば、主客転倒で + で囲まれた数(式)の寄与がわかる。次に考えるのは、範囲が + で囲まれた内部に端を発して外部に出ていく場合。範囲の内外で数字がちょん切られるので扱う値が変わってくる。だけど範囲の一方の端を決め打ったときの値とその寄与は同様に求められる。範囲の両端が + の内側にある場合の寄与は、これは累積和の問題として単独で D 問題あたりにでもなりそうな難易度の問題。ここまで触れてこなかったけど、+ で囲まれた内部は単独の数字ではなく * で連結された積の場合がある。ここまでと同じように * で分割して左右からの累積和(累積積？)で全体への寄与を求めるんだけど、このあたりからワーキングメモリが枯渇してきて全体を把握するのが困難になる。スラッシングというのかな、何をするにも復帰に時間がかかり、間違えて手戻りが発生し、ちっとも先に進めなくなる。最終的に自分はクラスを使って問題を分離して個別に対処することになった。そうするとあるレベルで考えているときに別のレベルのことを考えずに済む。メソッドを呼んで別のレベルの処理結果を得るだけにすると、大きくなりすぎたスイッチングコストがまるまる節約できる。■提出 #49805072 (G 問題 / AC / 1554 Byte / 825 ms)。サンプルが通りさえすれば他に特に罠はなかったみたいだけど、答えの突き合わせに C++ で提出が早かったこちら(#49712435)を使わせてもらった。実行結果にしか興味はなかったけど、ちらりと覗いてみた solve 関数のシンプルさがすごかったよね。しかしあまりにも最適化されすぎていて、冗長さが足りなくて、自分には書けないし理解できない。そんな簡単そうに解ける問題じゃなかったよ。この構成をあきらめたから、クラス化による問題の整理分割に行ったのだ。■コンテスト成績証。自分のすべての提出。ABCDE の５完でぎりぎりの青パフォ。もう書いたけど、これで上がるのは現在のレートが下振れてるだけなんよ。■G 問題。X で(自賛を)見かけたので探してみたこちらの提出 #49757867 (tanakh さん / Rust)。class を使って構造化するならこのレベルまで突き詰めて抽象を取り出して汎化したいよね、というお手本。あと変数名も適切でかっこいい。累積和のことを prefix sum と呼ぶこともあるみたいなので、今回のように色々な累積和を扱うときにああいう呼び分けはあまりに適切。■■■G 問題。お手本にならって再構成してみた。提出 #50091522 (TLE×7)。残念 TLE。一応、数字の列を１桁ずつ分解してオブジェクトを再帰的に構築するのは避けて、* と + で分解した数字の列からループを回してオブジェクトをひとつだけ作るようにしたんだけど、演算(+ と *)のたびに新しいオブジェクトを作るのがまだまだ負担だったか。前回の提出では + の数だけオブジェクト数が節約できている。あと eval も重い。だけど evall という問題名だから eval したくなるのはしかたないよね。■提出 #50102025 (AC / 1127 Byte / 1759 ms)。通った！ ネックは gsub だった(gets.gsub(/\d+/){ "Num.from_s('#$&')" })。たとえば入力が最長の１メガのとき、演算子と数値が半々なら１桁の数字が 500 キロ個ある。gsub メソッドが入力の 1 を Num.from_s('1') に置き換えるなら、変換後の文字列長は８メガになる。そしてそれを eval する。遅い。Num.from_s メソッドを１文字のローカル変数にキャッシュすることで文字列の全長を抑えたら、だいたい倍くらい速くなって TLE を免れた。ちなみに Object.const_missing を使うことでさらに縮めるアイデアもあった。1 や 123 を N1 や N123 に置き換えるのだ。だけど汚い方法でありながらタイムの改善が微々たるものだったので不採用にした。+ メソッドと * メソッドをそれぞれ +=、*= メソッド相当の実装にするアイデアもあった。これもコードを歪める一方で大した改善ではなかったので不採用。せっかくきれいに再構成しているのだから、ダーティハックはお呼びでない。ABC との一致を確認するだけかと思ったら、空文字列も拡張 A 文字列だって書いてある。じゃあ squeeze した文字列が ABC の中に見つかればいいかと思ったら、A、B、C、AB、BC、ABC は ABC の中に見つかるけど AC が見つからない。これは罠だ、実に示唆的な。■C 問題「Lining Up 2」。配列の添字と値を使ってリストを作る。そしてリストを順番にたどって出力する。■D 問題「Cheating Gomoku Narabe」。今回の実装枠かな。この提出 #49483745 (AC) を見てもらうと、29 行目から 68 行目まで使われていない変数が定義されている。てっきり斜めに揃えるのもありなんだと思っていたら、縦横の並びしか考えないんだって！ 無駄に実装時間を使わされたぜ。判定は尺取りで。■E 問題「Bad Juice」。パリティの問題だってのはわかる。どこにヒントがあるのかも知っている。この日(20170620)の日記からリンクしている論理幼女のページだ。「超難問論理クイズ「2人の幼女とチェス盤の部屋」が本当に難しすぎた - 明日は未来だ！」。コンテスト終了後にじっくり読んで提出したら off-by-one エラー(#49513582)を出してから AC (#49513739) だった。提出時刻を見ると最初に提出するまで 11 分しかかかっていない。コンテスト中の時間のプレッシャーの中で新しい知識を仕入れるところから始めて AC まで持っていくのは無理なんだよなあ。■F 問題「Usual Color Ball Problems」。コンテスト中は E よりこちらに取り組んでいた。時間が厳しそうで難しいデータ構造が必要になるかと思いきや、必要なデータを整理して更新していけば順番に答えが出てくる。これも尺取りか。提出が間に合わなかったのは実装が完了してサンプルを試すときまで違う問題を解いていたことに気がつかなかったから。残り数分で軌道修正はできない。しかし落ち着いて考えれば修正でなんとかなる範囲だった。扱うデータは 箱数 と 球数 と 色ごとの球数。あとは C 数列を見ながらがんばってボールを数える。何色のボールが何箱確保しているかがわかれば、答えるボールの数が決まる。箱数×K とその色のボールの総数のうち小さい方。箱数が M を超えない範囲で尺取りをしながら C 数列をローテーションしながらある色が新しく箱を確保したり手放したりしたときに球数をまとめて増減する。■６完が狙える問題セットで４完は残念が過ぎる。ああ繰り言。Since p/q - a/b < c/d - a/b = 1 / bd」の左辺が 1/bd より小さくなる部分がわからない。いや……わかった。そうかと思ってさっき見たときは比較するものを間違えていた。もういちど 116 ページにある木の図を確認したら、隣接する２つの分数は差が 1/bd になっていた。「なっていた」ではなくいついかなる場合でもそうなることを示して理解しろって話ではあるんだけど、つまりそうなるような操作をしているはずなんだけど、ぼんやりなので操作と結果が繋がりません。■本読みを再開したら、差が 1/bd になることが次の 117 ページに書いて示してあった。■「２つの素数」っていうのは、かつて AtCoder でよく見られた 10**9+7 と、もうひとつは 10**9+9 が使われていた。あれって双子素数だったんだ(知らなかった)。どちらも 10**9 をちょっとだけ超える数だから、掛けると 10**18 を超えるけど 60 ビットは超えないみたい。使い勝手のいい数だ。
C:\Program Files (x86)\Mozilla Firefox\firefox.exe を指している。この PC の Firefox は C:\Program Files\Mozilla Firefox\firefox.exe にあるのでそれはそう。ここからが問題。 (x86) を削除して Enter キーを押した。実行するとやはりリンク先が無効だと出る。なんだよデフォルトプッシュボタンは OK ボタンのはずだろ、と思いながら今度は最後に OK ボタンを押した。実行すると変わらずリンク先が無効と出る。OK ボタンを押す前に適用ボタンを押してみたがやはり無効。修正が通っていないのかと考えてあえて無効なパスに変更してみたら、初めてリンク先が無効だとのメッセージがプロパティダイアログが閉じる前に表示された。これまで普通に OK ボタンや適用ボタンが押せていたのはパスが有効だと確認されていたからだとわかる。では有効だと確認された修正後のパスはどこへ消えてしまうのか。ショートカットファイルの中で URL パラメータを firefox.exe に与えていたのが良くなかったらしい。いやいやいや、ショートカットにコマンドラインパラメータを埋め込むのは何も悪くないよ。そういうパラメータ付きのショートカットファイルを SendTo フォルダに入れておいてもファイルを送ったときにはパラメータが無視されるという罠もかつてはあったけど、Windows Vista までにはパラメータとファイルパスの両方がコマンドラインの一部としてプログラムに供給されるようになっていたよ。■Alt キーでメインメニューにフォーカスが移るけど、矢印キーによるナビゲーションが正気の沙汰ではない。左右キーを押すとサブメニューが開く(それは直観的には上下方向の移動だし、かつては上下キーでそれを行っていた)。上下キーを押すとトップレベルの隣の項目に移動する(それは直観的には左右方向の移動だし、かつては左右キーでそれを行っていた)。メインメニューを完全に無視してすべてがコンテクストメニューと同じ配置だと想定するとそうなるか。■エクスプローラーで一度 Alt キーを押してフォーカスがメニューに移ると、もう一度 Alt を押しても Esc を押してもフォーカスが戻ってこない。Vista なら元の場所に戻ってきたし、見失ったときでも Ctrl+E、↓で必ずリストビューにフォーカスが戻せたけど、タブキー連打以外の方法がまだ見つからない。７以降キーボード軽視が目立つけど、それが加速して止まらない。アクセシビリティはどこにある。自分だって専ら使うのはマウスだけど、マウスしか使えないのとキーボードが併用できるのとでは手間が断然違う。それぞれに使い所がある。だがどんどんキーボードが使えなくなる。■フォルダのプロパティの共有タブで共有設定をしてネットワーク越しに見えてはいるけどアクセスが拒否されて中が見えないとき。パスワード保護共有だって無効なのにアクセスさせてくれないとき。セキュリティタブで Everyone にアクセス権を与えないといけないみたいですよ。共有タブですでにそのように設定していたとしてもね。■右クリックがジャックされていて識別困難な全角１文字サイズのラベルなしアイコンと、アクセスキーのない厳選されたメニュー項目だけが表示されるので、App キーでメニューを出し直すまでがルーティーン。■何もスタートできないという評価を確立している Windows 10 のスタートメニューだけど、11 はさらにひどくしてきた。一番有用なショートカットアイコンがデフォルトで表示されない。追加してもラベルがない。１クリックを要するのが不満だけどラベルが展開できた 10 が優秀に見える。すべてのプログラムを表示するのにも追加の１クリックを要する。そのボタン。まるで現在すべてのプログラムを表示しているかのように見えるプルダウンリストのようなものが右上にあるが、それが切り替えボタンだった(ここの画像)。そういう風に表示を切り替えるときは「タブ」を使えばいいと思うんだよね。ユーザーの意表を突いて何かうれしいことある？ デスクトップ左下の一等地が天気(！)だったからスタートアイコンを左下に移動したけど、たしか Vista よりあとのどれかではもうスタートボタンが左下方向に無限の大きさを持ってはいなかったのだったか。もう一等地ではなかったかもしれない。■ノート PC に外部モニタをつないで蓋を閉じたらスリープしてしまって外部モニタに何も映らない。Web を検索してここにあると示されている設定項目がちょうど抜けている。やっと見つけた正解はスタートメニューで「cont」と入力するとコントロールパネルが見つかるので……というものだった。■スリープしない設定にしているのに翌朝になるとマウスやキーボードに反応しなくて電源ボタンを押す必要があるという。これも正解はスタートメニューで「cont」だった。そこには「休止状態にするまでの時間」という設定アプリにはない設定があって、そこに有限の時間が設定されていたのが原因だった。確かにスリープはしていませんでしたけどね。■あるプログラムで F1 キーが効かないことがあって困ってしまったが、デスクトップで F1 を押して Edge が出てきたあとでは効くようになっていた。よくわからない。■ここまでが一週間以内に起こったこと。もうね、すんごい。すべての Windows ユーザーの生産性を下げることに全身全霊を傾けているとしか思えない。過去を断ち切って破壊的な変更を企てているけど、破壊するばかりで秩序をもってデザインされたユーザーエクスペリエンスがどこにもない。未完成のがらくたで覆い尽くされていて無限に時間を奪われる。これが自分の PC ではないから私は平静です。# のマスでグループを作って、. のマスがいくつの異なるグループを連結してその結果連結成分がいくつになるかを数える。実装していて気がついたけど、. のマスが新たな孤立グループになることもある。期待値を求める式に難しいところはない。すべての . マスについて、連結成分の数を数えて合計し、. マスの数で割る。■F 問題「Christmas Present 2」。DP をしたいけど線形時間で解けと制約がいっている。どうしましょう。いったん時間を忘れると、ある子供のところに行くにあたり、２通りのルートが考えられる。(プレゼントが１つ以上あるなら)直前の位置から直行して手持ちのプレゼントを１つ減らす。もしくは、サンタさんの家に寄って K 個のプレゼントを手にしてから来て、K-1 個にプレゼントを減らす。K+1 要素のデックに移動距離を記録して、shift、push、最小値の取得をすれば答えは出る。しかし TLE が避けられない>提出 #48793891 (TLE)。アイデアはある。K+1 要素の固定長ではなく、スライド最小値の要領で意味のある値だけを記録すればいい。全要素に対して移動距離を加算したり、プレゼント数を減算したりしたくなるのは、ベースとなる値をそれぞれに用意して、それとの差分を記録するようにすればいい(ベースを増減すれば全体が増減する)。提出 #48800858 (AC / 415 Byte / 305 ms)。数字が合わなくて提出が間に合わなかったのだけど、原因は 12 行目の処理を 13-14 行目の後ろに置いていたこと。基準値(d0)を加味した値と基準値からの差分とを比較してはいけない。あーあ、解けてたのになー。■それでも青パフォうれしい。コンテスト成績証。最近不調だったけど、今日のここが定位置だと自認している。次のステップは F 問題を時間内に通すことなんだよな。■F 問題を Ruby で最初に通した人はセグメント木を使っている。最小値を取得するのにセグメント木を使いたくなったのは自分も同じだけど、shift/push をどうするかがわからなくて深追いしなかった。セグメント木で解けるとわかってそういう前提でもう一度考えてみると、N+K 個くらいの要素数でセグメント木を初期化しておいて、参照する K 幅の範囲を１ずつ右にずらしていくという方法で shift/push 操作がまかなえるのではないか。セグメント木をそういう風に使ったことがないので思いつかなかった。……と思ったんだけど、セグメント木を使う２つの提出 #48799502、#48806332 を見てみるとそれぞれ K+2 と N のサイズで初期化している。なんで全部違うんだ。いや、まあ、説明できないことはない。N+K と N は、最初は参照するべき値が K 個ないことを考えると実質同じようなものだし、K 要素の方は、無効になったインデックスに新しい値を詰めるようなリングバッファ的な使い方で理解できる。実際にそういう使い方をしているのかは確かめていないので知らないけども。最終更新: 2024-01-18T16:02+0900
AtCoder の問題ではないが精進。ABCE の４問。
基本的にはカードを順番にスキャンして判断をする。ハッシュ表を使って自分が一番小さいカードである場合、２番目、３番目の場合の３パターンについてカードが３枚揃っているかを確かめる。もしくは、昇順にソートして自分が一番大きいカードであるケースについてカードが揃っているかを確かめる。
N 個の商品がありそれぞれの商品は M 種類の商品カテゴリのどれかに属している。M 日間のセールがあり、セール期間のある一日にはあるひとつのカテゴリの商品が半額になる。Q 人の客がそれぞれある日に訪れ、ある範囲の連続する商品を購入する。さていくら？ Q 個答えよ。
割引がなければ範囲の総和を知るのに累積和を引くだけ。しかしある日にはあるカテゴリの商品が半額になっているので、範囲内にそのカテゴリの商品がいくつあるか知りたい。カテゴリごとに位置を昇順に記録して二分探索をした。
カテゴリごとに累積和を用意しようとすると最悪の場合長さ N の配列が M 個になって、N×M は大きすぎる。更新のあったところだけ記録しようとすると、さっき書いた「カテゴリごとに位置を昇順に記録」する方法になる。
難しいね。いっぱい間違えた。制限時間が１秒とやや厳しめ。
３の倍数の長さ(0,3,6,9,...)の範囲を切り取ってみれば、左端の位置と右端の位置、それと RGBRGB...RGB 文字列との不一致の数からコストがわかる。不一致を単位時間で数えるためには３種類の累積和を用意しておけばいい。すなわち、RGB...RGB..、BRG...BRG..、GBR...GBR.. 文字列と S との不一致を数えた３種類。
ところで、N の上限が 20 万のときに範囲の両端を自由に選ぶと 20 万の２乗(割る２くらい)で間に合いませんね。範囲の左端を総当たりすることにして最善の右端をどうやって決めるかというところで３回 WA を出した。
最初の提出 #48448208 では左端を右に移動するごとに右端を左右に移動させてみる尺取りをした。特定の制約を追加したサブタスクはクリアしたが、N の制約を甘くしただけのサブタスクで一定割合の WA がある。時間は間に合っていて(局地的に)最適な答えを見つけることもできているが、最善の答えをときどき見逃しているということ。
次の提出 #48453131 は不等号にイコールを追加するような微修正で、３割くらい WA の数は減ったけど本質的な誤りは修正されていない。
３番目の提出 #48453143 は３つのサブタスクで２つずつ WA があるという結果で、ほぼ AC と同じ。実はこれまでの２つの提出ではケアしていた、左右どちらかから全ての文字列を削除するケースに対応したコードを削った結果 WA を生んでしまっている。正しい解法を見つけたときにもういらない気がしたんだよなあ。
これが AC。右端を見つけるのにスライド最小値(？)だと思うものを使った。実装はしなかったけど三分探索も検討していた。知っている解法を総当たりして正当性の判断をジャッジに委ねるのはやめようね。
時間に依存したコストをどう扱うか。t=0 となる位置を１から N へのパスの中のどこに置くかでコストが変わる。パスの外に置いても得をしないので考えない。どこに置くのが最善で、どうすれば最善が見つけられるか。
t=0 となる地点をあるパスの中のある辺に置くとする。１がある方のパスに A 個の頂点が、N がある方のパスに B 個の頂点があるとして、A<B なら t=0 の地点を辺上で N の方に近づけるのが良い。A=B なら辺上のどこにあっても同じ。なので、t=0 の地点をどこかの頂点から選んで良い。
t=0 となる頂点を決め打って、１からの最小コストと、N までの最小コストが求まれば良い。１からは順方向に探索し、N からは逆方向に探索すれば、２回の手間で答えが求まる。N 頂点全てを始点にして N 回の探索をすることは時間的に許されない。
提出日の開きを見るとわかるけど、この AC はほぼ一週間がかりだった。
探索は BFS。移動コストが固定値の C と、パスに含まれる頂点数に比例する L×K なので、BFS によって頂点数が単調増加だと想定できると、単純にコストの総和を比較するだけで最短経路が見つけられるし、頂点数に比例したコスト計算もやりやすい。
サンプルの４、５、６あたりの答えがいつまでも合わなくて、ああでもないこうでもないと試行錯誤していた。さっぱり見えていなかったのは AC 提出の 22 行目、頂点 N までのコストを探索する D 関数に与える初期値(DN = D[ヨ[N].group_by{|s,|s}.map{|s,stcs| [s,stcs.map{_3}.min] }.to_h,ヨ])。１からのコストを求める 21 行目(D1 = D[{1=>0},E])と比較すると長さだけ見ても段違いなのがわかる。この違いがさささっと把握できる人はすごすぎると思います。
N から逆向きにコストを計算するのに N の隣接頂点を始点にすればいいとはなかなか……全然わからない。そこにやっと気がついても N とその隣接頂点 V を端点とする辺が複数あるということがまた思い出せない。
たいへんだった。これ予選なんですって。
今３ページくらい E 問題の AC 提出があるんだけど、Ruby の 113 ms が最速だった。おもしろ。ただ、前回の言語アップデートから AtCoder のジャッジは、言語ごとに最初の１ケースだけウォームアップ時間が計測に含まれるみたいな雰囲気があるので(このときの話の関連>20230807)、ワースト１ケースのタイムが特異例である場合の比較に意味はない。
こちらの提出 #48433529 を見ると N×M のループを順方向と逆方向の２回回してるだけに見える。辺を端点ごとにまとめたりもしていない。どういうことなの？ 結局 L[j]*K に (i+1) を掛けるか i を掛けるかというだけの違いだったの？ そうみたい。
頂点数を１減らしてコスト計算する試みはけっこう初期にやっていて、でもたぶん他の部分のバグのせいで答えが合うところまでいかなかった。AC コードがある今同じ方針でやってみるとふつーに、よりシンプルに、答えが出た。なんだよもー。さっき書いた 21、22 行目だけど、こうなった。
D1 = D[1,1,E] DN = D[N,0,ヨ]
そう、これくらい単純に順方向と逆方向の探索ができると思っていたし、実際できるのに、どうして１週間も沼にはまりこむ結果になったのか、謎だ……。
split(/0+/) した結果の 12 文字列について考えた。１の数を c1、２の数を c2 として、[c2,c1-M].max の max を答えにしたら WA だった。たぶん c2+[c1-M,0].max の max を答えにすべきだった。今以て確信はもてない。２パスの別方針の解答をでっちあげたらそちらはミスがなかったらしくそれで AC をとったので。■D 問題「Swapping Puzzle」。制約が５以下とささやかなので階乗の２乗に２乗を掛けても大丈夫。たぶん賢く操作を構成しようとすると、同じ値を持つマスの扱いが問題になりやすいと思う。すべての並べ替えを列挙して盤面が一致しているかを確かめるのが確実。■E 問題「Lucky bag」。解けてないよ。15 15／1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 という入力に対して３秒弱かかるのでは TLE が避けられない。勘違いする人がいるみたいだけど、３秒弱っていうのはコードテストで 2778 ms (＜３秒) かかったって意味だよ。俺は勘違いしてないよ。■F 問題「Random Update Query」。区間適用のセグメント木の香りがします。もっとも、仮にそれが手持ちの道具箱に入っていたとしても関数の合成が書けたわけではない。どこかで読んだけど、Ax+B の A と B を覚えておくだけで合成できたのかな。