/ 最近 .rdf 追記 設定 本棚

脳log[AtCoder: 2020-10-18~]



2020年10月18日 (日)

最終更新: 2020-10-27T18:44+0900

[AtCoder] AtCoder Beginner Contest 180/D,E

 D 問題 Takahashi Unevolved

数弱さんには頭が痛い問題だった。

 提出 #17475334 (WA)
 提出 #17517315 (AC)

経験値1を加算して増える強さを A と B で比較する。

強さが増加するに従って必ず A を掛けた方が B を足すよりも強さの増加量が増える。(A が1より大きい整数だから)

対数を使って強さの増加量が逆転する境目を求めたのだけど、それは A,B,X の関数であって、Y による制限が考慮されない。

WA だった提出では Y を考慮して上限を定めていたのだけど、境目が負になる場合を考慮して下限を 0 に規正することができていなかった。

コンテストが終わってから問題を明らかにするテストケースが見つかってデバッグができたが、遅すぎた。


1018 という制約の大きさにびびって対数を持ち出したけど、A が最小の 2 であっても 1018 <= 260 だから、A を使用した方が得する境目は高々 60 なのだった。頭痛の種を自分で作り出していた。

いや違う。比較対象は上限が 109 の B だから、境目の上限は高々 30 か 29 だ。

どちらにしろ簡単なループで求められたのだな。同じ手は食わない>#17612685 (翌週の ARC にて)

 E 問題 Traveling Salesman among Aerial Cities

コンテストが終わってから問題文を読んだ。イメージが湧きやすくていい問題名だと思う>Aerial。

 提出 #17485932 (TLE×13 / AC×13)

2**17*17*17(=約3800万)回のループであり、サンプルですら TLE になるのがわかっていたが、ビギナーはワーシャルフロイド法が書けただけで満足なのです。これ以上は解らないのです。

以前解けなかった問題で参考にした提出。「後半はワーシャル-フロイド法に見える3重ループ。ただし街と街を結ぶ中継地点(一番外側のループ)は街ではなく経由地のリスト」。これをチラ見しながら書いた。

 提出 #17516238 (AC / 1933 ms)

ダイクストラ法でコスト順に点を繋いでも時間がかかりすぎるのは確かめていた。問題に合わせたチューニングが何かできないか、そもそも総当たりのワーシャルフロイド法で可能なチューニングがあるのだろうか、と考えていたが思い付かない。コードを眺めてみよう。

  1. 一番内側のループで変化しない配列参照をループの外に出せばちょっとは良くなるかも。
  2. 一番内側のループで処理をスキップするための判断を加えるのは無駄。
  3. 一番内側のループから真ん中のループに外出ししてきた変数を使って処理をスキップすれば最内ループが丸々スキップできておいしい。

という感じの苦肉の策で AC をもらった。E 問題だからこんなものかも(というのはコンテスト中に解いてから言おうね)。


集合 S をビット表記により 0,1,…,2N−1 までの自然数にエンコードしてしまうと、S=0,1,2,… 順にループするだけでトポロジカル順序が守られることなどから、実装が簡潔になります。

自分はこの条件を知らないままなんとなくでうまくいく方法を真似しているだけだなあ。


頂点0からスタートするが、訪問済み頂点集合を考える上で頂点0は最初は含めない

こうすることで「訪問済み頂点集合が全集合になった」時「頂点0に戻ってきた」ことを意味するので、戻り道も含めた問題条件に適用できる

これを考慮するなら自分の AC 提出の 10 行目を NP[0][0] = 0 としなければいけないが、実際にそうしなければいけないだろうか。

NP = Array.new(N){ [Float::INFINITY]*2**N }
NP[0][1] = 0

NP[現在地][経由地] = 移動コスト であり、ゴールは NP[都市1][全都市網羅]。ゴールに初期値以外のコストが設定されているとき、それは全都市を経由してから現在は都市1にいる(またそれにかかるコストがいくらか)ということなので、スタートが NP[都市1][都市1] でも NP[都市1][無] でも関係はないかな。

 提出 #17524559 (AC / 1283 ms)

スタートが NP[都市1][都市1] でも NP[都市1][無] でも関係はない」ということと関係するのだけど、konayuki さんの提出 #17520925 のこの行……

dp[0][1] = 0
for i in 0..goal
  next if i&1 == 0

17 行目は、自分も全く同じように書いたが、スタート地点の初期化。だけど 19 行目のスキップが目新しい。これは経由地点にスタート地点を含まない場合を除外している。当然これに関わるコストを記録した配列の中身は初期値の Infinity で間違いない。

2N2N-1 になるだけでループの回数が半分になるのだからこれはとてもうまい。これもひとつのケチビットだな、ということで、メモ配列からもループの繰り返しからも最初から除外しておけば条件分岐すら不要。

ところで、コストを記録するメモは Array[N][1<<N(-1)] よりも Array[1<<N(-1)][N] としている提出がほとんどだった(例外が自分と konayuki さん)。これは「一番内側のループで変化しない配列参照をループの外に出せばちょっとは良くなるかも」の発展として理解できる。行列計算ともたぶん関係する。多重ループの最内ループが多次元配列の何次元目をイテレートするかは性能と無関係ではない。スクリプトにおいても、途中までの配列参照をローカル変数にメモすることでコスト削減が期待できる。

この2点で 1933 ms が 1283 ms になった。

 左にマイナス1ビットシフトは右に1ビットシフト

負数を習う中学1年生らしい言い換え。

さっきの提出で意図せず -1 ビットシフトしている部分があったが、エラーにもならず正しい答えが出ていた。Ruby に助けられた怪我の功名。この仕様は特に明記されていないし知らなかった。

これまでは 1<<N が取り得る値の最小が1だとばかり思っていたから、0にしたい場合を例外扱いしていた。活用したい仕様。

 提出 #17557645 (AC / 852 ms)

同じ都市を2度以上訪れて得することはない」、という考察を何か所かで読んだので、next if 0 < v[f-1] という条件を真ん中のループに足してみたら、1283 ms が 852 ms になった。わーお。

ちなみに Integer#[] である桁のビット(0,1)が得られるのだけど、最下位(右端)のビットが0番目になっている。負の添字は必ず0が返るっぽいので、今度は意図してこの仕様を利用した。

 提出 #17558093 (AC / 769 ms)

負の添字は必ず0が返るっぽいので、今度は意図してこの仕様を利用した」とか書いたけど、0は望ましい結果ではなく、結果的にスタート地点である都市1だけは何度も発着を繰り返していた。

真ん中のループの繰り返しから都市1の分を引いて N 回を N-1 回にしたら、852 ms が 769 ms になった。もうこれ以上は無理でしょ。

Integer#times の方が Range#each より速いようだったので Integer#times を使っている。そのせいで f(rom) と t(o) で都市番号への対応付けがずれているのが罠。

 提出 #17563476 (AC / 627 ms)

経由地を記録したビットフラグ(v)から0のビットを抽出して真ん中のループと一番内側のループに利用したら、769 ms が 627 ms になった。さすがにもうこれ以上はないでしょ。

 提出 #17563659 (AC / 583 ms)

TLE を初めての AC に変えた立役者である next if NP[0][-1] <= c0 が、変形を受けながらずっと残っていたのだけど、いつの間にか用無しになっていたことがわかったので消したら、627 ms が 583 ms になった。沼っぽくなってきたぞ。

メモ配列を見たら 0 番目の要素が 0 と Infinity に決まっていて無駄なので、長さ N の配列が N-1 にできるけど、ちょっとした省メモリにはなっても速くはならない感じ。

 提出 #17575125 (AC / 217 Byte / 1731 ms)

沼といえばゴルフ。217 バイト。

(N,),*Z=$<.map{_1.split.map &:to_i}
V,=C=Z.map{|a,b,c|Z.map{(_1-a).abs+(_2-b).abs+[0,_3-c].max}}
V+=[9e9]*N*M=1<<N-1
M.times{|v|N.times{|f|g=N.*v|1<<f-1;w=V[v*N+f];N.times{|t|V[g+t]=[V[g+t],w+C[f][t]].min}}}
p V[-N-N]

