最終更新: 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 の意味とほぼ同じ。だから十分。
create table P (N integer primary key); create view NP as with recursive NI(N) as (select * from (values(2) union select N+1 from P order by N+1 desc limit 1) union select NI.N+1 from NI where exists (select * from P where P.N*P.N <= NI.N and NI.N % P.N == 0)) select * from NI order by N desc limit 1; 素数を記録する表 P と、表 P を参照しながら次の素数を返すビュー NP を定義した。このように使う。insert into P select * from NP; 効率は知らない。SQL っぽく無限集合から素数が湧いてくるように定義できれば、limit, offset で自由に素数が取り出せるのだけど……。自然数の無限集合ならできる(with recursive N(N) as (values(1) union all select N+1 from N) select * from N;)。でも素数は？■マンデルブロ集合を描く SQL は想像もつきません。■あっ、SQLite のページにあった！「The following query computes an approximation of the Mandelbrot Set and outputs the result as ASCII-art」 このページからは全体に、「SQL はチューリング完全！」とか言って嬉しくなってしまうような人の気配を感じる。だめだよ野放しにしては(いいぞもっとやれ)。周りに迷惑をかけまいというのは、何でも自分で決めたいという一種のエゴ。生きているかぎり人は誰かに頼るほかない。だから、うまく迷惑をかけあう能力を磨くほうが先」 お坊さんの言葉なので、これで気を楽にして生きやすくなる人もいるのだろうな。あるいは戒めとしても。■「
役人が恐れるのは、人事の影響を受けるのは自分だけではないと思うからです。直属の上司、その上の上司、部下、ひいてはトップの事務次官、大臣らの人事にも響く、と感じています。私もふるさと納税の時、総務省のある先輩から『君だけの問題じゃ済まなくなるからな』と言われました」 どうして忖度してしまうのか、そんなに我が身がかわいいか、と思っていたのだけど、こういう考えもあるのかと初めて知った。自分はこういう風には考えられないし行動を自制できないので、想像できなかった。■偶然にも同じ日の新聞から。「
女性はもう一つ、被害を訴えにくい理由に「チームに迷惑がかかること」を挙げる。「みんなソフトボールで日本一になりたくて大学に来ていた。だから、自分さえ黙っていれば、と」」 ここでも。連帯責任は人を縛るのに有効なのだなあ。
最終更新: 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日。
パソコンや携帯電話でご利用可能な収納機関のホームページより行います。（当行ホームページからはお申込手続きを行うことができません）」「
お申込みの際に、口座番号・口座名義・生年月日およびキャッシュカードの暗証番号等が必要」で、「
本サービスの利用をご希望されないお客さまは、ATMから口座振替受付サービスの利用停止登録にて本サービスの利用停止登録ができます。」 利用停止するまで秘密情報と言えるのが４桁の暗証番号だけという守りの緩さで、「
ご利用可能な収納機関（2020年7月1日現在）※収納機関は順次拡大予定です」に対して過度の信用を付与した状況にあるということだ。その信頼は銀行のものであって俺のものではない。勝手にばらまかないでほしい。■銀行がこれなら au のやり方も当然か>20190122。どっちも願い下げ。そしてドコモ。俺は関わりがないのに存在するだけで有害。資格がないから銀行とは手を切れ。契約者が口座振替で電話代を払えなくなっても俺は関係ない。■デビットカードが関係するらしい。「
利用停止登録をされますと、本サービスとデビットカードの利用を停止します。」 最近 Visa タッチについて調べたけど、この銀行のカードは NFC に対応してない雰囲気だったし、グーグルアカウントなしで Google Pay が使える気もしないので、いらないサービスですね。そんなんで被害に遭いたくねーぞ。■去年携帯電話の回線を au から mineo に替えたので kddi に認めていた口座振替を止めたいと思った。銀行の窓口に問い合わせたのだけど、まあまあ話が通じなかった。よくある話ではないのかも。最終的に用紙はもらえたけど、埋めるの難しそうだった(事務能力ゼロの感想)。■「Web口振受付と即時口振に頼らなければならない新型決済スキームの問題 - novtanの日常」 今は適切な API が整備されていないがゆえの口座振替の乱用状態にあるといっていいのかも。■ドコモのプレスリリースで eKYC をこれから導入するというのがあって、なんぞやと検索してみた。とっても面倒なオンラインでの本人確認手続きらしい。ここでマイナンバーカードに埋め込まれた個人の電子証明書と PIN で本人確認が完了すると、とっても便利なんだけどなあ。無理に5000円くれなくてもカードを作りたくなるんだけどなあ(カードの発行者にこれ以上できることが限られるのはわかる)。マイナンバーカードよりむしろ IC を内蔵したキャッシュカードが利用できるべきなのか。確認したいのは口座の持ち主であることなのだから。■@2020-09-11 今日 KDDI の口座振替を止めてきた。やっぱり窓口でスムーズに進まない。そんなにおかしなことだろうか。電話代を払うために口座振替を申し込む。他所の回線に移ったので口座振替を終了する。普通じゃない？ なぜ解除するのか理由を聞かなければいけないのだと窓口の人が言っていた。そんなにか？ 用紙は前々から準備していたが提出のきっかけはドコモ口座だよ。説明が早くてけっこう。それと肝心の口座振替受付サービスを ATM で止めてきた。必要のないポートは閉じるべし。■ところで、まだ、ドコモ口座の害悪は拭えていない。KDDI は自分が口座振替の手続きをして、そして今日解除したわけだけど、実はこの口座が現在ドコモと結びついていないとも限らないわけだ。今日 ATM で停止するまで「Web口振受付サービス」が有効だったから。何か月ぶり何年ぶりに記帳してこれまでに不正な出金がなかったことは確認したけど、今後ないとも限らない。だから、後顧の憂いを断つためにドコモを締め出してほしい。銀行に間違いがあって、修正の必要があるのだとしたら、その手段のひとつがこれだ。俺はそれで問題ない。
この機能を使うには、リクエストが必要だ。日本ではまだサービスを提供していないが、リクエストは可能になっている。」 リクエストの主体はたぶん電話アプリのユーザー。こういうところきっちりしてるのいいと思います。
最終更新: 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 を削っておけば良かった。
* コンパイル済みのバイナリ展開とか。