最終更新: 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 の意味とほぼ同じ。だから十分。
最終更新: 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日。
最終更新: 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 を削っておけば良かった。
* コンパイル済みのバイナリ展開とか。
i <=> 0 で代用できる。メソッドであってほしいものと演算子で十分なものと、なんかちぐはぐだね。■<=> (Spaceship Operator) についてビャーネさんが何か言いたそうにしていたのをどこかで読んだ。Ruby での存在意義はこの１メソッドを定義するだけでクラスを Comparable にできることだと認めてはいる。でも C++ では何を追加しても、互換性を保って追加をする限り、煩雑さを増すことにしかならないだろう。■Uniform Function Call が一番楽しみだな、C++ に導入されるとしたら。シンタックスの統一はテンプレートの適用を拡大するし、メンバ変数を使用しないアクセサリメソッドをグルーピングのためだけにメンバ関数にするような暴挙を阻止できる。最終更新: 2021-10-24T17:45+0900
読んだ眺めた>「競プロerのための群論 (swapと順列と対称群) - little star's memory」
数学の用語で何か抽象的なことを言ってるなーということと、Swaps と Moving Piece の２問(だけじゃないけど)が取り上げられているということはわかった。
Moving Piece は先日解いたので(20200820p01)、以前解けなかった(20191111p01) Swaps も解ける気がした。
もちろん今日も AC に至るまでに WA を出した。それも前回と全く同じ入力に対して同じように誤った答えを出した。前回書いたスクリプトはひとつも参考にしなかったにも関わらず、構成も結果も瓜二つなのは、書いた人間が同じだからですね。同じところに留まっている……。
前回と違ったのはテストケースが利用できたこと>「atcoder_testcases > nikkeiqual_2019 > C」
今回のような Yes/No 問題の場合、間違った方法ででたらめな答えが出ても２分の１の確率で AC になってしまいデバッグが捗らない。そのような場合に(テストケースなしでも)使える手法をひとつ思い付いた。
スクリプトの真ん中に sleep (※引数なしなら永眠)を仕込んで、前半部分の Yes/No 判断に誤りがないかを確かめた。結果は TLE と AC のみだったので、前半部の判断は間違っていない。
予想外の WA (TLE なし)だった。これは後半部の No を sleep に置き換えたものなのだけど、１つも TLE がなかった。１つもないというのは(入力とバグり方がコラボした)偶然の結果なのだけど、偶然でもなんでも無条件 Yes は明らかなバグだ。
こんな感じで TLE(sleep) や RE(ヌルポ、０除算、変数名タイポ)が Yes/No ではない第３、第４の答えとしてデバッグに利用できると思った。こういう(アナーキーな)考え方ってゴルファーが得意としてそうだよね。常識だと思ってそう(違うんですよ)。
わかってみれば些細なことで、思えば去年もインデックスの扱いに確信が持てずに試行錯誤をしていた。どうして B 数列が予めソート済みではないという、そのひと手間で穴にはまるのか、何度でも。
つまり、A 数列の初期配列と B 数列の初期配列。A 数列のソート済み配列と B 数列のソート済み配列。A, B 両者の扱いが対等なこれら４つは脳みその中に居場所が確保されていた。しかし、B 数列の初期配列をソート済みとする、と条件を整えたときに A 数列の初期配列がどうなるか(ソート済みではないし、元の初期配列とも異なる)、という概念が脳みそからすっぽり抜け落ちていた。A, B の対称部分に気持ちを良くして、差異に向ける目がなかった。去年も、今回も(初めは)。
「去年の WA」を完成させたもの。必要以上に慎重だった(見極めが甘く無駄だった)二分探索がないぶん、冒頭の AC 提出より速い。
前回の日記に全部書いてある(あれで全部だった)。ひとつだけ付け加えるなら、「逆の例は、B 数列に重複する値が存在する場合や、B 数列の最小要素以下の要素が A 数列に複数ある場合など」の「など」でごまかした具体例の３つ目。
ソート済みの B 数列に異なる値を持つ隣接要素 B[i] と B[i+1] があって、B[i] < A[k] <= B[i+1] となる A[k] が存在しないときも、A 数列のすべての要素にあるべき位置が存在するとは言えなくなる。(A 数列がソート済みなら B[i] < A[i+1] を確かめるだけでいい)
最終更新: 2021-08-15T23:54+0900
余勢を駆って前回２つの WA であっさり引き下がっていた D 問題に再挑戦した。これも C 問題と同じ 600 点問題。
実は区間の片端に着目した貪欲法で解けるんですよ、というのが目から鱗だったスケジューリング問題そのままだった。どこにそう書いてあったかは忘れた*。
前回の WA 提出 #8424473 を見ると、今と同じことは考えていたことがわかる。C 問題の場合にも言えるけど、そこで結果を分けたものが何か。考えたことを過不足なく言い換えることと、バグなくコードに置き換えること。それができるかどうか。
それはどうやったらできるようになるんですか？ という問いは、どうしてそこで間違えたんですか？ という問いと対になる。わかりませんよ。ワーキングメモリが足りないんじゃね？(テキトー) こういうとき脳筋は手を動かして慣れるしかない。そうすればより少ない脳のリソースで解けるようになったり、型通りの手法で解けるようになったりして、うっかりや見落としで間違えることがなくなる(という期待)。
区間のどちら端に着目するか。冒頭の AC 提出では L のソート順に処理していたが、「前回の WA」では R でソートしていた。それを完成させてみたら、冒頭の AC 提出で使用していた Array#slice! と Array#insert という、配列に対して呼び出すにはやや気が引けるメソッドが、Array#pop と Array#push という配列に相応しいメソッドに置き換わっていた。二分探索も３回から２回に減っている。Swaps の場合もそうだったけど、AC に至りさえするなら部分的には過去の方が優れてるのなんでだろう。
グラフとか最短経路とかコスト０の辺を張るとかわからへんねん。
R でソートするバージョン(#p02.02)。
RC を二分探索し、最初に L かそれより後ろに到達する要素を見つける。より遠くに到達する要素はより高コストなので「最初」を見つける。
見つからない場合は断絶があるということでありパスする。R の昇順に RC に要素を追加しているのであり、今後 [L,R) の区間に到達する辺は現れない。R に到達する辺があとから追加されることはあるが、C が負ではないのでパスで良い。
ひょっとしたらこれも DP (動的計画法) の一種かもしれないけど、わからんけど、自分が頑なに DP の用語を使わないのは、それを言ってもメリットがないから。
一行ずつ左から処理するにあたり保持するデータを vs = [0]*4 と定めたあとは、特に詰まるところはなかった。つまりそこで詰まったということであり、一番のお楽しみポイントだったということ。あるマスにおける状態と、状態から状態への遷移が、４要素の配列でまかなえることの発見が。
これもそう。DP の核心は何を記録して遷移するかであり、それがわからないのに、「あ、これ DP だ」ということを言っても問題が解けない。むしろそれを言うことで何かわかったつもりになることが目眩ましになって問題に集中できない。過去に何度かそういう失敗をして、DP だということは言わないことにした。dp という変数名も自分にとって何も説明していないので使わない。
DP の一語でなく、配る DP、集める DP まで区別できるとまた違うのかもしれないけど、自分はそれらを識別しない。
どちらがどちらと同じと言うかはまあいいや。
速いでそ>「Ruby によるすべての提出」 それ以前に提出が少なすぎる……。
* 蟻本(初版第１刷)の43ページ「区間スケジューリング問題」だった。
最終更新: 2020-08-24T19:08+0900
コンテスト時間中には解けなかった。昨晩から苦しんで夕方に初の AC をもらった>「自分の提出」
バグが２種類あったけど方針は間違ってなかった。
K%A[i].size)の扱い。巡回グループの部分列(スコア数列)の和が最大となるときを考える。部分列の最大長が K%A[i].size 以下となる範囲で和の最大を求めるより、一周少なく回って(A[i].sum １個分のハンディを背負って) K%A[i].size 以上 A[i].size 以下の長さで和の最大を求めた方が得する場合がある。
RE の直接の原因は、最初はゼロ除算を疑ったのだけど、Array#take の引数 k-1 が負になることだった。その値の出所が K%A[i].size。
バグというよりパフォーマンス問題。Array#product で総当たりをしたので、間違いはないが時間がかかりすぎた。バグらせずに時間内に求める方法が最後までわからなかった。
やっとバグ２がとれた。総当たりの方の、間違いではないが時間のかかる方法と答えをつき合わせてデバッグをした。
こうやって振り返ってもさっぱり参考になることが書いてないね。実装が難しかった、しかない。
現在の２番目のタイムが 95 ms。区間の最大値ということでセグメントツリーの使用は一応考えたんだよ。だけどこのときのこれが頭を離れなかった>「追加する要素との大小関係によって、待ち行列の末尾から、永遠に最大要素(最小要素)としての順番が来ない要素を追い出す」。おかげで 77 ms。
理想的にはこんなふうにすっきり鮮やかに解きたいね>提出 #16033967 (581 Byte / 175 ms)
普通に累積和の配列から k 要素を切り出して最大値を取り出してる(ss[_1 + 1, k].max)。回路長の３倍の長さの累積和配列を用意してるのがよくわかっていない工夫か(ss = (1 .. 3*l).each_with_object([0]){|j, o| o << o.last + Cs[lp[j%l]]})。
ss[l] が回路全体のスコアの和。0...l の範囲の１点を始点にして長さ k(+1) の部分列を切り出す。k = mi[K, l + K%l] だから、最大で [l-1+(l+l-1)+1] の要素にアクセスする。長さは 3l 必要。 ma[0, ss[l]] によって回路全体のスコアの和が正か負かの場合分けを省略している。
Array#max を分岐と見ることもできるかもしれないけど、場合分けをしてそれぞれに固有のスペシャルな式を書くより、Array#max, Array#min を含んでいようとも１つの統一された式を書きたい。実に自分好みのスクリプト。「if 文が嫌いである。(20181029)」
そうだそうだ、自分は長さ k の部分列の始点を負のインデックスにすることで仮想的に配列の長さを倍にしたのだった。小賢しい。まあ、それでは長さ 2l にしかならないから、3l が必要な「場合」は配列の加算(a+a)をしている。このやり方をとる限り場合分けを解消できないね。
q,r = 7777.divmod(101) みたいに多重代入で受けると、多重代入が遅いせいで(20200428p01.08.01)密かに期待するパフォーマンスメリットが相殺されてしまう罠がある。最終更新: 2020-09-03T17:14+0900
時間内に B 問題までしか解けなかったので今日の日記は C 問題。AGC の C なら解けないのは残念ながら当然だけど、昨日あったのは ABC で、C 問題は 300 点問題だ。嘆かわしい。
解るような気がしながら解らなくて、でもやっぱり解りそうな気がするという堂々巡りを繰り返すだけで考えがさっぱり焦点を結ばなかった。具体的には 7,77,777,7777,... という数列を規定するルールを、どのように捉えれば解きやすいか考えあぐねていた。
布団の中でも考えていて眠る前に AC が出た。だけどまだ解らない。このプログラムが停止するかどうかさえ自分には不確かだ。
たどり着けるならK回目までにたどり着くので「K回目までにたどり着かなかったら到達不能と判断」でもよかったか
うん、これが解らない。
K の余りをとるなら余りの種類が K 種類しかないのはわかる。同じ余りが出たら以降が循環ルートに入るのもわかる。K+1 回目以降の余りが必ず既出なのもわかる。わからないのは、自分が提出したスクリプトでははっきりとわかる形で K の余りを求めていないところ。たぶん変数 k に配列７の要素( 0 以上 9K 以下の値)を足して 10 で割ったあとの k の値がそれっぽいから、この k の値が既出かどうかをチェックする方法があると思う。
でも問題に用意された入力について言えば、答えが出そうな K からは必ず答えが求まっているようではある。それは必然なのか偶然(出題者の作為)なのか。
他の人の提出を見ると明らかに自分だけ*おかしなことをしている(嬉しい)。え？ 停止条件さえ判れば(※自分には判らない)、数列を順番に K で割るだけでいいの？ (※桁が大きくなりすぎるので余りにだけ注目する必要はある)
たぶんやっていることは実質的に同じで、一方が難読化されているというだけなのだろう。問題の理解がこんがらかっているからスクリプトもそうなる。過去に２回くらい日記に書いてるけど、アホの子は自分で問題を難しくする。(問題の本質、抽象化された実質が理解できないから、無駄や回り道がなくせないという意味)。
「レプユニット数」という概念があるらしい>「[AtCoder] ABC 174 C – Repsept | ヤマカサの競技プログラミング」 そういえば問題名が Repeat でも Respect でもなく Repsept だ(今初めて読んだ)。
この問題の２つの解法というのは、逆元とか割り算を含む式の余りについて理解を深めるチャンスだという気がするんだよね。何か関係がありそう。以前解けなかった問題>「階乗が法外な大きさになるので余りを答える問題。割り算を含む式の余りが求められなかった。」
(別の問題の解説だけど)これも理解の手がかりにできそうな雰囲気。雰囲気しかわからぬ……
公式解説は累積和だね、横一列を1回の掛け算で済ます方法
僕の解法は「単純に2で割れないから逆元を使った難しい解法になる」と言われてた
抽象的に考えすぎて難しいだけでは。11ぐらいの小さい数で試したことがあれば難しくなく思いつけると思う
* この提出はお仲間かな。 https://atcoder.jp/contests/abc174/submissions/15654939
最終更新: 2020-08-15T20:50+0900
コンテスト中に解けなかった(問題文を読むところまでいかなかった)問題に挑戦。
「連結成分」っていうのがわかんないよね、まず。出力例１の解説を読むに、頂点集合が辺で繋がれたいくつの部分に分かれるかを数えるみたい。
L<=[C,P].min && [C,P].max<=R だから、その否定。(追記：これは嘘。実装中に気がついたがこれだと頂点 C が頂点集合に含まれないケースが紛れている)スクリプト化にあたって一番考えたのって、重複組合せの求め方だった。最初 N×N にして間違っていて、仕切りを置く場所を考えるんだったような、と思い出すのに時間がかかった。そして最終的に補集合ではなく目的のものを直接数えられることがわかって無駄になった。
あと、ちょこざいなやり方だとは思うけど、C と P の大小で場合分けをしたくないなと思って符号を利用した>[(c+1)*(p-c),(p-c)*(c-N),].max。あ、カンマが余分。これは「２頂点間の最短パスは短絡辺を通るか通らないかのどちらかである」が最後まで見抜けなかった恨みである。
こうしたら最後の計算で根(c==0)の場合を例外扱いしないで済む。
P[0] = N # 0 を根にする。N は計算のため。
p (0...N).sum{|c|
p = P[c]
[(c+1)*(p-c),(p-c)*(c-N)].max
}
ワンライナーとかわけがわかりません＞＜
あ、これ？ 「閉路が存在しないならば「連結成分の個数 = 頂点数 - 辺の数」が成り立つ。」 木のどの部分を切り取っても木だろうし、木なら頂点数と辺の数は N 対 N-1 に決まってるので、頂点数と辺の数のずれの大きさがそのまま森を構成する木(連結成分)の数というのは、まあ、言われたらそうかもね、という感じ。
言われなきゃわからないし、なんなら、連結なグラフで頂点数と辺の数の比が N 対 N-1 ならそれは木だというのも、最初からなんだか化かされてるような気がしてる。
最終更新: 2020-07-09T19:18+0900
コンテスト中に解けなかった問題に再挑戦。(C 問題まで11分で終わらせてそこで力尽きていた。そんだけ時間を余らせてなぜ解けない？)
距離を求めるのに頂点の分類が必要だったのだけど、分類して組み合わせを網羅して距離を計算することができなかった。
今回は頂点を２次元座標に配置することを思い付いて、そうすると組み合わせの網羅や距離の計算が if 文ではなくデータを中心に構成できたので、解答の提出にまで至った。
N の上限が 2000 だから N×N(=400万)のループは TLE のおそれがあり、実際に 2 秒制限ギリギリだった。提出一覧を見たところ 100 ms は切れないみたいだが 500 ms くらいは普通に切りたい感じ。
というあたりでもうちょっと。
atcoder.jp/contests/abc16… すべてのiをBFSで最短距離出すところまではすぐ思いついたけど分岐する場所の計算がわからなくて敗北した
BFS とは思いもよらなかった。たぶんグリッドでなくほぼ直線だったからだろう。そういう先入観でプランＢが見えなかった。
期待以上に速くなった！ ２桁ms！
すでに書いた通り頂点を４つにクラス分けして、始点４クラス×終点４クラスの場合に距離 k の頂点ペアがいくつになるかを計算した。計算は定数時間なので全体で k(=1..N-1) に比例した時間。
L[n][k] が主な道具。n 頂点で直線を作るときに距離 k の頂点ペアがいくつあるかを返す。
C[n][k] は n 頂点の円に対応する。頂点X,Yを除外する-4,-2 がアドホック。
k=1 の場合は例外。他と同じ式に組み込めなかった。
300 ms 台の人の十分に速くてシンプルな提出を見た>#14717011。長さ N の二重ループだった。ありうる２通りの距離のうち短い方を採用するだけだった。これをコンテスト時間中に書きたかったね。まあ、あとからでも書けなかったんだけど。
「２頂点間の最短パスは短絡辺を通るか通らないかのどちらかである」ということが最後まで見抜けなかったからなんだけど、それでも、何らかの方法で答えにたどり着きたかった。
たぶん Python のこの提出(#11387294)が自分と似た方針で同じようなコード構成だと思う。難しくてよくわからんけど。
最終更新: 2020-07-05T23:55+0900
コンテスト全体については順当に、冴えない結果であった。あまり書くことがないので１つだけ。
他が概ね 1000 ms ほどかけているところ、１つだけおよそ半分の 515 ms で済ませている>提出 #14757268。
ループでは他と同じ式を使ってるんだけど、半分に割って足しているところが鮮やか。足し算の背後にある論理がわかりません。
N/2+1 から N までの数は掛ける２をするだけで N を超えてしまうので、その数自身しか数える必要がない、というあたりかな。ループの中の計算が必要ない。
こんな手の込んだことをしていながら提出時刻も早くて、Ruby の中では５番目なんだよね。一方の自分は、C 問題で脳死の愚直手続きスクリプトを書いていた>提出 #14743690。脳死のまま清書>提出 #14788308。ステートメントを減らそうとしてやりすぎた>提出 #14788890
D 問題にも最初は脳死状態で挑んでいた。こういうスクリプト。
でもサンプル３が親切にも N の上限値で、このやり方では時間がかかりすぎることに気付かせてくれた。さもなくばずぼらと拙速の代償として TLE を１個拝領していたことだろう。
D 問題。問題と格子点の関連がさっぱりわからなかったのだけど、ループでシミュレートしてるΣ計算に N の一般式を与えようとしたときに、Σの中に整数除算があるから、反比例のグラフと軸のあいだの格子点の数に興味があるの？ その前に、k*N/k*N/k を約分したり分解したりはできない？
ところで、この縦に足す方法では、半分から先はどうせ1つしかないのにループを回して一つずつ足してしまう。ここを斜めに足せばループは半分で済む。しかしどうせ斜めに足すなら… 左上までしっかり斜めに足す。そうするとループの回数はルートNのオーダーになる。
画像が見えない(scrapbox も CSS を切らないと読めない)。まだ「斜めに足す
」がわからない。√N のオーダーになるとは他所でも読んだが、わからなかった。
k*(N/k)*(N/k) の、N/k が１になるものだけを特別扱いするのでなく、２になるもの、３になるもの、４、５……で分けると定数係数としてΣの外に出せる(それとΣの区間も変化する)とか、そういう話なんだろうか。いや、どう書いてあるかはざっと読んだんだけど、読んだだけで解れば世話がないわけで……(あとでスクリプトにして確かめよう)。
しかし明らかにもっとすっきり書く方法がありそうなんだよな、っていうかそれはすでに Python スクリプトとして示されてるんだけど、理解できないのです。
自分がやったのはすでに書いた通り、「N/k が１になるものだけを特別扱いするのでなく、２になるもの、３になるもの、４、５……で分けると定数係数としてΣの外に出せる
」ということを利用して、k=1..N のループについて前から計算すると同時にループの反対側にある N/k==k (※)となるケースを計算して両端からループを進めようということ。繰り返し回数は 1,2,3,...,N/3,N/2,N の半分になるはずなんだけど、中間地点がどこにあるのか、全長がいくつになるのか、わかりません。
でもまあ、√N のオーダーになってるみたいだから、N=a*a だとして、1,2,...,a-1,a(=N/a),N/(a-1),...,N/2,N なんでしょう。
m=N/k; n=N/(k-1) なのを利用して 68 ms のスクリプトのループの中の式を s+=N*(N+1)/2; s+=k*m*(m+1) と整理できそうなんだけど、そうするとこれまたどこかで見たような式(と定数)でさらに整理できそうな雰囲気があるんだけど、m と n の関係は通分したり約分したりできる関係ではたぶんないんだよね(答えが合わないから)。
図がわかりやすい。オーダーをちょっとずつ改善していく構成が付いて行きやすい。そして最後に見逃せないこれ>「なお、O(N^1/3)の方法もあるらしいです。
」
格子点のやり方がこのオーダーらしい。さっぱり想像がつかない
じゃあね、せっかくリンクを張って紹介してくれた先(「格子点の数え上げの高速化 - memo」)を読みましょうよ、って話なんだけど、高速化云々より前に格子点がどのように関わってくるのかがまず知りたいよね。
まずここから(わかんない)。
1 から n までの約数の個数の総和（つまり、y=n/x の第一象限内の格子点の個数）は
2 \cdot \left(\sum_{i=1}^{\lfloor{\sqrt{n}}\rfloor} \left\lfloor\frac{n}{i}\right\rfloor\right) - \lfloor{\sqrt{n}}\rfloor^2などを用いて計算することが多く
傾きが既約分数の場合」)
それというのも Python の方には２桁msの提出が１ページ以上もあって、オーダーは変わらないしブレもあるだろうとはいえ、28 ms と 32 ms のスクリプトのあいだには明らかに式の複雑さに差がある。
※ 実行時間昇順で並べたときだけ自分の 32 ms の提出がリストされない。降順だったり提出時刻だったりでソートすれば現れる。消えているときは代わりに他の人の 32 ms の提出が２回リストされている。
32 ms の１つは自分のだが、28 ms は例えばこれ>提出 #14788253。平均タイムからして明らかに速い。
未だ及ばずながらだいぶ迫ったのではないか。
最後に÷４するのにループの中で無駄に×４してるのが気になったので。
これを最適化というのではないか。この問題でしか意味のないループになった。少なくとも自分は式の意味を、途中からは理解していない。
実は最終版の while ループの中身は一番最初の 997 ms の提出とそっくりになっている。戻ってきた。
Ruby で書くとこんな感じ。
N = gets.to_i
p (1..Math.sqrt(N)).sum{|k|
n = N/k
k*n*(n+1)-k*k*k
}
違いを見比べると -k^3 がループの中にあるか外にあるかの差なんだろう。Wikipedia による
と \sum_{i=1}^nk^3 = \left(\frac{n(n+1)}{2}\right)^2 らしい。
k*[n*(n+1)-k*k] からは、何か、意味が読み取れそうな気がするね。数学力があれば見えるんだろうか。数学力があれば意味を保ったまま易々とたどり着けるんだろうか。
ループ後のつじつま合わせの正体が -\sum{k^3} だとわかったので……
N = gets.to_i s,k,n = 0,1,N while k<=n s += k*n*(n+1) k += 1 n = N/k end s -= (k*(k-1)/2)**2 p s
※ 両辺の k は異なる。右辺の k が 1,2,3,... の順で繰り返される k として、それに対応して左辺を満たす k が N,N-1,N-2 の順で発見される。１対１対応ではない。
最終更新: 2020-07-09T19:28+0900
WA(Wrong Answer)の記憶なんてないまま新鮮な気持ちで挑戦したら普通に解けた。過去の提出を見直してみたらまあ、解答の構成がびっくりするほど瓜二つ。
では二者の分かれ目はどこに？
WA の方はすべての人について一度だけ、その友達リストを処理している。AC した方は深さ優先探索で再帰的に処理している。なぜ再帰が必要か？
ある人 A と B が友達で、また C と D が友達であるとする。この時点で２つの友達グループがある。ここで A と C の両方と友達である E さんを処理するときに、A と C と E を繋ぐだけでは不十分で、すでに A や C とグループを作っていた B と D の所属グループまで更新しなければいけない。これをするためには配列を通り一遍に処理するだけではダメで、友達グループを記録した配列を何度もなめなめするか、再帰的に処理をする必要がある。
今ではこういう処理を Union-Find と呼ぶことを知っているし、グループの大小を管理することで書き換え処理が軽減できることも知っている。検索したらこれは序の口で、まだまだ奥が深いらしい。読んでないよ>「素集合データ構造(Union-Find)」「UnionFindTree に関する知見の諸々 - noshi91のメモ」
インタープリタ型言語は基本的に書けば書くほど実行に時間がかかるものだし、一般化して構造化すれば無駄が生じる。多く書いてそれが速いなら、アルゴリズムが優れていることに他ならない。
ところで、つい先月の新しい提出にすごいのがありますね。「Ruby(2.3)によるすべての提出(実行時間昇順)」
tamura2004 さんの提出 #13758236 (AC / 915 Byte / 291 ms / 12292 KB)
def size(a); -@data[find(a)]; end @data ひとつでグループとサイズの両方を記録している。@data[b] = a によって b グループを a グループに併合している。事前の比較により a グループの方が b グループより小さくないことが保証されている。しかし同時に行っている @data[a] += @data[b] の意味がわかりにくい。これは @data のもう一面、大きさを合計している。@data[a] < 0。負になるのはルートに対応する要素の値で、ルートにぶら下がる要素は 0 以上の値で他の要素をポイントしている。@data 変数ひとつであれもこれも済まそうなんて、なんてケチで欲張りなんだ。
コンピュータで処理するものなのだから、現実的制約は無視できない。集合演算と整数の引き算(+α)のコストの差。十分過ぎて必要のない情報にコストをかけてはいけない。
引き合いに出した ARC097 の D 問題の AC 提出は去年の10月のものだった。３月時点ではそれを糧にできていなかったのだな。
さらに言えば ARC097 の D 問題には AC 提出の前に１つ TLE になった提出があったのだけど(#8121130)、TLE の原因がグループを表現するのに集合を使っていたから。３月の提出が TLE なのと同じ理由。まるで成長していない……(それどころか WA まで)。去年の10月は TLE のままで終わらなかったのが偉くて、30分くらいかけてグループの中で一番小さいインデックスにグループを代表させることにしたらしい。それがどうして３月に生きなかったのか……。
しかし今日の日記を書く過程でさらに省メモリかつ高速なスクリプトへの手がかりを見つけられたのはもっけの幸い。わずか２日での進歩である。
tamura2004 さんの提出を参考に。同じ問題に対する#10479576ではなくて、さっき引き合いに出した#13758236の方。
出力形式も変えたけど、ジャッジがスペース区切りと改行区切りを区別しないらしいのは kotatsugame さんの何かの提出で知った。これって kotatsugame さんの記事なんだけど……「AtCoderで実行時間0msを狙う - Qiita」
「どうしても1ケースだけ1msかかってしまう……せや！テストケース特定したろ！
」「ちょっとくらい……探索サボってもバレへんか
」「進む方向を定めるのに、ベクトル(sin(r),cos(r)) (r=0,...,99)を使っています。根拠はないです。
」
「根拠はないです」やあらへんでまったく。ゴルファーでもあるこんな人がジャッジの細かい仕様を知らんはずないんだよなあ。
それに問題を読み直したら「答えを空白区切りで順に出力せよ
」と書いてあって、たしかにスペース区切りの出力例は出力形式の一例に過ぎないといえる。
最終更新: 2020-09-01T19:43+0900
コンテスト本番では問題文を読むところまでたどり着けなかったし、仮に読んでいても TLE は免れなかったろう。
しかし今や蟻本でセグメントツリーについて読んだので何の問題もない。適切なデータ構造を扱えますか、というだけの問題である。それと時間内に実装できますか、という……(BITを使おうとしてた時間を含めて３時間くらいいじくってた)。
内部データサイズが単なる 2N に見えるのが不思議。添字の扱い方はヒープに見えるけど、２の冪乗じゃないと階層が崩れて右が左に左が右になりそうなものだ。さっぱりわからん。
蟻本の著者の一人のスライドを見つけた。
実際には，この実装なら n が 2 の累乗でな くても動作する
値の更新の方はこのままではダメで，同様の 手法で再帰関数で書けば OK
- ただし，配列サイズは MAX_N * 2 - 1 では 足りない – MAX_N * 4 取れば十分
まだわかりません。それに Python による fold 関数とスライドにある query 関数は引数の数が全然違うんだよね。片方は再帰ですらないし。
一方の提出ご本人による記事である。「いわゆる非再帰実装
」「N = 2^n を仮定しない
」 これこれ。ありがたやありがたや。
最終更新: 2020-06-15T23:25+0900
第三回まで過去問をやったけど(20200607p01、20200607p02)、やはり順当に解けるのは K 問題まで。L 問題が自分にとってのチャレンジ。そこまでの問題が漏れなく時間内に解ければ上級認定。今回時間をかけてでもこれが解けたのは、今日たまたま読んでいた蟻本で紹介されていたデータ構造を雰囲気で実装してみたことによる。(この日記は今日書いた>20200602p02.03)
ヒープ構造を使って冗長な情報を削ったら同時に保険がなくなって、雰囲気実装のふんわりした理解の穴が露呈してバグに苦しんだ。AC と AC のあいだに 3WA。
二分木におけるLCA
木の構造が定まっているので、bit演算で計算できる。
こんな感じでうまいことできないかずっと考えていたのだけど、バグが取れてみれば、１つか２つのノードを見るだけでは済まないみたいなのでもとから無理だったっぽい。
他の人(Ruby では２人いる)の提出を見ていたら不備に気がついた。
B,BL = A.map.with_index.to_a,1<<A.size.bit_length H = [nil]*(BL-1) + B + [B[-1]]*(BL-B.size)
こんな感じで配列 A のビット長をもとにしてヒープのサイズを決めてるけど、例えば A のサイズが２のべき乗でヒープの最下段にきっちり収まるとき、なぜか倍のサイズを確保してしまってる。
例えば A.size == 8 のとき、ヒープサイズは 8+4+2+1 の 15 で十分だけど、上の BL の定義ではヒープ H のサイズが 31 になる。無駄のない定義は BL=1<<(A.size-1).bit_length。-1 がキモ。
これはうまくないみたい。今回は値の更新がなかったけど、更新を遅延させて値の取得に合わせて伝播させるためには、上から下っていかないといけない。
更新を遅延させるとか、考えてもみなかった。
それに最下段の要素に直接アクセスできたのは今回の問題に限った特殊条件ではある。範囲が配列の添字、０から連続する離散値だっていう。
必要になるまで考えないでいいことは考えない方針で。
上に上るにしろ下に下るにしろ、自分が左右どちらの枝にいるかは考える必要がなくて、右ないし左に移動してから隣の階層に移動するだけで次の判断がつく。
右(左)に移動するとは、兄弟もしくは従兄弟ノードに移動するということ。最初に右の枝にいたか左の枝にいたか、そして右に移動したか左に移動したかで関係が違ってくるが、気にする必要がない。そのうえで上の階層に移動するとは、元のノードから見て親か伯叔父ノードに移動するということ。いとこの親ならおじさんである。
具体的なコードは次で。
| 提出 | コード長 | タイム | メモリ |
|---|---|---|---|
| とりあえず AC | 660 Byte | 1293 ms | 93824 KB |
| ちょっときれいに AC | 740 Byte | 870 ms | 61964 KB |
| 十分に詰めて AC | 707 Byte | 700 ms | 51032 KB |
単純にタイムを縮めるだけなら他に優れた解法がある。これは次にこのデータ構造を使う準備みたいなもの。
すっごく読みやすいね。実は答えを保持するスタックに push/pop するだけで答えになるらしい。しかも速い。
自分の最初の提出(TLE)がこれで、#14163100、素朴なやり方では無理なんだと思っていたのだけど、どういう違いが AC(速い) と TLE を分けたのか。
もっともらしいことを想像で書こうとしたのだけどよく解らなくなった。バグで無限ループしてるという方が納得できる。だって K の大小や D の大小に応じて、最小値を求める区間や回数はしっかり反比例してる。たしかに重たいケースで TLE になってるみたいだけど、他のケースの10倍20倍も時間がかかるというのは解せない。
D が小さくて A 数列がほぼ昇順に並んでるときに、N の上限の20万要素ちかい範囲から何度も最小値を選ばされる地獄を見ることがあるのか。いやあ、そんな意地悪な入力を与える人はいないと信じるよ。
♭ nishio「循環ルートに入る」＝「kの1の位が偶数か5」ということみたいです、追記しました。
♭ ds14050お知らせありがとうございます。しかも代わりに考えていただいて^^。 循環する場合に「B-AはKの倍数」からの「..