TLE になったら元も子もないので削れない一時変数と -1 がある。

 提出 #17667397 (AC / 207 Byte / 1963 ms)

うん、沼だ。207 バイト。

配列の初期化を省いて || で初期値を補うようにしたら 10 文字短くなって 200 ms ほど遅くなった。

(N,),*Z=$<.map{_1.split.map &:to_i}
V,=C=Z.map{|a,b,c|Z.map{(_1-a).abs+(_2-b).abs+[0,_3-c].max}}
(1<<N-1).times{|v|N.times{|f|g=N.*v|1<<f-1;w=V[v*N+f];N.times{|t|V[g+t]=[V[g+t]||9e9,w+C[f][t]].min}}}
p V[-N]

整形すれば普通に読めるあたり変態度が足りないと思うんだよなあ。発想に飛躍がない。

 研究>提出 #17680607 (yamagiri さん / 556 ms)
  • ループの回数が何パーセントか少ない。内側のループが 0(potentially 1) to 0 でなく 0 to 1 だから。そうしようとすると初期化にフラグが絡んできて手間がかかると思ったけど、実はそうでもなかった>提出 #17685423。手間を省いた代償として数万回のループの初回にしか関係しない || が二重ループの内にあるけど、大差ないみたい。
  • とりあえず大きな数としての初期値に Float::INFINITY を使うと、10**9 のような整数型を使うより比較にコストがかかる。

2020年10月15日 (木)

最終更新: 2020-10-18T20:31+0900

[AtCoder] HHKB プログラミングコンテスト 2020E 問題 Lamps

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 問題に手を出した。

 提出 #17317545 (TLE)

方針はすぐに決まった。逆に考える。照明の置き方が 2^k 通りを網羅しているのだから、照明の置き方を考える必要がない。あるマスを照らす照明の置き場所が何か所あるかを数えることにする。

もちろんグリッドを1マスずつ移動しながら4方向に探索を進めるようでは TLE を免れない。N の上限が 2000 の時に 2N^3 マスの走査は認められない。

lambda P が4方向の探索を省力化する工夫なんだけど、2回の P の合計が後半の N^2 のループと同じくらいの重さであり、N^2 の上限が 400 万だということはループの中身がごく簡単な処理でなければ Ruby は1秒2秒で終了しないので、N^2 ×2の結果は TLE だった。

 Ruby によるすべての提出

TLE の山を見てわかる通り、Ruby にとってこれは実装をがんばる問題らしい。そうとわかれば考えるより先に手を動かすのみ。

 後日の提出 #17357029 (AC / 1433 ms)

構造はほとんど同じ。lambda P の代わりの lambda F が4、5倍速いおかげで AC になった模様。スクリプト言語は自分で書いたスクリプトとランタイムライブラリの処理速度に雲泥の差があるので、プリミティブな処理を自分で書かずにいかに丸投げするかが肝要。

それと、2の冪乗を含む掛け算は展開すると一部がループの中身に関わらない定数になって外に出せる。2のK乗を1回だけ計算しておけば、ループの中の2の累乗計算は1回だけでいい。もちろんその計算結果は2回目3回目に備えてメモしている。

最終更新: 2020-10-17T17:20+0900

[AtCoder] AtCoder Beginner Contest 174F 問題 Range Set Query

C 問題が解けなくて大爆死した回の ABC。「時間内に B 問題までしか解けなかったので今日の日記は C 問題」。F 問題が解けたら D と E も解けたつもりでいいんじゃないかな?

 提出 #17399477 (TLE×4 / 427 Byte)

どういうデータであればクエリに答えが出せるか、どういうデータ構造であればひとつひとつのクエリに妥当な時間で答えが出せるか、とっても考えた。

  1. ユニークな色数の累積和で……
  2. だめだめ、始点の位置によってユニークさが変わる。
  3. じゃあ色ごとに直前の出現位置を記録して……
  4. でもクエリごとに区間をスキャンして区間内でユニークな色を数えるわけにはいかない。
  5. 始点か終点を固定してよければ定数時間で答えるためのデータを用意できる。
  6. でも始点も終点もクエリごとに移動する。
  7. 始点用のデータと終点用のデータの2本を組み合わせて答えを出せないか。
  8. 無理。
  9. う~ん。
  10. 色をスキャンしながら現在のユニークな色数とその色がユニークである始まりの点を記録するとする。クエリ区間の入りと出を色のスキャンと同時並行で処理して……

「LOC (last occurrence of colors)」とか「QIR (q in range)」といった名前をとっかかりに部分的に形を作っていった結果、移動する終点に合わせて始点用のデータを(事前に用意するのではなく)継続的に発展させていくやり方に落ち着いていた。

色の列を空間としてではなく時間として処理すること*が振り返ってみての転換点。意識してではなく手探りで進めるなかでの変化だったけど。

でも TLE。ソート列やハッシュ表といった素朴な構造ではダメみたいだ。

 提出 #17400113 (TLE×1 / 622 Byte)

BIT を持ち出しても TLE とは恐れ入りました。ソースコードが長くなるのが仰々しくて嫌だとか言っていられない。

 Ruby によるすべての提出

TLE の山と AC 提出の実行時間を見るに、Ruby にとってこれは実装をがんばる問題らしい。そうとわかれば()。

 提出 #17407692 (AC / 600 Byte / 1731 ms)

配列と BIT に余分な要素を付け加えて単項マイナス演算子と引き算の数を減らしたり、配列の初期値を工夫してループの中の if を取り除いたり、1-origin な入力値を 0-origin に加工するのをやめたり、i-=i&-ii&=i-1 に代えて演算子を1つ減らしたり、といった泥臭い改善の成果で AC。

こういう脳筋的努力は考察不足の可能性がちらつくと身が入らないのだけど、その心配はなさそうなので心置きなく。

 提出 #15667239 (climpet さん / AC / 1696 ms)

これが Ruby で一番速い(しかも Ruby で一番早い AC でもある)。速さの秘密はよくわからない。クラスやメソッドなしですべてが一体だからだろうか。 初めて見たのだけど BIT の初期化をするこの行……

b = (0..n).map{|x|x&-x}

BIT 実装のキーでもある LSB を蓄えるこれは公差1の等差数列を初期数列にしようとすると現れる。蟻本の図を見ていたのだけど、LSB は内部配列の要素が分担する重みに対応している。倍率(公差)は好きに決めたらいいだろう。

BIT の初期化が多少複雑になっても実行時間でペイするのは変数 u の存在がある。自分の提出で答えを設定する式は Ans[q] = r-l+1-Dup[N-l] (変数 Dup が BIT) だけど、BIT の初期値の工夫により -l が消せても +1N-l も残る。そもそも BIT を使用する向きが違っているのだ。BIT から2回値を参照するのを嫌って自分は向きを決めたけど(※BIT の操作が一番のホットスポット)、変数 u があれば参照が1回節約できる。参照が同じ1回なら他の部分の有利が生きるということなのだろう。

* この「空間」と「時間」はユニバーサルな表現ではなかったかもしれない。三次元に囚われた話者の感覚に根差した主観的な意味が込められていて、理解する前提条件になっていると思う。


2020年09月22日 (火)

最終更新: 2020-10-14T18:33+0900

[AtCoder] ACL Contest 1A 問題 Reachable Towns

ACL は ARC と AGC の中間あたりの位置づけだそうな。この A 問題は 300 点問題。1問目のこれしか解けそうにない。

 最初の提出 #16962327 (TLE)

移動可能な範囲が第Ⅰ象限と第Ⅲ象限に限られるが、移動先の点からさらに移動先を選ぶことができる。双方向に移動可能だし、X と Y の比率を変えながらジグザグに Y=-X 方向に移動することもできる。ともあれこの感じ(「友達の友達は友達」)は UnionFind だと思った。

問題は Union する点の選び方で、見境なく Union したら TLE になった。

見境なくとは言っても、相互に移動可能なら片方向だけを取り扱えば足りるわけで、X 座標の昇順に処理することで X 座標の大きい方から小さい方だけを見るようにしている。X 座標のソートに関してもこの問題で NlogN の時間をかけるのはもったいなくて、線形時間でソート列が手に入る。

 3番目の提出 #16962544 (AC / 565 Byte / 559 ms)

