最終更新: 2020-10-18T20:31+0900
D 問題をしばらく考えて、
完全に内 = lambda{|n,a|
next (1+(n-a).abs).pow(2,M)
}
はみだし = lambda{|n,a,y|
n,a = a,n if n < a
y = a-1 if a-1 < y
next [完全に内[n+y,a]-完全に内[n,a],0].max
}
みたいな関数を書いたりしていたんだけど、ここから詰め切れる見通しが立たなかったので E 問題に手を出した。
方針はすぐに決まった。逆に考える。照明の置き方が 2^k 通りを網羅しているのだから、照明の置き方を考える必要がない。あるマスを照らす照明の置き場所が何か所あるかを数えることにする。
もちろんグリッドを１マスずつ移動しながら４方向に探索を進めるようでは TLE を免れない。N の上限が 2000 の時に 2N^3 マスの走査は認められない。
lambda P が４方向の探索を省力化する工夫なんだけど、２回の P の合計が後半の N^2 のループと同じくらいの重さであり、N^2 の上限が 400 万だということはループの中身がごく簡単な処理でなければ Ruby は１秒２秒で終了しないので、N^2 ×２の結果は TLE だった。
TLE の山を見てわかる通り、Ruby にとってこれは実装をがんばる問題らしい。そうとわかれば考えるより先に手を動かすのみ。
構造はほとんど同じ。lambda P の代わりの lambda F が４、５倍速いおかげで AC になった模様。スクリプト言語は自分で書いたスクリプトとランタイムライブラリの処理速度に雲泥の差があるので、プリミティブな処理を自分で書かずにいかに丸投げするかが肝要。
それと、２の冪乗を含む掛け算は展開すると一部がループの中身に関わらない定数になって外に出せる。２のＫ乗を１回だけ計算しておけば、ループの中の２の累乗計算は１回だけでいい。もちろんその計算結果は２回目３回目に備えてメモしている。
最終更新: 2020-10-17T17:20+0900
C 問題が解けなくて大爆死した回の ABC。「時間内に B 問題までしか解けなかったので今日の日記は C 問題」。F 問題が解けたら D と E も解けたつもりでいいんじゃないかな？
どういうデータであればクエリに答えが出せるか、どういうデータ構造であればひとつひとつのクエリに妥当な時間で答えが出せるか、とっても考えた。
「LOC (last occurrence of colors)」とか「QIR (q in range)」といった名前をとっかかりに部分的に形を作っていった結果、移動する終点に合わせて始点用のデータを(事前に用意するのではなく)継続的に発展させていくやり方に落ち着いていた。
色の列を空間としてではなく時間として処理すること*が振り返ってみての転換点。意識してではなく手探りで進めるなかでの変化だったけど。
でも TLE。ソート列やハッシュ表といった素朴な構造ではダメみたいだ。
BIT を持ち出しても TLE とは恐れ入りました。ソースコードが長くなるのが仰々しくて嫌だとか言っていられない。
TLE の山と AC 提出の実行時間を見るに、Ruby にとってこれは実装をがんばる問題らしい。そうとわかれば(略)。
配列と BIT に余分な要素を付け加えて単項マイナス演算子と引き算の数を減らしたり、配列の初期値を工夫してループの中の if を取り除いたり、1-origin な入力値を 0-origin に加工するのをやめたり、i-=i&-i を i&=i-1 に代えて演算子を１つ減らしたり、といった泥臭い改善の成果で AC。
こういう脳筋的努力は考察不足の可能性がちらつくと身が入らないのだけど、その心配はなさそうなので心置きなく。
これが Ruby で一番速い(しかも Ruby で一番早い AC でもある)。速さの秘密はよくわからない。クラスやメソッドなしですべてが一体だからだろうか。 初めて見たのだけど BIT の初期化をするこの行……
b = (0..n).map{|x|x&-x}
BIT 実装のキーでもある LSB を蓄えるこれは公差１の等差数列を初期数列にしようとすると現れる。蟻本の図を見ていたのだけど、LSB は内部配列の要素が分担する重みに対応している。倍率(公差)は好きに決めたらいいだろう。
BIT の初期化が多少複雑になっても実行時間でペイするのは変数 u の存在がある。自分の提出で答えを設定する式は Ans[q] = r-l+1-Dup[N-l] (変数 Dup が BIT) だけど、BIT の初期値の工夫により -l が消せても +1 も N-l も残る。そもそも BIT を使用する向きが違っているのだ。BIT から２回値を参照するのを嫌って自分は向きを決めたけど(※BIT の操作が一番のホットスポット)、変数 u があれば参照が１回節約できる。参照が同じ１回なら他の部分の有利が生きるということなのだろう。
* この「空間」と「時間」はユニバーサルな表現ではなかったかもしれない。三次元に囚われた話者の感覚に根差した主観的な意味が込められていて、理解する前提条件になっていると思う。
<script>$(function(){$('var').each(function(){var html=$(this).html().replaceAll('<sub>','_{').replaceAll('</sub>','}');$(this).html('\\('+html+'\\)');});});</script> が「replaceAll is not a function.」というエラーになっている。これ１か所だけに対応するコードは
String.prototype.replaceAll = function(s,r){ return this.split(s).join(r); }; とか、グローバルフラグを付けた正規表現パターンを第１引数にして String.prototype.replace を replaceAll の代わりに呼び出すとか。■atcoder.jp から送られてくるページの埋め込みスクリプトを書き換える方法がわからなかったので、replaceAll 関数を事前にブラウザに定義することにする(userChrome.js)。しょうもないもんに引っかかってるなあと思うけど、おかげで対策が簡単で助かる。今はまだ？■……と思ったら、「@chokudai「さすがにこの対応状況で入れるのは時期尚早でしょ、ってことでちょっと修正コミット入ったっぽい caniuse.com/?search=replac…」最終更新: 2021-01-19T03:44+0900
最近こういう記事を読んだ(20200912p01)。「【Python】平衡二分木が必要な時に代わりに何とかするテク【競プロ】 - Qiita」
その少し前に雰囲気で書こうとしたけど、バランスの取り方に対する理解が雑で完成しなかった(20200604p01.04)。
Ruby の標準添付ライブラリにある SortedSet は内部構造がハッシュテーブルでありキーの順序付けが利用できない。ありていに言えばキーの二分探索をしたいができない。「RBTree ライブラリ (https://rubygems.org/gems/rbtree) が利用可能である場合、内部記憶としてハッシュの代わりに RBTree を使用します
」ということが書いてあるけど、RBTree が利用可能だったことがない。
性能はまったく期待できない。まったく。
注意すれば省メモリにはなるかもしれないけど、出し入れのたびに配列の全長のおよそ半分を右へ左へ動かしていたのでは、他に何も期待できない。
注意を要するのは rotate_l/rotate_r の実装。このとき(20200905p01.07)のように、不必要に膨大なメモリ要求が実行速度まで低下させかねない。
すばらしき(20200912p01.03) Array#fill メソッドにならって、Array#rotate も第２引数以降を使って対象範囲を受け付けたらいい。
内部構造は「社長から始めて決まったやり方で社員を一列に並べていったら、ある社員とその部下と部下の部下以下末端までを一定の連続する範囲で表せるのではないかと考えた。なんのことはないそれって深さ優先探索と同じ順番だったのだけど」(20200607p01.02)と書いたときのものと同じ。
その後の検索で「最小共通祖先 [いかたこのたこつぼ]」というページを見つけて、「LCA」「オイラーツアー」という用語を仕入れている。そんな感じの構造。
ちょっと待て、このドメイン名は……。20200905p01.03 で参照した AtCoder の ikatakos さんと同じでは？
苦労の 70 % くらいは sink と push の２メソッドを見出すところにあった気がする。実装することではなくシグニチャを発見するまでのところに。でも、どういう操作が必要か、どういう操作であれば十分か、実装を始めてデバッグをする過程でしか見つけられないジレンマ。
以前にも似たようなことを書いている。「メソッド名を決めるまでで 9割が終わってる。」 そのときはその後の検索で「最小全域木」「プリム法」「クラスカル法」という用語を仕入れてクラスカル法で再実装しているが、今回はどうか。AVL木とか赤黒木とか知らないよ？>「平衡二分探索木 - Wikipedia」
ソート列における順序と内部配列における添字という、２つの数字を元にして each メソッドが簡略化できそうな気がする。したい。
つまり、現在の向き(行きか帰りか)と次の添字がわかるならスタックがいらなくなる。開始点(最小値の添字)はもうわかっている。
あっ、これ二分探索のためにあらかじめ並べ替えたソート済み配列だ(いま気がついた)。Array#bsearch_index と Array#insert で済むものをよくも難しく書き直したものだ。
メモリブロックの移動を減らすためにギチギチに詰め込まないでルーズに管理しようとしたら、固定長の大きさを持っていて最大値と最小値で特徴付けられる疎な配列(リスト)の入れ子構造に行き当たって、ピボットはいらないな、そうするとこれ木じゃないな、ただの(入れ子になった)ソート列になっちゃったな、と。じゃあ原点に戻ってあれも(並べ方が素直じゃないだけの)ソート列だな、と気がついた次第。
持っていることも忘れていた『[単行本] K. メールホルン, P. サンダース【アルゴリズムとデータ構造―基礎のツールボックス】 シュプリンガー・ジャパン株式会社』をぱらぱらめくってると、(a,b)-木という構造があって、これは木の各ノードが最長で長さ b の子ノード列を持つらしくて、つまりは入れ子になったソート列なんだけど……。
入れ子になったソート済み配列もやっぱり木？
最終更新: 2020-10-14T18:33+0900
ACL は ARC と AGC の中間あたりの位置づけだそうな。この A 問題は 300 点問題。１問目のこれしか解けそうにない。
移動可能な範囲が第Ⅰ象限と第Ⅲ象限に限られるが、移動先の点からさらに移動先を選ぶことができる。双方向に移動可能だし、X と Y の比率を変えながらジグザグに Y=-X 方向に移動することもできる。ともあれこの感じ(「友達の友達は友達」)は UnionFind だと思った。
問題は Union する点の選び方で、見境なく Union したら TLE になった。
見境なくとは言っても、相互に移動可能なら片方向だけを取り扱えば足りるわけで、X 座標の昇順に処理することで X 座標の大きい方から小さい方だけを見るようにしている。X 座標のソートに関してもこの問題で NlogN の時間をかけるのはもったいなくて、線形時間でソート列が手に入る。
Union した中で一番条件のいいものだけ代表として残すようにしたら AC。
よくわからないが UnionFind ではない。キーは12行目の if x + min_y == N+1: だと思う。UnionFind で形作られるグループが持つ幾何学的性質が何かあるのだろうか。
右上がりの対角線上に並ぶ場合と右下がりの対角線上に並ぶ場合を対極として、その中間の状態がうまく考えられない。
X 座標と Y 座標がともに 1..N の順列だということから導かれる論理的必然性を何か見落としてると思う。
検索してたら答えらしきものが見えちゃったんだよな、maspy さんのページは避けてたんだけど他の所で。
頂点をソートして x 座標が小さい順に見ます。
頂点 i と頂点 i+1 について、「y1, …, yi が (N,…, N−i+1) の順列」であるときのみ非連結であり、そうでないとき必ず連結になることがわかります（あとで証明かなんかできたらいいな、、）
「わかります
」(わかりません)
maspy さんの提出に沿って*理解したことをひとつひとつコメントにしながら書いた。完全にそのままではなく、「# ymin の最初期化が必要？」とコメントしたように、ループ中の代入をひとつ省略した。(あ、タイポ。最初期化→再初期化)
しかし、ガイドなしの独力でこの道筋が見つけられるとは思わん。
けんちょん(敬称略)のページにわかりやすい図があった。へー、そうだったのか(まだ見えていなかった)。
「ACL Contest 1 A - Reachable Towns (300 点) - けんちょんの競プロ精進記録」
でも図を見てみたらある意味わかって当然の図ではあった(それがわからなかった)。つまり、x + y = N+1 という X と Y の関係式を見て幾何学的性質について考えたのだし、であれば、その性質は y = -x + N+1 という直線に関わるものでしかありえない。答えを目の前にしながら「わからんなあ」と悩むふりをしていたのだった。下手の考え……。
* ～に沿って、というのはある意味嘘。こちらにゴールがある、という指針だけを手にして考えた結果の式が一致することを確かめただけ。結果が同じなのだから考えたことの軌跡をコメントとして残さなければ完全丸コピと見分けがつかない。コメントを書くのは必然だった。
最終更新: 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 はチューリング完全！」とか言って嬉しくなってしまうような人の気配を感じる。だめだよ野放しにしては(いいぞもっとやれ)。周りに迷惑をかけまいというのは、何でも自分で決めたいという一種のエゴ。生きているかぎり人は誰かに頼るほかない。だから、うまく迷惑をかけあう能力を磨くほうが先」 お坊さんの言葉なので、これで気を楽にして生きやすくなる人もいるのだろうな。あるいは戒めとしても。■「
役人が恐れるのは、人事の影響を受けるのは自分だけではないと思うからです。直属の上司、その上の上司、部下、ひいてはトップの事務次官、大臣らの人事にも響く、と感じています。私もふるさと納税の時、総務省のある先輩から『君だけの問題じゃ済まなくなるからな』と言われました」 どうして忖度してしまうのか、そんなに我が身がかわいいか、と思っていたのだけど、こういう考えもあるのかと初めて知った。自分はこういう風には考えられないし行動を自制できないので、想像できなかった。■偶然にも同じ日の新聞から。「
女性はもう一つ、被害を訴えにくい理由に「チームに迷惑がかかること」を挙げる。「みんなソフトボールで日本一になりたくて大学に来ていた。だから、自分さえ黙っていれば、と」」 ここでも。連帯責任は人を縛るのに有効なのだなあ。