Union した中で一番条件のいいものだけ代表として残すようにしたら AC。

 Python で一番速い提出 #16928237 (maspy さん / 363 ms)

よくわからないが UnionFind ではない。キーは12行目の if x + min_y == N+1: だと思う。UnionFind で形作られるグループが持つ幾何学的性質が何かあるのだろうか。

右上がりの対角線上に並ぶ場合と右下がりの対角線上に並ぶ場合を対極として、その中間の状態がうまく考えられない。

X 座標と Y 座標がともに 1..N の順列だということから導かれる論理的必然性を何か見落としてると思う。


検索してたら答えらしきものが見えちゃったんだよな、maspy さんのページは避けてたんだけど他の所で。

頂点をソートして x 座標が小さい順に見ます。

頂点 i と頂点 i+1 について、「y1, …, yi が (N,…, N−i+1) の順列」であるときのみ非連結であり、そうでないとき必ず連結になることがわかります(あとで証明かなんかできたらいいな、、)

わかります」(わかりません)

 提出 #17013139 (AC / 1055 Byte / 326 ms)

maspy さんの提出に沿って*理解したことをひとつひとつコメントにしながら書いた。完全にそのままではなく、「# ymin の最初期化が必要?」とコメントしたように、ループ中の代入をひとつ省略した。(あ、タイポ。最初期化→再初期化)

しかし、ガイドなしの独力でこの道筋が見つけられるとは思わん。

 「UnionFind で形作られるグループが持つ幾何学的性質」

けんちょん(敬称略)のページにわかりやすい図があった。へー、そうだったのか(まだ見えていなかった)。

ACL Contest 1 A - Reachable Towns (300 点) - けんちょんの競プロ精進記録

でも図を見てみたらある意味わかって当然の図ではあった(それがわからなかった)。つまり、x + y = N+1 という X と Y の関係式を見て幾何学的性質について考えたのだし、であれば、その性質は y = -x + N+1 という直線に関わるものでしかありえない。答えを目の前にしながら「わからんなあ」と悩むふりをしていたのだった。下手の考え……。

* ~に沿って、というのはある意味嘘。こちらにゴールがある、という指針だけを手にして考えた結果の式が一致することを確かめただけ。結果が同じなのだから考えたことの軌跡をコメントとして残さなければ完全丸コピと見分けがつかない。コメントを書くのは必然だった。


2020年09月20日 (日)

最終更新: 2020-10-10T17:39+0900

[AtCoder] AtCoder Beginner Contest 179/D,E,F

 D 問題 Leaping Tak

コンテスト時間は D 問題で詰まっているうちに終わってしまった。計算過程で余りをとらないと一部の入力で TLE になってしまうのだが、余りがうまく計算できなかった。何を言っているのか自分でもよく解らない。

 提出 #16922727 (AC / 302 Byte / 282 ms / 15976 KB)

一日経ってみれば普通に AC できた。どこに詰まっていたのか解らない。

もうちょっと書く。方針。

  1. スタート地点1に立って移動可能なポイント(S の要素)を眺める。
  2. スタート地点から(1ステップで)それらの地点へ行く方法は1通り。メモする。
  3. 地点1に一番近い移動可能地点A(1とメモしてあるはず)に移動する。
  4. そこから移動可能なポイントを眺める。移動した分だけスライドしたが地点1からの眺めと同じである。
  5. 地点Aに来る方法が1通りなので、地点Aから行ける地点へ行く方法も1通り増える。メモする。
  6. 以下、3、4、5の繰り返し。
  7. さて、地点 N に来る方法は何通りになったでしょうか。

移動可能地点ひとつひとつに対してメモしていては TLE になる>提出 #16879797

S の要素数は N に準ずるが、S を定義する区間の数は幸いにも最大で 10 に制約されている。メモの仕方を工夫して、絶対値ではなく変化量を記録する。どうせ地点を端から端まで処理するつもりなので、変化量をつどつど加算していけば絶対値は得られる。これでループ1回の書き込み量が区間の両端の数(最大で20)まで減る>提出 #16883620。TLE なのは、途中で余りを求めなかったから多倍長整数の桁数に比例した計算量に押し負けた結果。

ここから途中過程で余りをうまく求められなかった(冒頭に戻る)。

 E 問題 Sequence Sum

D 問題で詰まったのでコンテスト中に問題文は読まなかった。色気を出せば解ける D 問題も解けなくなるので。

 提出 #16923150 (AC / 253 Byte / 68 ms / 15728 KB)

すんなり書き下してデバッグの必要もなかった。N の値が膨大だが M の値がそれなりなので、余りの種類もそれなり。となれば A 数列は途中から循環する。

 F 問題 Simplified Reversi

D 問題で詰まったのでコンテスト中に問題文は読まなかった。色気を出せば解ける D 問題も解けなくなるので。

 提出 #16923745 (AC / 518 Byte / 513 ms / 17472 KB)

すんなり書き下してデバッグの必要もなかった。縦軸横軸それぞれにブロックラインが単調に前進していくだけなので、それを BIT に記録した。

@chokudai「F問題とても好きな問題なんだけど、データ構造でいくらでも殴れちゃうのが残念……O(N)で解いてみてね><

BIT は読み書きともに対数時間なので、さっきの提出は O(NlogN) になる。O(N) で解くというチャレンジ課題がまだある!

 提出 #16937624 (AC / 269 Byte / 254 ms / 17392 KB)

N に比例したループの中で長さ N(-1) の配列に書き込むとしても、書き込む要素の総数が 2N 以下にとどまるなら O(N) なんじゃないかな。かな?

ひと工夫しないと配列への書き込み量が N×N になってしまう罠がある。変数 ii を介在させて書き込みタイミングを一拍遅らせたことが書き込み量削減のキモ。これには以前日記で触れた「Scintilla 方式」が参考になった。その要諦は……「メインのデータ構造はギャップバッファ。そこに張る行インデックスの更新コストの問題。更新が必要なインデックスのエリアはある点から始まり必ず末尾で終わる。ある点をひとつ記憶しておくことで更新範囲をある点とある点の差分にすることができる。

 ところで kotatsugame さんが…… 提出 #16893528 (121 Byte / 198 ms)

ゴルフをしながら Ruby の中で最速タイムを記録していたのだった。異次元過ぎてさっぱりわかりません。

 @2020-10-09 提出 #17269548 (AC / 249 Byte / 243 ms / 17464 KB)

お風呂でなんとなし思い付いた。

メインループのイテレーションごとに X 軸と Y 軸が参照軸と更新軸のどちらかの役割を受け持つ。参照軸更新軸それぞれが N-2 要素のメモを持つ。メインループの中で……

  1. 参照軸のメモを参照したい要素まで(必要なら)埋める。
  2. 参照した値でスコアを更新する。
  3. 更新軸のメモを参照した値の範囲まで(必要なら)埋める。

前回の提出では更新軸のメモが更新の対象だったが、今度の提出では更新の一部が参照軸の参照時に分散している。その結果ループの中がストレートになり、値の大小関係によってあっちの値を参照したりこっちの値を参照したりという場合分けが不要になっている。しかし変わらないタイム差(たぶん配列参照のコストが大きい)。

メインループの中に2つの対称的な書き込みループがあるあたりが kotatsugame さんの提出と共通だと思ったけど、あちらでは一回に片方のループしか実行していなかった。たぶん参照軸のメモだけ更新しているのではないか。もはやこの軸の命名が意味不明であるが……。

更新軸が更新軸である所以はそれが「ブロックライン」をメモする軸であり、今後のスコア(何枚の黒石を裏返せるか)に影響するから必要があって書き込むからなんだけど、何枚の黒石を裏返すことができるかを知るために見る参照軸のメモだけが更新の対象でいいなんて、どうして想像できる?

参照軸のメモは「何枚裏返すことができたか」の記録として捉え直すことができるんだろうな、きっと。それだけわかれば十分だということの理解はまだ。

 提出 #17272161 (AC / 205 Byte / 244 ms / 17380 KB)

更新軸の更新部分に当たる1行を削除してみたが AC のまま。たしかに参照軸のメモだけ更新していれば十分みたいだ。

「ある座標より後ろは何枚裏返せたかの記録がまだない」というのが、参照軸のメモから読み取るべきもうひとつの情報であり、これは変数 ii の意味とほぼ同じ。だから十分。


2020年09月12日 (土)

最終更新: 2020-10-09T18:36+0900

[AtCoder] AtCoder Beginner Contest 128E 問題 Roadwork

精進ですよ。今日*こういうものを読んだ。

【Python】平衡二分木が必要な時に代わりに何とかするテク【競プロ】 - Qiita

この前の日記(20200907p01)で散々 TLE に苦しめられた問題も、C++ なら変数 r を map に、変数 nmin を multiset にすることで、ある範囲のキーを二分探索で検索することも、小さい方からキーを取り出すことも、STL 任せで妥当な時間で行える。適当に速くて短い提出を選んだけどこんな感じ>「提出 #16578878」。トリックは必要ない。

Qiita の記事で題材にされているのが今日の E 問題 Roadwork で、記事をよく理解するためにまず解きたいと思った。

 提出 #16613595 (TLE×1 / AC×14)

とってもくやしい。

最悪の場合に 200k 要素の配列に 200k 回書き込みを行うのが良くないのかなと思う。掛けて 40G×単位サイズの書き込み量。あ、これはやべーわ。

遅延更新と区間更新が可能なセグメントツリーがあればこのアホな書き込み量はなんとかなる気がするなあ。

 提出 #16618964 (AC / 721 ms)

ループの中でがっつり二分探索して配列のスプライシングをしても通るあたり、この前の F 問題(前掲)より易しい。

二分探索がしたい、線形よりましな時間で挿入がしたい、というときに平衡二分探索木が欲しくなるんだよね。

プライオリティキューを実装するときも、最大(最小)値を得るだけでなく、整列済みのキューにアクセスして操作したいときがある。でも内部構造がヒープだからできない。std::multiset とは違う。

2本目のキューに削除済みとマークした要素を入れておくの頭いい(Qiita の記事)。二分探索はできないけど、一度放り込んだ値を後から取り消したいときが、たしかに以前あった。

 Ruby によるすべての提出 (実行時間昇順)

Ruby のバージョンが違うので一概に比較できないけど、他の AC はどれもヒープを使用していて 1000 ms 以上かかっているところが共通している。配列のスプライスよりヒープの方が賢いよね。

でもスクリプトで手の込んだことをするよりインタープリタに丸投げした方が速いこともある。Python は汎用スクリプト言語でありながらそういうバッチファイル的、グルー言語的なあり方も板についている。

たとえば、ダイクストラ法、ワーシャルフロイド法などのアルゴリズムが名前で利用できる。ヒープ構造もある。二分探索も、比較式をブロックで与えられる汎用性が Ruby にはあるが、それが遅さに繋がってしまう。実は lower_bound, upper_bound だけでほぼ足りる。オブジェクトの形が不定だとしても、key 配列と value 配列を持てば解決する。

Ruby に範囲を指定する Array#fill があるのを、しかも古くからあるのを知ったときは嬉しかったし、同時に自分の不明も明らかになった。Ruby は汎用スクリプト言語だからループやイテレータを使って Array#fill 相当の処理は自在に書ける。書いてきた。でも書かずに fill を1回だけ呼び出すのが賢い(が、実は Ruby で実装されています、という可能性もなくはない)。

* 日記を書いている今日は10日。


2020年09月07日 (月)

最終更新: 2020-10-02T19:10+0900

[AtCoder] AtCoder Beginner Contest 177F 問題 I hate Shortest Path Problem

まだ AC してない。(←その後 AC)

 8日3時 提出 #16567031 (TLE×3 / AC×8)

前回の日記(20200905p01)で解いた問題と構造は同じ。一番大きな違いはグリッドの大きさで、こちらは制約上の上限が 200000×200000 だから1マスずつの処理では間に合わない。

そこは何とかなって今は上限20万回のループの中で、上限20万要素からの二分探索が2回と、上限20万要素からの最小値検索を1回行っている。配列からの最小値検索が線形時間なのが明らかにまずいんだよなあ。実はループの中で配列のスプライシングをやってるのもまずくて、まずいのが2つ組み合わさって手がつけられないんだなあ。

 8日23時 提出 #16582545 (TLE×1 / AC×10)

問題のイメージが掴めてきた(今です)。H 枚の板が上から順にやや右下がりで設置されていて、最上段では横一列に並んだ W 個の蛇口から水が流れている。k 段目で注目すべきは水が落下している位置(複数)と、そこに流れ込む水流のうち落下点に最も近い蛇口がどれか。蛇口と落下点を結ぶ線はどれも交わらない。

蛇口と落下点の距離が最小となるものを効率的に見つけるデータ構造がわからんのだよなあ。

あ、TLE が2つ減ったのは nmin, rmin の導入効果。「蛇口と落下点の距離」ごとに数を数えておいて、数がゼロではない距離を小さい順に検索する。距離は増加する一方だから検索範囲は狭まっていく。

 9日0時 提出 #16584229 (AC / 456 ms) やったぜ!

今回のポイントは r を可変長から固定長にしたこと。可変長のときの r のサイズは W から減っていく一方だったのだけど、固定長だと最初から最後まで W(+1)。それでどうして速くなるのか。

r の中身について。これまでは落下点と落下点までの横移動コストを記録していた。今回は落下点は(固定長)配列の添字となり、配列の中身に蛇口の位置を記録した。落下点までの移動コストは計算で求まる。

ここでトリック。落下点と蛇口の位置関係は「蛇口<=落下点」で決まってるので、「添字<中身」の場合を、落下点を見落とさずに配列のスキャンを安全にスキップするための情報とした。

Ruby で提出してると AtCoder Problems で確認できる Shortest Code の数がいつの間にか増えている現象がある。この提出が(いまのところ)そうだし、巨大企業(20200607p01)もそう。

 Ruby によるすべての提出

AC 一番乗りである。C++ は甘え。まあ、Python は普通に AC がいくつもあるんだけど>「Python によるすべての提出

 提出 #16590103 (AC / 453 ms)

  1. コメントをプラスして、
  2. ちょっとだけ余分にスキップするようにして、
  3. ありえないケース(すでにある落水点の最近蛇口更新)に対応したコードを省いたが、

見事なまでに変わらず。スキップ情報を UnionFind と同じように深さ優先探索で貪欲に求めて書き込むようにしても、やっぱり変わらないだろうなと思ってる。


2020年09月05日 (土)

最終更新: 2020-09-12T01:54+0900

[AtCoder] AtCoder Beginner Contest 175E 問題 Picking Goods

今週は ABC がないようなので精進である。D 問題が「コンテスト時間中には解けなかった」ので E 問題は問題文を読みさえしなかった。

 提出 #16526116 (AC / 1195 ms)

一行ずつ左から処理するにあたり保持するデータを vs = [0]*4 と定めたあとは、特に詰まるところはなかった。つまりそこで詰まったということであり、一番のお楽しみポイントだったということ。あるマスにおける状態と、状態から状態への遷移が、4要素の配列でまかなえることの発見が。

 Ruby によるすべての提出

今のところ2番目の提出より倍くらい速いみたい。だけど書き方による違いかもしれないね。

 (飛び道具*なしの) Python で一番速い 提出 #16010823 (ikatakos さん / 357 ms)

この人の名前は AtCoder を初めて日記に書いた 20190907 のこの部分(20190907p01.05)で初めて目にした。このときも Python で一、二を争うくらい速くて、同じくらい速い他の複数の提出から参考にしたと参照されていた。

参考にできるところがあるだろうか。

自分のスクリプトで気になっているのが r0[c] = vs.max と書いた部分で、長さ 4 の vs 配列のうち 1,2,3 番目は基本的に昇順ソート済みなのだけど、0 番目にイレギュラーが飛び込んでくるせいで vs[3] や vs[-1] とは書けずに vs.max と(4要素とはいえ)配列を走査するほかなくなっている。

up = dp[i - 1][j][3]
for w in range(4):
   dp[i][j][w] = max(dp[i][j - 1][w], up)

上のように、隣の行から値を引っぱってくるときに最大4要素を更新すればすべてソート済みであるとして末尾の要素を最大値として取り出すことができるんだけど……

 遅くなったよ! 提出 #16526544 (AC / 1480 ms)

もうわからぬ。

 kuma_rb さんの2つの提出

違いは入力 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 の場合のパフォーマンス特性はわからないけども。

 提出 #16528314 (AC / 934 ms / 36832 KB)

Python で一番速い提出 #16084621 を読んだ。コンパイル済みのバイナリを書き出して実行するなら Python である理由がないじゃん、と思ったんだけど、元になった Python のソースをちゃんと読めるようにしてくれている。コンパイル前のソースが Python なのだった。

長さ C の作業配列が昇順ソート済みだという特性が活用できていなかったことがわかったので、それを踏まえたコードに。あまり速くはならず。結局 R×C 回配列を更新するところは変わりがないから。

 提出 #16528556 (AC / 1813 ms / 188724 KB)

配列を昇順ソート済みにするための書き込みを省いて、配列の重複のない範囲から最大値を抽出するだけにすれば良くなると思った。倍遅くなってメモリ消費も激増した。むしろ逆で、予想外のメモリ消費がスローダウンを招いた? Array#[] か Array#max に何かある?

 提出 #16528834 (AC / 1038 ms / 46636 KB)

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

に書き換えたところ、1つ前の異常なメモリ消費、異常な実行時間だったものが、2つ前よりメモリも時間もやや悪いという、予想の範囲内の結果に収まった。

いや、悪くなってるのはがっかりなんだけど、1つ前の悪くなり方はやはり尋常じゃなかった。配列に最大値を聞くのではなく、添字の範囲を使って配列の最大値を求めるという回りくどいやり方より遙かに遅かったのだから。

素直なやり方で予測可能な結果が出るなら速かったりしないかなあ。

 提出 #16543158 (AC / 727 ms / 37188 KB)

困ったときのセグメントツリー。もう3回目の実装なので空で書いてバグも無し(でも一応内部データを目視するテストはした)(1回目と2回目は空で書いてバグだらけ)。メモリ参照の局所性なんて関係ないハードウェアから遠い言語でできる悪あがき。今のところのベスト。こんな作業ってアルゴリズムひとつで桁違いの差をつけて置いて行かれる類のものだ。楽しくはあるけどこれで終わり。

@l の利用場所すべてで @l+1 って書いてるから @l の定義から -1 を削っておけば良かった。

* コンパイル済みのバイナリ展開とか。


2020年08月26日 (水) [Ruby] 当然あるだろうと、先にタイプしてから存在を確認するメソッドに Numeric#sign がある。ところが 2.7 にもないのである。zero?, nonzero?, positive?, negative? は存在している。でも -1,0,+1 のいずれかを返す sign メソッドはないのである。レシーバが -0.0,+0.0 の場合に何を返すべきかはすぐにはわからないけど、-1.0,+1.0 を返すのは罠になりそうなのでレシーバ自身が無難だろう。■「sign メソッド」で検索したらトップに出た>「Math.Sign メソッド (System) | Microsoft Docs」。ほらほら。■■■わかったぞ。i <=> 0 で代用できる。メソッドであってほしいものと演算子で十分なものと、なんかちぐはぐだね。■<=> (Spaceship Operator) についてビャーネさんが何か言いたそうにしていたのをどこかで読んだ。Ruby での存在意義はこの1メソッドを定義するだけでクラスを Comparable にできることだと認めてはいる。でも C++ では何を追加しても、互換性を保って追加をする限り、煩雑さを増すことにしかならないだろう。■Uniform Function Call が一番楽しみだな、C++ に導入されるとしたら。シンタックスの統一はテンプレートの適用を拡大するし、メンバ変数を使用しないアクセサリメソッドをグルーピングのためだけにメンバ関数にするようなことを阻止できる。

最終更新: 2020-10-09T18:49+0900

[AtCoder] 第二回全国統一プログラミング王決定戦予選 - AtCoderC 問題 - Swaps ()

読んだ眺めた>「競プロerのための群論 (swapと順列と対称群) - little star's memory

数学の用語で何か抽象的なことを言ってるなーということと、Swaps と Moving Piece の2問(だけじゃないけど)が取り上げられているということはわかった。

Moving Piece は先日解いたので(20200820p01)、以前解けなかった(20191111p01) Swaps も解ける気がした。

 提出 #16248329 (AC / 403 Byte / 283 ms)

もちろん今日も AC に至るまでに WA を出した。それも前回と全く同じ入力に対して同じように誤った答えを出した。前回書いたスクリプトはひとつも参考にしなかったにも関わらず、構成も結果も瓜二つなのは、書いた人間が同じだからですね。同じところに留まっている……。

 デバッグ

前回と違ったのはテストケースが利用できたこと>「atcoder_testcases > nikkeiqual_2019 > C

今回のような Yes/No 問題の場合、間違った方法ででたらめな答えが出ても2分の1の確率で AC になってしまいデバッグが捗らない。そのような場合に(テストケースなしでも)使える手法をひとつ思い付いた。

 提出 #16245274 (TLE)

スクリプトの真ん中に sleep (※引数なしなら永眠)を仕込んで、前半部分の Yes/No 判断に誤りがないかを確かめた。結果は TLE と AC のみだったので、前半部の判断は間違っていない。

 提出 #16245473 (WA)

予想外の WA (TLE なし)だった。これは後半部の No を sleep に置き換えたものなのだけど、1つも TLE がなかった。1つもないというのは(入力とバグり方がコラボした)偶然の結果なのだけど、偶然でもなんでも無条件 Yes は明らかなバグだ。

こんな感じで TLE(sleep) や RE(ヌルポ、0除算、変数名タイポ)が Yes/No ではない第3、第4の答えとしてデバッグに利用できると思った。こういう考え方ってゴルファーが得意としてそうだよね。常識だと思ってそう(違うんですよ)。

 バグ

わかってみれば些細なことで、思えば去年もインデックスの扱いに確信が持てずに試行錯誤をしていた。どうして B 数列が予めソート済みではないという、そのひと手間で穴にはまるのか、何度でも。

つまり、A 数列の初期配列と B 数列の初期配列。A 数列のソート済み配列と B 数列のソート済み配列。A, B 両者の扱いが対等なこれら4つは脳みその中に居場所が確保されていた。しかし、B 数列の初期配列をソート済みとする、と条件を整えたときに A 数列の初期配列がどうなるか(ソート済みではないし、元の初期配列とも異なる)、という概念が脳みそからすっぽり抜け落ちていた。A, B の対称部分に気持ちを良くして、差異に向ける目がなかった。去年も、今回も(初めは)。

 去年の借りを返す 提出 #16278383 (AC / 445 Byte / 199 ms)

「去年の WA」を完成させたもの。必要以上に慎重だった(見極めが甘く無駄だった)二分探索がないぶん、冒頭の AC 提出より速い。

 考察(おまけ)

前回の日記に全部書いてある(あれで全部だった)。ひとつだけ付け加えるなら、「逆の例は、B 数列に重複する値が存在する場合や、B 数列の最小要素以下の要素が A 数列に複数ある場合など」の「など」でごまかした具体例の3つ目。

ソート済みの B 数列に異なる値を持つ隣接要素 B[i] と B[i+1] があって、B[i] < A[k] <= B[i+1] となる A[k] が存在しないときも、A 数列のすべての要素にあるべき位置が存在するとは言えなくなる。(A 数列がソート済みなら B[i] < A[i+1] を確かめるだけでいい)

最終更新: 2020-10-26T23:02+0900

[AtCoder] 第二回全国統一プログラミング王決定戦予選 - AtCoderD 問題 Shortest Path on a Line

余勢を駆って前回2つの WA であっさり引き下がっていた D 問題に再挑戦した。これも C 問題と同じ 600 点問題。

 提出 #16254983 (AC / 387 Byte / 402 ms)

実は区間の片端に着目した貪欲法で解けるんですよ、というのが目から鱗だったスケジューリング問題そのままだった。どこにそう書いてあったかは忘れた*

前回の WA 提出 #8424473 を見ると、今と同じことは考えていたことがわかる。C 問題の場合にも言えるけど、そこで結果を分けたものが何か。考えたことを過不足なく言い換えることと、バグなくコードに置き換えること。それができるかどうか。

それはどうやったらできるようになるんですか? という問いは、どうしてそこで間違えたんですか? という問いと対になる。わかりませんよ。ワーキングメモリが足りないんじゃね?(テキトー) こういうとき脳筋は手を動かして慣れるしかない。そうすればより少ない脳のリソースで解けるようになったり、型通りの手法で解けるようになったりして、うっかりや見落としで間違えることがなくなる(という期待)。

 去年の借りを返す 提出 #16288240 (AC / 319 Byte / 375 ms)

区間のどちら端に着目するか。冒頭の AC 提出では L のソート順に処理していたが、「前回の WA」では R でソートしていた。それを完成させてみたら、冒頭の AC 提出で使用していた Array#slice! と Array#insert という、配列に対して呼び出すにはやや気が引けるメソッドが、Array#pop と Array#push という配列に相応しいメソッドに置き換わっていた。二分探索も3回から2回に減っている。Swaps の場合もそうだったけど、AC に至りさえするなら部分的には過去の方が優れてるのなんでだろう。

 解説記事を読んでもわからないので自分で書く。

グラフとか最短経路とかコスト0の辺を張るとかわからへんねん。

R でソートするバージョン(#p02.02)。

  1. RC を、ある地点(R)に到達する最低コスト(C)を記録したリストとする。R が同じならコストの低い方を記録する。R についても C についても昇順(2要素の比較において R が大きければ C も大きい)。RC の要素は R の昇順に追加されることに留意する。
  2. 区間 [L,R] から R までをコスト C で繋ぐ場合を考える。
    1. RC を二分探索し、最初に L かそれより後ろに到達する要素を見つける。より遠くに到達する要素はより高コストなので「最初」を見つける。

      見つからない場合は断絶があるということでありパスする。R の昇順に RC に要素を追加しているのであり、今後 [L,R) の区間に到達する辺は現れない。R に到達する辺があとから追加されることはあるが、C が負ではないのでパスで良い。

    2. 見つけた要素のコストを加算して C′とする。辺を追加することによりコスト C′で R に到達できることになる(始点は問わない)。
    3. RC に記録されている C′より高コストの要素は用済みであり取り除く(RC がコストの昇順であることを利用する)。処理時点で R が最遠到達地点であり、それより近くに高コストで到達することに価値がないから。
    4. ペア [R,C′] に記録する価値があるなら RC の末尾に追加する。
  3. ということの繰り返し。

ひょっとしたらこれも DP (動的計画法) の一種かもしれないけど、わからんけど、自分が頑なに DP の用語を使わないのは、それを言ってもメリットがないから。

一行ずつ左から処理するにあたり保持するデータを vs = [0]*4 と定めたあとは、特に詰まるところはなかった。つまりそこで詰まったということであり、一番のお楽しみポイントだったということ。あるマスにおける状態と、状態から状態への遷移が、4要素の配列でまかなえることの発見が。

これもそう。DP の核心は何を記録して遷移するかであり、それがわからないのに、「あ、これ DP だ」ということを言っても問題が解けない。むしろそれを言うことで何かわかったつもりになることが目眩ましになって問題に集中できない。過去に何度かそういう失敗をして、DP だということは言わないことにした。dp という変数名も自分にとって何も説明していないので使わない。

DP の一語でなく、配る DP、集める DP まで区別できるとまた違うのかもしれないけど、自分はそれらを識別しない。

* 蟻本(初版第1刷)の43ページ「区間スケジューリング問題」だった。


2020年08月20日 (木)

最終更新: 2020-08-24T19:08+0900

[AtCoder] AtCoder Beginner Contest 175D 問題 Moving Piece

コンテスト時間中には解けなかった。昨晩から苦しんで夕方に初の AC をもらった>「自分の提出

 最初の提出 #15953114 (RE / TLE)

バグが2種類あったけど方針は間違ってなかった。

 バグ1:K が各巡回グループ(配列 A の要素)の要素数より大きいときの端数(K%A[i].size)の扱い。

巡回グループの部分列(スコア数列)の和が最大となるときを考える。部分列の最大長が K%A[i].size 以下となる範囲で和の最大を求めるより、一周少なく回って(A[i].sum 1個分のハンディを背負って) K%A[i].size 以上 A[i].size 以下の長さで和の最大を求めた方が得する場合がある。

RE の直接の原因は、最初はゼロ除算を疑ったのだけど、Array#take の引数 k-1 が負になることだった。その値の出所が K%A[i].size。

 バグ2:1以上 K 個以下の連続する部分数列のうち和が最大となるものの求め方。

バグというよりパフォーマンス問題。Array#product で総当たりをしたので、間違いはないが時間がかかりすぎた。バグらせずに時間内に求める方法が最後までわからなかった。

 最初の AC #16057773 (729 Byte / 77 ms)

やっとバグ2がとれた。総当たりの方の、間違いではないが時間のかかる方法と答えをつき合わせてデバッグをした。

こうやって振り返ってもさっぱり参考になることが書いてないね。実装が難しかった、しかない。

 Ruby によるすべての提出(実行時間昇順)

現在の2番目のタイムが 95 ms。区間の最大値ということでセグメントツリーの使用は一応考えたんだよ。だけどこのときのこれが頭を離れなかった>「追加する要素との大小関係によって、待ち行列の末尾から、永遠に最大要素(最小要素)としての順番が来ない要素を追い出す」。おかげで 77 ms。

理想的にはこんなふうにすっきり鮮やかに解きたいね>提出 #16033967 (581 Byte / 175 ms)

普通に累積和の配列から k 要素を切り出して最大値を取り出してる(ss[_1 + 1, k].max)。回路長の3倍の長さの累積和配列を用意してるのがよくわかっていない工夫か(ss = (1 .. 3*l).each_with_object([0]){|j, o| o << o.last + Cs[lp[j%l]]})。

ss[l] が回路全体のスコアの和。0...l の範囲の1点を始点にして長さ 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 を含んでいようとも1つの統一された式を書きたい。実に自分好みのスクリプト。「if 文が嫌いである。(20181029)

そうだそうだ、自分は長さ k の部分列の始点を負のインデックスにすることで仮想的に配列の長さを倍にしたのだった。小賢しい。まあ、それでは長さ 2l にしかならないから、3l が必要な「場合」は配列の加算(a+a)をしている。このやり方をとる限り場合分けを解消できないね。


2020年08月03日 (月) Ruby には商と余りを同時に求める Integer#divmod メソッドがあるけど、それを q,r = 7777.divmod(101) みたいに多重代入で受けると、多重代入が遅いせいで(20200428p01.08.01)密かに期待するパフォーマンスメリットが相殺されてしまう罠がある。

最終更新: 2020-09-03T17:14+0900

[AtCoder] AtCoder Beginner Contest 174C 問題 Repsept

時間内に B 問題までしか解けなかったので今日の日記は C 問題。AGC の C なら解けないのは残念ながら当然だけど、昨日あったのは ABC で、C 問題は 300 点問題だ。嘆かわしい。

解るような気がしながら解らなくて、でもやっぱり解りそうな気がするという堂々巡りを繰り返すだけで考えがさっぱり焦点を結ばなかった。具体的には 7,77,777,7777,... という数列を規定するルールを、どのように捉えれば解きやすいか考えあぐねていた。

 提出 #15651178 (AC / 306 Byte / 136 ms / 14428 KB)

 提出 #15663806 (AC / 294 Byte / 118 ms / 14508 KB) ※無駄を省いて整理したもの

布団の中でも考えていて眠る前に AC が出た。だけどまだ解らない。このプログラムが停止するかどうかさえ自分には不確かだ。

たどり着けるならK回目までにたどり着くので「K回目までにたどり着かなかったら到達不能と判断」でもよかったか

うん、これが解らない。

K の余りをとるなら余りの種類が K 種類しかないのはわかる。同じ余りが出たら以降が循環ルートに入るのもわかる。K+1 回目以降の余りが必ず既出なのもわかる。わからないのは、自分が提出したスクリプトでははっきりとわかる形で K の余りを求めていないところ。たぶん変数 k に配列7の要素( 0 以上 9K 以下の値)を足して 10 で割ったあとの k の値がそれっぽいから、この k の値が既出かどうかをチェックする方法があると思う。

でも問題に用意された入力について言えば、答えが出そうな K からは必ず答えが求まっているようではある。それは必然なのか偶然(出題者の作為)なのか。

 Ruby によるすべての提出

他の人の提出を見ると明らかに自分だけ*おかしなことをしている(嬉しい)。え? 停止条件さえ判れば(※自分には判らない)、数列を順番に K で割るだけでいいの? (※桁が大きくなりすぎるので余りにだけ注目する必要はある)

たぶんやっていることは実質的に同じで、一方が難読化されているというだけなのだろう。問題の理解がこんがらかっているからスクリプトもそうなる。過去に2回くらい日記に書いてるけど、アホの子は自分で問題を難しくする。(問題の本質、抽象化された実質が理解できないから、無駄や回り道がなくせないという意味)。

 「おかしなこと」の説明をば

  1. 与えられた K の1の位の数字を見る。
  2. 1、3、7、9なら掛ける数を(1から9から)選べば1の位に7が作れる。
  3. 作りました。1の位の7はもう無視します。(K にある数を掛けてできた数の)1の位ではないところに7か7ではない数字が残ります。
  4. 次はそれに、K に(0から9の)何を掛けたものを足せば末尾に7が作れるかを考えます。
  5. 以下3へループ。
  6. 3から5は要は K に何を掛ければ7の列になるのか、1の位から順に決定していこうという手順。筆算をイメージしながら。
  7. たぶん、運が良ければ、もしくは不思議な法則に従って、掛けてできた数字のどの桁も7になることがあるでしょう。
  8. 全部で7がいくつ作られましたか? というのが答え。

 「7,77,777,7777,... という数列を規定するルールを、どのように捉えれば解きやすいか考えあぐねていた」

「レプユニット数」という概念があるらしい>「[AtCoder] ABC 174 C – Repsept | ヤマカサの競技プログラミング」 そういえば問題名が Repeat でも Respect でもなく Repsept だ(今初めて読んだ)。

 逆元?

この問題の2つの解法というのは、逆元とか割り算を含む式の余りについて理解を深めるチャンスだという気がするんだよね。何か関係がありそう。以前解けなかった問題>「階乗が法外な大きさになるので余りを答える問題。割り算を含む式の余りが求められなかった。

(別の問題の解説だけど)これも理解の手がかりにできそうな雰囲気。雰囲気しかわからぬ……

公式解説は累積和だね、横一列を1回の掛け算で済ます方法

僕の解法は「単純に2で割れないから逆元を使った難しい解法になる」と言われてた

抽象的に考えすぎて難しいだけでは。11ぐらいの小さい数で試したことがあれば難しくなく思いつけると思う

* この提出はお仲間かな。 https://atcoder.jp/contests/abc174/submissions/15654939


2020年07月09日 (木) コンテスト時間中に F 問題が解けたことはまだない。時間をかけさえすれば解けるということでもなく、解けた問題だけが日記になっているのだ。

最終更新: 2020-08-15T20:50+0900

[AtCoder] AtCoder Beginner Contest 173F 問題 Intervals on Tree

コンテスト中に解けなかった(問題文を読むところまでいかなかった)問題に挑戦。

「連結成分」っていうのがわかんないよね、まず。出力例1の解説を読むに、頂点集合が辺で繋がれたいくつの部分に分かれるかを数えるみたい。

 考えたこと

  1. 頂点集合は考え得るすべての通し番号から作られる(1~2、1~3、2~7など)。頂点番号と木の構造に関連はない。
  2. 頂点集合ごとに Union-Find するのはどう考えても間に合わない。
  3. LCA が高速に求められたらいけるだろうか。頂点集合に含まれる任意の2頂点をすべて試していたらどう考えても間に合わない。
  4. トポロジカルソートして割り振った番号と実際の頂点番号を見比べて何かわかるだろうか。わかんない。
  5. 木を構成する頂点を「決まったやり方で並べていったら(20200607p01.02)」連結成分が配列の連続する部分として見出せるだろうか。そんなにうまくない。
  6. 木ってどこが根とか決まってたっけ? どのノードでも根になれる? 葉でも根になる? なる。
  7. 一番考えやすいのは、葉が単独で連結成分を構成するとき。葉Cと親Pのあいだに辺があるような(=CとPが共に頂点集合に含まれるような) L,R の選び方が L<=[C,P].min && [C,P].max<=R だから、その否定。(追記:これは嘘。実装中に気がついたがこれだと頂点 C が頂点集合に含まれないケースが紛れている)
  8. 大元の根(※勝手に1つ決めます)に一番近いノードに連結成分を代表させることにすると、あるノードCを根とする連結成分がカウントされるかどうかはノードCと親とのあいだに辺があるかどうかでわかる。
  9. すべての連結成分(=任意のノードを根とする連結成分)について、それがカウントされるような L,R の選び方を数えよう。

 提出 #15106396 (AC / 307 Byte / 351 ms / 35716 KB)

スクリプト化にあたって一番考えたのって、重複組合せの求め方だった。最初 N×N にして間違っていて、仕切りを置く場所を考えるんだったような、と思い出すのに時間がかかった。そして最終的に補集合ではなく目的のものを直接数えられることがわかって無駄になった。

あと、ちょこざいなやり方だとは思うけど、C と P の大小で場合分けをしたくないなと思って符号を利用した>[(c+1)*(p-c),(p-c)*(c-N),].max。あ、カンマが余分。これは「2頂点間の最短パスは短絡辺を通るか通らないかのどちらかである」が最後まで見抜けなかった恨みである。

こうしたら最後の計算で根(c==0)の場合を例外扱いしないで済む。

P[0] = N # 0 を根にする。N は計算のため。
p (0...N).sum{|c|
	p = P[c]
	[(c+1)*(p-c),(p-c)*(c-N)].max
}

 Ruby(2.7)によるすべての提出

ワンライナーとかわけがわかりません><

あ、これ? 「閉路が存在しないならば「連結成分の個数 = 頂点数 - 辺の数」が成り立つ。」 木のどの部分を切り取っても木だろうし、木なら頂点数と辺の数は N 対 N-1 に決まってるので、頂点数と辺の数のずれの大きさがそのまま森を構成する木(連結成分)の数というのは、まあ、言われたらそうかもね、という感じ。

言われなきゃわからないし、なんなら、連結なグラフで頂点数と辺の数の比が N 対 N-1 ならそれは木だというのも、最初からなんだか化かされてるような気がしてる。


2020年07月01日 (水)

最終更新: 2020-07-09T19:18+0900

[AtCoder] AtCoder Beginner Contest 160D 問題 Line++

コンテスト中に解けなかった問題に再挑戦。(C 問題まで11分で終わらせてそこで力尽きていた。そんだけ時間を余らせてなぜ解けない?)

距離を求めるのに頂点の分類が必要だったのだけど、分類して組み合わせを網羅して距離を計算することができなかった。

今回は頂点を2次元座標に配置することを思い付いて、そうすると組み合わせの網羅や距離の計算が if 文ではなくデータを中心に構成できたので、解答の提出にまで至った。

 提出 #14892703 (AC / 1842 ms / 14560 KB)

N の上限が 2000 だから N×N(=400万)のループは TLE のおそれがあり、実際に 2 秒制限ギリギリだった。提出一覧を見たところ 100 ms は切れないみたいだが 500 ms くらいは普通に切りたい感じ。

  • 距離を求めるのに頂点を3つか4つにクラス分けすれば直接計算できるのではないか
  • クラスに属する頂点は連続する値を持っていて、求める距離も連続する範囲に分布するのではないか

というあたりでもうちょっと。


atcoder.jp/contests/abc16… すべてのiをBFSで最短距離出すところまではすぐ思いついたけど分岐する場所の計算がわからなくて敗北した

BFS とは思いもよらなかった。たぶんグリッドでなくほぼ直線だったからだろう。そういう先入観でプランBが見えなかった。

 提出 #14909026 (AC / 66 ms / 14388 KB)

期待以上に速くなった! 2桁ms!

すでに書いた通り頂点を4つにクラス分けして、始点4クラス×終点4クラスの場合に距離 k の頂点ペアがいくつになるかを計算した。計算は定数時間なので全体で k(=1..N-1) に比例した時間。

L[n][k] が主な道具。n 頂点で直線を作るときに距離 k の頂点ペアがいくつあるかを返す。

C[n][k] は n 頂点の円に対応する。頂点X,Yを除外する-4,-2 がアドホック。

k=1 の場合は例外。他と同じ式に組み込めなかった。


300 ms 台の人の十分に速くてシンプルな提出を見た>#14717011。長さ N の二重ループだった。ありうる2通りの距離のうち短い方を採用するだけだった。これをコンテスト時間中に書きたかったね。まあ、あとからでも書けなかったんだけど。

「2頂点間の最短パスは短絡辺を通るか通らないかのどちらかである」ということが最後まで見抜けなかったからなんだけど、それでも、何らかの方法で答えにたどり着きたかった。


たぶん Python のこの提出(#11387294)が自分と似た方針で同じようなコード構成だと思う。難しくてよくわからんけど。


2020年06月28日 (日)

最終更新: 2020-07-05T23:55+0900

[AtCoder] AtCoder Beginner Contest 172D 問題 Sum of Divisors

コンテスト全体については順当に、冴えない結果であった。あまり書くことがないので1つだけ。

 D 問題への Ruby による提出(実行時間昇順)

他が概ね 1000 ms ほどかけているところ、1つだけおよそ半分の 515 ms で済ませている>提出 #14757268

ループでは他と同じ式を使ってるんだけど、半分に割って足しているところが鮮やか。足し算の背後にある論理がわかりません。

N/2+1 から N までの数は掛ける2をするだけで N を超えてしまうので、その数自身しか数える必要がない、というあたりかな。ループの中の計算が必要ない。

こんな手の込んだことをしていながら提出時刻も早くて、Ruby の中では5番目なんだよね。一方の自分は、C 問題で脳死の愚直手続きスクリプトを書いていた>提出 #14743690。脳死のまま清書>提出 #14788308。ステートメントを減らそうとしてやりすぎた>提出 #14788890

 脳死といえば……

D 問題にも最初は脳死状態で挑んでいた。こういうスクリプト。

  1. N 要素の配列を 0 で初期化する。
  2. 1..N のそれぞれに対してそれ自身と倍数に対応する配列の要素を +1 する。
  3. 最後にその配列を使って K×f(K) (K=1..N) を計算して合計する。

でもサンプル3が親切にも N の上限値で、このやり方では時間がかかりすぎることに気付かせてくれた。さもなくばずぼらと拙速の代償として TLE を1個拝領していたことだろう。

 [AtCoder 参加感想] 2020/06/27:ABC 172 | maspyのHP

D 問題。問題と格子点の関連がさっぱりわからなかったのだけど、ループでシミュレートしてるΣ計算に N の一般式を与えようとしたときに、Σの中に整数除算があるから、反比例のグラフと軸のあいだの格子点の数に興味があるの? その前に、k*N/k*N/k を約分したり分解したりはできない?

 ABC172D - 西尾泰和のScrapbox

ところで、この縦に足す方法では、半分から先はどうせ1つしかないのにループを回して一つずつ足してしまう。ここを斜めに足せばループは半分で済む。しかしどうせ斜めに足すなら… 左上までしっかり斜めに足す。そうするとループの回数はルートNのオーダーになる。

画像が見えない(scrapbox も CSS を切らないと読めない)。まだ「斜めに足す」がわからない。√N のオーダーになるとは他所でも読んだが、わからなかった。

k*(N/k)*(N/k) の、N/k が1になるものだけを特別扱いするのでなく、2になるもの、3になるもの、4、5……で分けると定数係数としてΣの外に出せる(それとΣの区間も変化する)とか、そういう話なんだろうか。いや、どう書いてあるかはざっと読んだんだけど、読んだだけで解れば世話がないわけで……(あとでスクリプトにして確かめよう)。

 スクリプトにして提出したら 997 ms だったものが 68 ms になった。(比較のため Python だと 32 ms)

しかし明らかにもっとすっきり書く方法がありそうなんだよな、っていうかそれはすでに Python スクリプトとして示されてるんだけど、理解できないのです。

自分がやったのはすでに書いた通り、「N/k が1になるものだけを特別扱いするのでなく、2になるもの、3になるもの、4、5……で分けると定数係数としてΣの外に出せる」ということを利用して、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 の関係は通分したり約分したりできる関係ではたぶんないんだよね(答えが合わないから)。

 AtCoder Beginner Contest 172 D - Sum of Divisors - Crieit

図がわかりやすい。オーダーをちょっとずつ改善していく構成が付いて行きやすい。そして最後に見逃せないこれ>「なお、O(N^1/3)の方法もあるらしいです。

格子点のやり方がこのオーダーらしい。さっぱり想像がつかない

じゃあね、せっかくリンクを張って紹介してくれた先(「格子点の数え上げの高速化 - memo」)を読みましょうよ、って話なんだけど、高速化云々より前に格子点がどのように関わってくるのかがまず知りたいよね。

 格子点の数え上げの高速化 - memo

まずここから(わかんない)。

1 から n までの約数の個数の総和(つまり、y=n/x の第一象限内の格子点の個数)は 2i=1nni-n2 などを用いて計算することが多く

  • y=n/x と y=x の交点が (√n,√n)
  • y=n/x は y=x を軸にして対称
  • x=1..√n の範囲で y=n/x と y=x のあいだにある格子点を数えて2倍する? (たぶん y=x 上の格子点を一度だけ数えるよう気を配るのが面倒くさい)
  • x=1..√n の範囲で y=n/x と x 軸のあいだにある格子点を数えて2倍して、重複して数えた (1,1)から(√n,√n)を対角線とする正方形領域の格子点を引く
 「考え方」
  • 曲線上にある格子点が列挙できたら
  • 隣り合う格子点間を結んで斜辺とする各台形内の格子点を計算で求めるだけでいい
  • 斜辺上にある格子点にだけ注意してね(「傾きが既約分数の場合」)
  • 最初のステップの列挙には Stern–Brocot tree が使えるよ
 「求め方」
  • わかりません。ニュートン法みたいな試行を繰り返すの? むしろユークリッドの互除法?

 ループをまたいで式を整理した。

それというのも Python の方には2桁msの提出が1ページ以上もあって、オーダーは変わらないしブレもあるだろうとはいえ、28 ms と 32 ms のスクリプトのあいだには明らかに式の複雑さに差がある。

 Python によるすべての提出(実行時間昇順)

実行時間昇順で並べたときだけ自分の 32 ms の提出がリストされない。降順だったり提出時刻だったりでソートすれば現れる。消えているときは代わりに他の人の 32 ms の提出が2回リストされている。

32 ms の1つは自分のだが、28 ms は例えばこれ>提出 #14788253。平均タイムからして明らかに速い。

未だ及ばずながらだいぶ迫ったのではないか。

 これで最後。

最後に÷4するのにループの中で無駄に×4してるのが気になったので。

これを最適化というのではないか。この問題でしか意味のないループになった。少なくとも自分は式の意味を、途中からは理解していない。

実は最終版の while ループの中身は一番最初の 997 ms の提出とそっくりになっている。戻ってきた。

 Python のこの提出 #14841471

Ruby で書くとこんな感じ。

N = gets.to_i
p (1..Math.sqrt(N)).sum{|k|
	n = N/k
	k*n*(n+1)-k*k*k
}

違いを見比べると -k3 がループの中にあるか外にあるかの差なんだろう。Wikipedia による と i=1nk3=n(n+1)22 らしい。

k*[n*(n+1)-k*k] からは、何か、意味が読み取れそうな気がするね。数学力があれば見えるんだろうか。数学力があれば意味を保ったまま易々とたどり着けるんだろうか。

 結局これでいい。

ループ後のつじつま合わせの正体が -k3 だとわかったので……

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 の順で発見される。1対1対応ではない。