脳log[AtCoder: 2020-06-02～]

最終更新: 2020-06-18T09:50+0900

♪ [AtCoder] AtCoder Beginner Contest 006／D 問題 トランプ挿入ソート

ちょっと日記に書きたくなるような、適度に歯応えのある問題だった。問題は、例えば

2 4 6 1 3 5 

のような数列が与えられたときに、

1 2 3 4 5 6

のように昇順に並べ替えるためには、いくつの要素を移動する必要があるか、その最小を答えるというもの。

 1. 連続する２要素に注目して増加しているか減少しているか見てみたら？

例えば、「2 4 6」「1 3 5」の並びは２要素間の関係において増加しているのでそのまま温存して答えにできるのではないか、逆に、「6 1」の並びは減少しているので必ず介入して解消しなければいけない。

しかし２つの増加列の関係に注目すると、「2 4 6」と「1 3 5」の位置関係が前後しているために、 2 と 4 と 6 の３要素または 1 と 3 と 5 の３要素を移動しなければ答えになりそうにない。

 2. 数列全体から最長の増加列(※要素は連続してなくていい)を１つだけピックアップしたものが答えの一部になるのでは？

たとえば初期数列が以下の通りだったら、

5 6 7 1 2 3 4 8 9

できるだけ長くなるようにピックアップした増加列は「5 6 7 8 9」と「1 2 3 4 8 9」の２本で、最長は６。

移動せずに済ませられるのが６要素で、他は必ず(ちょうど挿入ソートがソート列の中に挿入先を探して移動するのと同じように)移動させられる。仮に長さ６の増加列が２本あっても、移動せずに済ませられるのは６要素だけ。

 3. どのようにして最長の増加列の長さを知るか。ツリーを作る？

たとえば、以下の初期数列に対して、先頭の要素から順に継ぎ足して木を作るとする。

1 3 2 5 4 6

しかしこれは網羅してないながらすでにして冗長。(画像ソース：verbose graph.dot)

ここが思案のしどころ。

1. ある要素の後ろにいくつの要素が続くかは、その要素の値によって決まる。
2. だから 4 と 5 と 6 が複数回出現しているが、最も深いところの１つ以外は無用。
3. くっつけられる場所を見つけるために、そのうちのどこにくっつけるのが最善かを知るために、都度都度葉を根まで(あるいは根から葉まで)たどるのはいかにも無駄。
4. 知りたいのは深さだけ、それも最大の。中途半端はいらないし、経路もいらない。
5. どの枝がどれだけ伸びうるかは 1 に書いた通り。さらに言えば値は小さいほど良く、小が大を兼ねる。
6. 深さごとに最善の要素(最小の値)を１つ記憶しておけば足りる。
7. たとえば上の画像に対応する作業配列は [1,2,4,6] になる。２番目の深さにおいて最善の要素は 2 であり、その他の 3, 4, 5 の後ろが 2 の後ろより長くなることはない。

8. 新しい要素は作業配列の末尾に付け加えられたり、既存の要素をより小さい値で置き換えたりする。

   数列を先頭から処理するときの作業配列の変遷：[1] → [1,3] → [1,2] → [1,2,5] → [1,2,4] → [1,2,4,6]

 提出 #13936266 (AC / 227 ms / 4348 KB)

提出一覧を見ると 227 ms というのはいかにも遅い。

「Ruby による提出(実行時間昇順)」

ちらちらスクリプトの中身を見てると、二分探索の使用が目につく。それで気をつけて作業配列を見てみると、どの時点でもソート済みの状態が保たれているようだった。

できるだけ増加列の長さを伸ばしたいから、作業配列の末尾から更新位置を探していたし、更新位置が見つからない場合も想定していたけど、どちらにも無駄があった。位置探索はソート済みなのを活かして対数時間で済ませられるし、書き込む位置は必ず見つかる。

たぶん値の重複のあるなしで二分探索の使い方が変わるけど、この問題では重複なしが制約に含まれている。最近「bsearch_index の使い分けが見事」と評したのはこの提出>#13393878。lower_bound とか upper_bound とか -1 とか。Ruby には区別がないけど。

 提出 #13936659 (AC / 41 ms / 2556 KB)

凡人は一足飛びに答えにたどり着いたりはしない。しかしたどり着ける難易度ではあり、さらには提出した後でも発見があった。思わず日記に書きたくなる楽しさ。

 AtCoder Beginner Contest 165／F 問題 LIS on Tree

特になんということもなかった。作業配列を深さ優先探索のあいだ使い回しするだけだった。

 提出 #14435898 (AC / 707 ms / 259260 KB)

問題名で解説記事を検索してみると、LIS(※) に関して色々な方法があるなかで、自分が唯一知っている方法がぴたりとはまる幸運があったと言えそう。

※トランプ挿入ソートの解説記事を読むといやでも目に入るよね>LIS。ストレートな知識問題だって書いてるところがあったけど、知らなくても解けるし、むしろ問題を通して教えてもらえる、ありがたくも教育的な問題だった。

最終更新: 2020-07-10T21:58+0900

♪ [AtCoder] AtCoder Beginner Contest 006／B 問題 トリボナッチ数列

「Ruby による提出(実行時間昇順)」

２番目が 60 ms のところ、１番速い提出が 16 ms で済ませてしまっている。いったいどんな魔法を使ったのか、読んでみた。

 提出 #1163397 (nejiko96 さん / 16 ms / 4732 KB)

といっても、require 'matrix' して pow(power 累乗) して mul(multiply 乗算) してるだけに見える。優れたコードはストレートで無駄がない。あえて mul を定義しているのは途中で mod を取りたいからなのかなんなのか。

require 'matrix' には NArray や NumPy で得られるような恩恵はないと思う。累乗の高速化手法に掛け算の回数をおよそ log2(N) 回に減らす方法があって、最初の掛け算で２乗を作り、次に２乗と２乗で４乗を作り、という感じに倍々で N 乗に迫っていく。

途中の式がどんな掛け算と足し算と係数になるか想像もできないけど、トリボナッチ数列の第 N+3 項を求めるための N 回の計算を約 log2(N) 回に縮めるための行列であり、pow メソッドであるのだと思う。

これぞ線形代数って感じ(すくなくとも自分がイメージできる範囲の)。

 Tribonacci Numbers - GeeksforGeeks

素朴な手法から順番に紹介されている。1.再帰 2.配列メモ 3.三変数使い回し 4.行列の累乗

1. A simple solution is to simply follow recursive formula and write recursive code for it,
2. Time complexity of above solution is exponential. A better solution is to use Dynamic Programming.
3. Time complexity of above is linear, but it requires extra space. We can optimizes space used in above solution using three variables to keep track of previous three numbers.
4. Below is more efficient solution using matrix exponentiation.

 蟻本にはすべてがあるような気がしてくるな。

実際は自分の到達点の低さの反映に過ぎない。

最初に読んだときは動的計画法のラッシュで頭がパンクして「もういいです……」と本を閉じた。

その次に開いたときは実装したことのあるグラフアルゴリズムの登場に気をよくしていたところで、ここからが中級だ、と新しいチャプターが始まって、「もう無理です……」と本を閉じた。

182ページのコラムから

もっと高速な漸化式の計算

実は、m 項間漸化式の n 項目は行列を用いるのではなく、各項を初項の線形結合で表して繰り返し二乗法を行うことにより、O(m^2log(n)) で計算することも可能です。興味のある人は考えてみるとよいでしょう。

最終更新: 2020-05-31T18:32+0900

♪ [AtCoder] NOMURA プログラミングコンテスト 2020／C 問題 Folia

こんな非道な仕打ちがあるだろうか。

AC AC AC AC AC AC AC AC AC AC AC AC AC AC AC AC AC AC AC AC AC AC AC AC AC AC AC WA AC AC AC AC AC AC AC AC AC AC AC AC AC

最初の提出(#13737796)が MLE と WA であって、コンテスト終了30秒前で MLE の解消はできたのだけど、ひとつだけの WA が WA のまま残ってしまったと。

 提出 #13742470 (WA)

600点問題は解ける解けないの山が最初にあって、どちらかといえば時間をかけてもほとんど解けないのだけど、それだけに恨めしい。

 N よ！ お前か！ 提出 #13747866 (AC / 91 ms / 22960 KB)

N の制約「0≤N≤10^5」 0 以上

 leaf の複数形は leaves です。

どうしても完全丸ぱくりになるので提出する気がなくなったけど、N=0 の場合を特別扱いせずに対応できるようにループの中身を半分ずらしたり、配列 B を後ろから前から往復して値を埋め込んでいる処理を２種類の累計値を管理するだけで済ませたりできる。そうすると最後の答えを出すのに sum メソッドもいらない。

最終更新: 2020-05-26T21:01+0900

♪ [AtCoder] AtCoder Beginner Contest 168／F 問題 . (Single Dot)

解説PDFが奮ってる。これが全文。

x 座標・y 座標それぞれを重複を除いてソートし，十分なサイズの2 次元グリッド上に各線分を刻 み込んでからBFS すれば，O(NM) 時間となって十分間に合います．

座標値(-10^9 以上 10^9 以下の整数)でなく座標値の序列(N個以下とM個以下)でグリッドを作るって発想が出てこないんだよなあ。

さらにこんな工夫も。「F問題は座標圧縮してグリッドグラフ上のBFSにしたいんだけど、こんな感じで、線の幅(=0)のマス目を仮想的に作ってあげると、面積は4倍になるけど、線がマス目の塗りつぶしで表現できるかららくちんになるよ。 pic.twitter.com/ZpX0hxGQjC」

そんなこと知らずに、重なってる線分を連結して、交点を列挙して、閉路(多角形)を見つけ出して、包含関係を判定して、多角形の面積の引き算で求めようとしてた。しかも閉路の列挙に関するバグが取り切れなくて完成しない。完成しても間違いなく TLE(Time Limit Exceeded) だし。

 C 問題が理由で「余弦定理」がトレンド入りしていたらしい。

名前が出てこないと検索も何もできないよね、この前の「逆元」「モジュラ逆数」みたいなもので(20191118p01)。自分は弧度法への変換だけして Ruby の Complex クラスに投げた(polar, 引き算, abs)。組み込みクラスなので使ってあげよう。

 F 問題。最初の提出 #13402510 (WA)

方針を教えてもらっても実装できるかどうかは別問題なわけで……。座標のグリッド化に際して線分の端点を切り詰め忘れて大量の WA。

 ３番目の提出 #13404210 (TLE)

２番目の提出はデバッグ出力を消し忘れて全部 WA だった。デバッグ出力を標準エラーに出すようにするといろいろ捗るらしいが。

線分の切り詰めバグを修正したら WA だったものがすべて AC か TLE になった。メモリ使用量が百数十MBを超えるテストケースがすべて TLE になっており、AC ケースのメモリ使用量は概ねそれ以下。無限ループ内でメモリリークでもないと思うから、単純に時間が足りないだけだと思いたい。

 現在 Ruby で AC してる人が一人だけいる！

555 ms！>「すべての提出 - AtCoder Beginner Contest 168」

 やったぜ！ #13406078 (AC / 2489 ms / 50112 KB)

diff をとらんとわからんくらいの微修正で全部 AC。バグはなかった。

TLE になった手法はこのときの成功体験を再現しようとしたものだった>20191006p01。たぶん今回は問題の規模が大きすぎて裏目に出たんだろう。

Ruby で２人目の AC なのは嬉しいけど、こちらは 2489 ms もかかってるんだよなあ。ソースコードも長いし、メモリも余計に使ってる。早期に INF を判定して終了すれば一部のケースで速くなるかもだけど、最悪ケースの改善にはならないんだよなあ。事前にデータを作り込むんでなく、インテリジェントなアクセス関数を通して仮想的なデータにアクセスする手法ならレイテンシは下がりそう。スループットも下がりそうではあるが。そんなこんなより面積４倍のオーバーヘッドが効いてるんかなあ。

 面積４倍を解消しても…… 提出 #13413181 (AC / 1460 ms / 22892 KB)

555 ms は驚異のタイムだよなあ。移動可能判定を検索でやってるのがまずダメなんだけど(メモリ使用量は減った)。

Python の AC 提出一覧がこちら>「すべての提出 - AtCoder Beginner Contest 168」 ほぼ一人の独壇場なんだけど、タイムの縮みかたがエグい。2488 ms から始まって 131 ms に至る。

「[AtCoder 参加感想] 2020/05/18:ABC 168 | maspyのHP」

 面積４倍でも

さっきの提出は一から書き直して面積４倍確保を解消したけど、面積４倍のグリッドを作ったままでもグリッド線上を飛び越えて移動するようにすればデメリットは解消する。牛がグリッド線上にいる場合にだけ注意すれば。

 Ruby で 555 ms の人のスクリプトを読んだ。

特別な工夫は見つけられなかったけど、必要のないことはやってない印象。bsearch_index の使い分けが見事。

翻って自分のスクリプト。o を埋めたり、Infinity を埋めたり、座標丸め関数を４方向分用意したり、各グリッドの面積をすべて事前計算して記憶したり、省けるなら省きたいところに文字数と処理時間とメモリを費やしている。未熟で不安があるから冗舌になる。『テスト駆動開発』(ケント ベック)の表現を借りれば「ステップを刻む」「歩幅は変えられる」。今の自分は細かく刻まなければ進めないということ。

 提出 #13454965 (AC / 474 ms / 43092 KB)

ぱくりです。写経。見比べて書いたわけではないけど、アイデアが同じなら同じになるでしょう。後で見たら PyPy3 で速い提出も同じ道具立てだった。

接続してる線分をまとめたり、交点のない線分を取り除いてからグリッドを作りたい気持ちがあるけど、見込まれる処理の重さに比して改善する度合いが入力依存でゼロになるとあって、何かのついでで棚ぼた的に交点一覧とグリッド座標化された線分一覧が手に入らないかなと夢想してる。

最終更新: 2020-10-29T15:09+0900

♪ [AtCoder] AtCoder Beginner Contest 167／F 問題 Bracket Sequencing

 わからない。提出 #13147757 (WA)

解説 PDF で考え違いを教えてもらおうと思ったら解説動画しかなくて、うんまあ、じゃあいいや。(追記) 13日の現在はPDFもあるみたい。

これを読んでも間違っているとされている定義のどこに問題があるのかわからんのだよね。果たしてそれで解けるものか。>「競プロでよくある「バランスのとれた括弧列」の定義が壊れがちな話 - notブログ」

 まだわからない。提出 #13156522 (WA)

正規表現の ? を * に変えたことで、AC は増えたけどまだ WA がある。

こういう生成スクリプトでテストした結果、最初の提出で使用した正規表現パターンに問題が見つかった。

def puts s
	re = /(?<p>\(\g<p>?\))/ # バグあり。提出 #13147757 より。
	re = /(?<p>\(\g<p>*\))/ # 意図通り。提出 #13156522 より。
	t = s.gsub(re,'')
	print "#{t.empty?}:\t#{s}\t#{t}\n"
end

L,R = '('*5,')'*5
10.times{
	puts L+((L+R).chars.shuffle.join(''))+R
}

LR = '()'
10.times{
	puts 10.times.inject(''){|s,| s.insert(rand(s.size+1),LR) }
}

そうするともう、提出したスクリプトは完全に自分の意図通りに動作しているはずなんだけど、WA がある。書き間違いではなく、考え違いがある。

 そっか、)( 型の s を連結する順番によって結果が変わる。

)))( と )((( の２つの s があるとき、連結のしかたによって )))((( が残る場合と )( が残る場合に分かれる。)( を残した方が 'Yes' と答えられる確率が高くなる。

 提出 #13158713 (AC / 1014 ms / 16076 KB)

 バグがありますよ。)( 型の文字列が１つだけのときに必ず No と答えてしまいそう。

今現在 Ruby で一番速い提出は 498 ms だ。>すべての提出 - AtCoder Beginner Contest 167

再帰ありの正規表現(※矛盾した表現)を使ってる時点で勝ち目はない。左括弧の数が負になれないのに気をつけながら、左括弧と右括弧を対消滅させながら、左括弧と右括弧がいくつ残るかを数えればいいんだろうけども。

 問題はそこではなかった。>提出 #13160001 (AC / 821 ms / 14380 KB)

しかたない、省メモリを売りにしていこう。>すべての提出 - AtCoder Beginner Contest 167

ソートを必要としてないあたりで(※)ちょっとは有利を得てもよさそうなもんなんだけど、トップの提出はソート対象を )( 型に限るなどしてる。※ループ内で２要素のソートもあかんか？

 これが限界>提出 #13174623 (AC / 533 ms / 14308 KB)

 ちなみに

( 型の文字列を最優先に、)( 型のうち ( 優位のものを優先的に、最後に ) 型を、という感じで連結していくのがストレートな解答らしい。

３つの型の文字列を統一的にソートすることもできるし、)( 型だけソートしてもいい。

自分はどれもソートしてないんだけど、)( 型の中から１番目と２番目に条件のいい文字列をピックアップするための比較演算()( 型の文字列１つにつき１～２回)が重くてソートした方が速い。

 @2020-10-29 提出 #17712418 (AC / 391 Byte / 377 ms / 19604 KB)

(ゴルフ勢を除けば)わりと短くてそこそこ省メモリで今のところ Ruby で一番速い。すべては正規表現エンジンとそれを使う gsub のちから。

やってる内容は最初の AC と変わらない。入力をがばっとひとまとめに処理するようにしたのと、最小２要素を取り出すのに一度全体を配列に蓄えてから min メソッドを使うようにしただけ。

最終更新: 2020-05-29T19:43+0900

♪ [AtCoder] AtCoder Beginner Contest 165／D 問題 Floor Function

数弱さんには厳しい回だった。E 問題は読む時間さえなかったので今日の日記は D 問題。次の整数式を考察するだけ。

x*A/B - x/B*A

A を掛けてから B で整数除算するか、B で整数除算してから A を掛けるかという違いで生じる値の差について。その最大。

 1. x が大きいほど大きいんじゃないの？>提出 #12618779

違います。B を周期として第一項と第二項が一致します。A がその周期に与える影響はよくわかりません。

ちなみに B の上限は 10^{12} のため周期全体をテストすることはできません。>提出 #12633357

 2. x が B の倍数マイナス１のとき第二項の整数除算で切り捨てられる値が最大になるんじゃないの？

• →引き算される第二項が相対的に小さくなる
• →全体として大きくなる

たぶんその通り。だけど説明を端折った N との関係がわかんなかったのと、A と B の因数によって第一項と第二項で周期 B の位相がずれていくんじゃないかという気がしたので探索した。>提出 #12640433。でも錯覚。位相がずれるなら「B を周期として第一項と第二項が一致します」が嘘じゃんねえ。

Ruby で提出している他の人は、提出の早さも実行速度も優秀だった。>すべての提出 - AtCoder Beginner Contest 165

 B 問題 1%

実は B 問題で15分近く詰まっていた。瞬殺できないとあせる。最初は(もはやうろ覚えの) log を使って計算していた。

X = gets.to_i
p ((Math.log(X) - Math.log(100)) / (Math.log(101) - Math.log(100))).ceil

でも大まかにしか数字が一致しない。同じかちょっと小さい数字になる。俺が log を忘れているか浮動小数点数の誤差か(近い数字の引き算とか良くないのでは？)これの影響じゃないかと>「(複利、小数点以下切り捨て)」。複利の計算をするごとに切り捨てなければいけないのでは？

B 問題なので手続き的に解いても TLE にならないのはわかっていた>提出 #12601266

 C 問題 Many Requirements

実は C 問題でも30分近く詰まっていた。A 数列の総当たりでいこうと決めるまでに制約条件を総当たりしようとしていて、他の制約にまったく制約されない孤立した制約条件の扱いをうだうだ考えていた。

再帰をループにするとかの効率を考えずにちゃっちゃと書いただけなので、提出へのリンクはなし。

上手い人のゲームプレイ動画と AtCoder の解説 PDF のあいだの共通点。多様性のなさ。へたくその動画の方がバラエティに富んでいて見ていて面白くさえある。間違え方というのは本当に千差万別で、ありとあらゆる機会を逃さずに、そう来るかと予想もできない脱線をする。たったひとつのゴールに向かう限られたルートに収斂していくということがない。

当人にとっては面白くもなんともないので、B 問題、C 問題に詰まらないような世界線に乗っていきたい。

 あ、この問題ってそういう見かたができるのか。>小数部を分離

chokudai(高橋 直大)🌸🍆 Verified Account @chokudai

とはいえ、高度な問題を解く時に、「floorが出てきたら整数部と小数部に分離して式変形！」って結構大切な考え方なので、Dみたいなのを出さないと、後半問題で突然そういう数学力が応用状態で問われることになるので、そのあたりの塩梅がむずかしいよね。

x が固定小数点数で小数部が５桁なら、x - x/100000*100000 が小数部分になる。……という話ではない？ D 問題を解くときの話？

以前にもはっとさせられたことがあった。

kを使った場合のコストは、k-1以下のすべてを使ったコストより高い

これって要は 100000 > 11111 (２進数) と同じことなんだけど、自分のような人間は「この一連の操作のコストは（書き換えた要素の数によらず）2^k である」という問題文を読んだだけではたどり着けなくて、上のように事実として示されて２進数で考えてみて初めて了解できることだったりする。

「一を聞いて十を知る(20200508)」ってこういうことだと思う。賢い人は「いやそれって同じことだから一の内に入るのでは？」と思うかもしれないけど、全然違うのである。

そして自分が AGC022C 700点問題 にまるで歯が立たない理由には、列挙された要素の数とそれらを煮詰める段階の深さに関係があると思ってる。「理解が及ぶ広さ、深さ、早さに優れ(20200508)」という風に書いたけども、そうでない自分は頭の中で抱えきれないし、整理して外に出して部分ごとに解決することもできない。

アストロノーカやテラリアですでに知ってるんだけど、ツリー状にねずみ算式に倍々に増えていく要求リソースの全体を把握すること、並列に進行する精製過程をストールさせないように需給を絶えず調整すること、このサプライチェーンの階層がある程度以上になると(たぶん３くらい)完全にお手上げになってしまう。そういう能力がない。

「たぶん３くらい」 深さが３、二分木なら葉の数８までしか脳内で扱えないんです。

 「アルゴリズム格言」

ちょっと検索したら「銀の格言」としてこんなのが列挙されてる。

• 攻めは銀、受けは金
• 銀は千鳥に使え
• 桂頭の銀定跡なり
• 銀は成らずに好手あり

つまりはこういうことなんでしょう？

chokudai(高橋 直大)🌸🍆 Verified Account @chokudai

「この問題だったらこうするだろ」って感じに無意識にやってることってめちゃめちゃ多くて、その「無意識」を言語化して列挙するだけでもめちゃめちゃ有効だと思うのよねえ。

chokudai(高橋 直大)🌸🍆 Verified Account @chokudai

「chokudaiのアルゴリズム格言1000」とか作って、こういうのをひたすら列挙しまくると、格言の組み合わせだけで良い感じに解ける問題がたくさんできそうだな、と思っていて、アルゴリズム名とは別レイヤーで浸透させたいな、ってちょっと思ってる。

「解説なんかだと、正しいルート以外はすっ飛ばされちゃう」というのがまさしく今日書いたことで(20200502p01.04)、解説PDFよりも「競技プログラミングの強みと「典型力」について - chokudaiのブログ」という思考の跡が見えるブログ記事の方が自分には有用となる理由。アルゴリズム格言に期待する理由。

最終更新: 2020-06-15T20:02+0900

♪ [AtCoder] AtCoder Beginner Contest 164／E 問題 Two Currencies

日付のあたりに書いた通り解説PDFを読んで実装した。だけどあれ全然答えじゃないね。Chokudai さんのブログで以前読んだような、ちょっとひねってあるのをいかにして典型問題に落とし込むかというタイプの問題だったらしい。ある意味そこまで含めて典型では。でも一度も実装したことのないパターンだから「(現在の頂点, 所持している銀貨の枚数) を状態としてdijkstra 法を適用すると、(略) 解くことができます。」とだけ書かれても、～を状態とするってどういうことですか？

 提出 #12489199 (TLE / 2206 ms / 19760 KB)

Wikipedia の「ダイクストラ法」を読みながら雰囲気でPDFに書いてあった方針で実装しようとした。一応答えは出たがサンプル入力ですら一瞬の間を感じさせる激遅スクリプト。

N 個の頂点と銀貨の枚数を組み合わせて状態にするといっても、訪れなければいけない地点は依然として N 個のままなわけで、そのあたりの状態を集約する手つきが具体化できなかった。最終的に提出したスクリプトで「すべての地点を一度でも訪れた時点で完了」としたところとか、「銭なしの再訪に用なし」とコメントしたあたりがそうだと思うんだけど。

苦しんで何度か書き直すうちに原型を失いつつもすっきり書けて、プロファイルをとりながらの実行もすっきりだったから「どうだ！」と提出したら、AC の中１つだけが TLE で脱力。これ以上は無理ですよ。

この段階で他の人の提出を見た>「すべての提出 - AtCoder Beginner Contest 164」。

Ruby での全提出は１ページに収まるほどで、AC していたのは２人だけ。TLE 仲間の提出を覗いてみれば、自分が TLE になった入力(とサンプル)だけ AC していたりして、line_2.txt が何と癖の強い入力であることか。

 提出 #12498094 (AC / 205 ms / 14528 KB)

ダイクストラ法に立ち返らないといけないかと思っていたが、diff をとらないと判らないレベルのチューニングでなんとかなった。不思議。

要修正その１

M.times.map の .map がいらない。

.each の短縮形として .map と書くことがあるみたいだけど、.times (ブロックを受け取る)があるのでここではただの無駄。定数 E で map を受けていたときのなごり。

要修正その２

PQ#deq の変数名 max は min の誤り。

プライオリティキューが必要になるたびにこのとき(20190916p01)の max-heap を使った実装を書き換えて使ってるせい。必要になるのはほぼ min-heap。符号を反転させてそのまま使うのと手間はどっこいどっこい。

 ところで、Python (3.8.2) で今一番速いのがこれ>提出 #12430772 (140 ms)

すっごく読みやすいんだよなあ。何をやっているのか手に取るようにわかる(笑)。配列総なめが嫌だからって冗長なカウンター変数を用意するところまで。

自分に欠けていた工夫が２つあって、

1. ある頂点から出る辺を予めソートしておいて、除外条件に一度引っ掛かれば以降の辺をまとめて無視してる。
2. 効果のないちまちました両替をひとまとめにしてる。(ソートした辺がここでも役に立っている)

特に２番目は効果が大きいんじゃないかなあ。キューへの出し入れがボトルネックだから、エンキューをひとつ節約するごとにそこから波及する複数のエンキューが節約されるのは大きい。

それはそれとして、Python は AC だけに限っても５ページの提出があるのがうらやましい。傾向として判で押したように似たような提出が多くはあるが。理由のひとつはヒープ(データ構造)とかダイクストラ法とか、名前のついたアルゴリズムが簡単に利用できるところにある。

 Ruby (2.7.1) のこの提出>提出 #12467639

読めない記述がある。この行

  (v = V[n]&.&SM) ? (next if v>=s || v>2500) : R << [n,t]

演算子(に見えるがメソッド)をドット記法で呼び出せる(それが結合規則を変えるのでゴルフに使える)というのは読んだことがあって、たとえば 1&3 と 1.&(3) は同じ意味になる。でも &.& をどう解釈すればよいか。SM はただの数値変数だからブロック引数化の & ではないと思う。

他にもアロー記法だとか、暗黙のブロック変数(_1, _2 とか)だとか、Ruby 2.7 を読むには知識が足りない。ローカルにインストールしている Ruby 2.5 ではまだ使えない記法だったりする。まだ gem コマンドを一度も使ったことがないから、デフォルト添付ライブラリ(prime とか)の gem 化は歓迎できない？。

ブロック変数には悩ましいところがあって、.map(&f) とか .map(&:to_i) とか書けるときには積極的に書いていきたいんだけど、.to_i ではなく .to_i(2) を適用したくなると途端に .map{|_|_.to_i(2)} と書かなければいけなくなる。.to_i に 2 (と self)を予め束縛した関数がサッと(記述コストと実行コストなしに)利用できるといいんだけど、なかなかそうもいかないらしく、とりあえず .map{_1.to_i(2)} と書けますよ、ということ。たぶん。まだ試したことない。

 「メソッド呼び出しで `.' の代わりに `&.' を使うことができます。この形式でメソッドを呼びだそうとすると、レシーバが nil の場合は以下のように働きます。」

• 引数の評価が行なわれない
• メソッド呼び出しが行われない
• nil を返す

&.& が何だったかと言えば、nil テストを含んだ & 演算だったと。Swift とか C# にあるやつじゃない？ どっちも使わんしよう知らんけど。

 提出 #12550661 (AC / 154 ms / 14520 KB)

51 ms 縮まったけど本質的な改善ではないと思う(配列４とか比較が雑で適応が限られるし、ない方がいいかも)。シンプルさも失われていいことない。しかも Python (140 ms) に負けてる！ Ruby のバージョンが 2.3 から 2.7 になって、実行前のオーバーヘッドが 40 ms ほど大きくなったと思うんだよなあ(それでも勝ちたい。ユーザー数で負けても質で勝ちたい)。

 参考にされた！>提出 #12916854 (146 ms)

嬉しい！ 自分で解釈して手を動かして理解してる！ 立派！ 自分で好き勝手書くより他人の考えをトレースする方が難しいものよ。

タイムが縮んでるのはホットスポットである PQ#up_heap (PriorityQueue#update_heap_to_up) で配列アクセスを減らしてるからなんだろうか。キューが長くなるほど効果があると思う。

あと自分は意味まとまりのある変数群を一行で定義するために多重代入を多用するんだけど、実は字数が減るわけではないし、多重代入式に対応する配列値が作り捨てられているとしたら、もったいないことをしてる。

地味に変数の定義位置をずらして無駄な計算を減らしたりもしてる。自分は変数の定義をひとつにしたいがために効果のない値([0,0] とか)を使用して効果のない加算を実行してたりするんだけど、贅沢ではある。関連>20181029。

 改善点みっけ

(自分の提出だよ)

	z, y = ２[v]+a, ３[v]+a # z < y
	if z < s
		c, d = s < y ? X[v][s-a,３[v]] : [0,0]

X[v] が返す関数が受け取る引数２つ(s-a と ３[v])はその差だけに意味があるから、両方に a を足して、X[v][s,y] とすると引き算１つと配列アクセス１つが省略できる。そもそもが引数が２つある冗長性から生じた無駄であるな。

こういう楽しみがあるのはスクリプトならではなんだよなあ。C++ コンパイラにかかると本質的でない差異は全部同じにされてしまう。そこに性能を犠牲にせずに読みやすい表記を追求する余地があるとも見られるんだけど。

 即セルフツッコミ「C++ コンパイラにかかると本質的でない差異は全部同じにされてしまう。」

もう一度asmコードをよく読むと不要なはずの配列の初期化が走ってる模様. デフォルトcstrは空のはずなんだけどと自分のコードを見直すと、FpDblクラスだけ配列の初期化が入っていた.

うっかりいれちゃっていた模様. 削除するとgcc-7.5で13%高速化. おおこいつのせいだったのか. それでもclang-8より4%ほど遅いけど気がすっきりした. でも配列の初期化で1割変わるというのは(clangは速いだけに)何か変なことしてるのかな.

プログラマに指示されたらコンパイラは無視できない(こともある？ clang の場合をどう解釈する？)。結果に影響しない表面上はささいに見える違いが思わぬペナルティを生むことも。

 実装比較。この件>>20200428p01.07

• 提出 #13001464 (1349 ms) 自分のプライオリティキュー実装を利用した richvote さんの提出。
• 提出 #13001205 (1273 ms) 自分のプライオリティキュー実装を基にした？ yappy0625 さんの実装を利用した richvote さんの提出。

プライオリティキューの実装が違うだけで、メインループは共通して richvote さんのオリジナル。

richvote さんの提出は、自分が最初唯一の TLE を食らった line_2.txt という入力が際立って他のケースより速いため、明らかに異なる部分に着目して探索の優先順位を決めている。

それはさておいて、俺の目には２つのプライオリティキュー実装に違いがあるとは見えないんだけど、俺の書き方の方が遅いという傾向が間違いなくあるようだ。

loop{} と書くより while 0; end と書く方が速いというように、気をつけておくと得する書き方がまだあるみたい。だけどわからん。

 多重代入と代入

require 'benchmark'

N = 10_000_000
Benchmark.bm{|x|
	x.report('多重'){ N.times{ a,b,c = 1,2,3 } }
	x.report('代入'){ N.times{ a=1;b=2;c=3 } }
}

これを Ruby 2.5 で実行してみた。

> ruby25 a.rb
       user     system      total        real
多重  1.591000   0.000000   1.591000 (  1.585992)
代入  0.967000   0.000000   0.967000 (  0.969697)

多重代入遅いなあ。(bm メソッドを bmbm に変更してリハーサルを行っても同じ結果)

あと最近驚いて、確かめてみたら Ruby 1.8 の昔から一貫して同じ挙動だったんだけど、多重代入の評価順って、単純に右辺から左辺とか、カンマで区切られた左から右ではないみたい。次のスクリプトの実行結果に驚いた。

i, a = 0, [0,1,2] # 準備
i, a[i] = 2, i # どうなる？
puts "i=#{i}; a=#{a.inspect}" #=> i=2; a=[0, 1, 0]

最初に右辺を評価して、それから左辺の評価と代入を左から順番に実行していく感じかな？ 右辺の一時記憶が必要？

多重代入は遅くて時々評価順が難しい、というのが現在の評価。

最終更新: 2020-05-06T23:27+0900

♪ [AtCoder] パナソニックプログラミングコンテスト2020／C 問題 Sqrt Inequality

コンテストの配点を見るに ABC 互換。B is for Beginner.

 まず間違えた。「提出 #10843998」

入力が整数なので戻り値が Float になる Math.sqrt は使いたくなかった。ふわふわした浮動小数点よりかっちりした固定小数点が好き。三角不等式みたいな高校時代に知ったような単語が思い浮かんだが関係するかは知らない。両辺を二乗して不等号が維持されるかどうかが気になった。すべてルート付きで正の実数だから大丈夫。

で、１つだけ WA(Wrong Answer)。

こういうことだ。ルート付きの元の不等式が成立するとき、両辺を二乗した不等式も成立する。でも逆は？ 二乗した不等式が成立することは提出したスクリプトで確認した。そのときルート付きの不等式はどうだ？

数学とは便利なもので、イメージが湧かなくても途中の式変形で同値関係さえ確認していけば答えにたどり着いた。実は二乗する操作を２回やっていて、２回目のチェックが疎かになっていた。「提出 #10855551」

とっても高校生向けだと思う。大学入試で同値関係の証明を求められるもんね。そのとき一方通行では道半ば。

最終更新: 2020-05-06T23:27+0900

♪ [AtCoder] AtCoder Beginner Contest 145／D問題 Knight

階乗が法外な大きさになるので余りを答える問題。割り算を含む式の余りが求められなかった。もちろん階乗を計算しきってから余りを求めるというのは実行制限に引っかかるので無理。

 #AtCoder から見つけたヒント

モジューラ逆数っていうのがあるんですね、これはすごい pow(down,mod-2,mod) 昨日のD問題逆元の計算どうやればいいのかわからなくて1時間くらい経ってしまった

AtcoderのABC145D問題しっかり理解して頭の中整理してすっきりかけた気がする。Python3です。 pic.twitter.com/Dcs3IfoZ95

mod って演習込みでイチから習った記憶がない。「割った余りですよ」以上の理解がない。キーワードすら知らなくてググりようがない。

 キーワード

• 「逆元 - Wikipedia」
• 「モジュラ逆数 - Wikipedia」
• 「ユークリッドの互除法 - Wikipedia」
• 「ベズーの等式 - Wikipedia」

Ruby には Python と違って「冪剰余 - Wikipedia」が求められる関数が用意されていないみたいなので(※補足訂正)、拡張ユークリッド互除法を使う方の求め方を Wikipedia(ja) からコピペ実装した>https://atcoder.jp/contests/abc145/submissions/8508807。明日には理解できないとしても「モジュラ逆数」というものの存在くらいは覚えておきたい。

 現在 Ruby で最速の提出(55 ms)>提出 #8501110 - AtCoder Beginner Contest 145

速いからには変わったことをしてる。derive_inverse メソッドが理解できない。法のビットを利用しているみたい。理解できないのは本質を掴んでいないから、演繹が働かないからだろう。「冪剰余#さらなる最適化 - Wikipedia」を実装してるのだろうか、雰囲気的に。

pow メソッドを使って実装された derive_inverse がコメントアウトして残されている。

 Ruby で冪乗余

試したら Ruby 2.5 には冪乗余が求められる Integer#pow メソッドが用意されていた。2.6 の「数値関連のメソッドを実際に定義しているクラス一覧」には載ってなかったんだよなあ。Ruby 1.9 時点では pow メソッドはなかった。AtCoder の 2.3 でもまだないかもしれない。

 方法色々

つらつら眺めてると、require 'matrix' して lup.solve で勝手に方程式を解いてもらえるとか、require 'openssl' すると mod_inverse が利用できるとか、知らない方法が色々あるもんだ。でも LUP 分解が解らなければ見ても使うべきときが判らないし、知っても使えない。『[単行本] 平岡 和幸, 堀 玄【プログラミングのための線形代数】 オーム社』は中座してるし、『[単行本] ロナルド・L. グレアム, オーレン パタシュニク, ドナルド・E. クヌース【コンピュータの数学】 共立出版』もちょっと眺めただけ。若いうちに学校で広く浅くでも詰め込んでおくべきなんだよ。基礎がないと何も積み上がらない。

最終更新: 2020-08-27T19:59+0900

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

解けなかった。まだ解けていない。考慮すべきが漏れてるのか、何か思い違いがあるのか。

とりあえず、完全に並べ替えても題意を満たせないケースに No を返してみた。該当(AC)１件>https://atcoder.jp/contests/nikkei2019-2-qual/submissions/8356932。

 N-2 回の交換

N-1 回の交換だと N 要素の A 数列を完全に思い通りに並べ替えられると思った。ぎりぎり１回足りないのが N-2 回なのかな、と。

ぎりぎり１回足りない条件とは？

A 数列のすべての要素があるべき位置から外れた状態にあり、A 数列のすべての要素が数珠つなぎに位置を交換している、だと思った。

 1. A 数列のすべての要素にあるべき位置が存在する(B 数列にあって対応する要素が１つだけしか存在しない)とは

ソート済みの A 数列のどの隣接要素を入れ替えても題意を満たせなくなることだと思った。

逆の例は、B 数列に重複する値が存在する場合や、B 数列の最小要素以下の要素が A 数列に複数ある場合など。その場合は A 数列に区別が不要な要素が存在するということであり、交換回数を節約できてしまう気がした。

 2. A 数列のすべての要素が数珠つなぎに位置を交換しているとは

これもそうではない例を考えると、A 数列が k 要素と N-k 要素の２グループに分かれて位置を交換している場合が該当する。k 要素をあるべき位置に並べ替えるのに k-1 回の交換を要し、N-k 要素を並べ替えるのに N-k-1 回の交換を要するのだから、計 N-2 回の交換で A 数列のすべての要素があるべき位置に納まってしまう。

だから A 数列のすべての要素が唯一のグループを作って位置を交換していなければいけない。その場合に最大 N-1 回の交換を要する。

というのをコードにして提出したのだけど、WA が半分>https://atcoder.jp/contests/nikkei2019-2-qual/submissions/8366469。答えが二択なんだから惜しくもない。わっかんねーなー。

続く……

最終更新: 2020-05-06T23:26+0900

♪ [AtCoder] AtCoder Grand Contest 039／B問題 Graph Partition

もはや毎週恒例。たかだか B 問題に一日散々苦しんでおいてなんだけども、実行速度にハンデのあるスクリプトで、何の工夫もない総当たりを通されては、まったく釈然としない。

 最初の AC (AC / 1053 ms / 4476 KB)

Ds 関数１回は10数msで完了するみたい。Ds 関数１回２回でまあまあ AC (accepted) は出る。でも当てもんではないし、なんだかんだ残った WA (Wrong Answer) が潰せなくて総当たりにした結果、最長タイムが 1053 ms になったと、予期していた TLE ではなかったと。何か手を抜く洞察があれば。

Python でひとつだけ抜けた提出が 100 ms を切ってる。事前作成した実行ファイルを書き出して実行したり、コンパイル＆実行したりの飛び道具は使ってないみたいだし、NumPy の文字も見えない。集合演算をよく使っている。ちょっとわかる気がしない。Python という時点で「for 文に else？ これと同じ話？」>「なぜreturn -1にelseはいらないのか」というところから始まるのだが、それが主たる理由ではない。

 ２番目のAC (AC / 849 ms / 4220 KB)

目新しいアイデアはない。ただ、「あるノードからあるノードへ移動可能かどうか」というデータを「あるノードから移動可能なノードの配列」へと事前処理しただけ。効果はめざましく、600 ms 台だった入力を処理する時間が軒並み２桁msに落ちた。たぶんほとんどのノード間に交通がなかったのだろう。

残る３桁msは３つだけで、それぞれ 100 ms、849 ms、840 ms。特に 800 ms 台の２つの入力がどういう特性を持っているのか(たぶん辺が多い密なグラフ)。対策したい。

 ３番目のAC (AC / 74 ms / 2300 KB)

目新しいアイデアはない。Ds 関数の中心にある二重ループを効率的に回すことを考えただけ。ループが総体としてどのように歩を進めているかを低レベルで考える。そしてそれを縮約する方法を。やることは関数の仕様を変えない関数内部のコード変換なので、機械になったつもりで意味をはぎ取った記号(ビット列)を操作して、入力と出力を最短で結ぶイメージ。

Ruby は200ビット整数が普通に扱えて便利。その結果できあがったのが DsMax 関数なんだけど、副作用として……

• ある点からその他の点への距離一覧(※Ds 関数の戻り値)の代わりに、最も遠い点までの距離しか得られなくなった。
• -1 を返すパターンを検出できなくなった。

答えには最も遠い点までの距離しか使わないので１点目はいい。-1 パターンを検出するために、１回だけ Ds 関数を呼び出すことにして、それ以外で DsMax 関数を呼び出している。

いやあ、またしても Python に勝ってしまったなあ。(そういうコンテストではないし、コンテストは終了している。でもゴルフを楽しんでる人もいるし、なんでもいいじゃない)

あ、r -= s は r ^= s の方が良かったかも。

 極まってるね！ 提出 #7878842 (C++14 / 1 ms / 256 KB)

こんなん問題も見んと printf("%s", "答え"); してるんかと思うやん？ 普通に二重ループを回してるんだよなあ。でも自分みたいに総当たりをするために三重ループになってしまってはいない。二重ループのある bfs を２回だけ呼び出して済ませてる。

この bfs 関数、すごく既視感があるんだけど、これを２回呼び出すだけで問題が解決する理屈が知りたいなあ。

 ４番目のAC (AC / 26 ms / 2300 KB) と、その１文字違いのWA

ベースは２番目のAC。それの総当たりをやめて、２回だけ Ds 関数を呼び出すことにした。キモは、最初の呼び出しで引数に 0 を選んではいけない、ということ。それが WA と AC を分ける。たぶん 0 だと当たりを引いてしまうんだろうなあ。代わりに何を選ぶかは先の「極まってる」提出を参考にした。

正直言ってこれは入力依存のヒューリスティクスなので、時計を見て時間いっぱいまでランダムな試行を繰り返してまぐれ当たりを期待する手法と代わりがない。Ruby で一番に AC を獲得した提出がそういうものだった。

自分にとって真の提出は「３番目のAC」でいい。総当たりで間違いのない答えを求めても、３倍しかタイムが違わないのだから。

 ５番目のAC (AC / 58 ms / 2044 KB)

３番目のACの改良版。DsMax 関数で -1 を返すパターンを検出できるようにして、Ds 関数を用済みにした。３重ループの総当たりでも、インチキの約２倍のタイムにまで迫ってきた。(でもこれをベースにインチキをしたら……)

 ちょっとだけGOLFに走った (311 Byte / 60 ms / 1916 KB)

短い方がすぐに読み終えられて理解が早いよね(大嘘)。でもね、コードはソルーションなのだから、理解するヒントは問題の中に存在している。問題を見て、答えを考えたら、コードが理解できる。それができないなら、どれだけ注釈があっても理解はできない。読みやすいコメントのおかげで理解した気になれるだけ。……というのが、20191002からリンクした「わかりやすさについて」からリンクした「C++で３秒だという人のコードを読んでいた」経験からの実感。

同じく20191002からリンクした「ドキュメントについて」に書いたが、ちょっとだけGOLFに走ったコードに足りないのは「基本がわかっている人間に向けた内部を理解する時間を節約するための勘所」だというのが自分の答え。そのために使えるのが意味のある変数名であり、プリミティブすぎるビット演算に意味を与える注釈であり、採用したアルゴリズムや入出力を説明する関数冒頭のコメントなどだ。

但し、但しだ。Easy はコードの性質ではないのだから、Easy なコードという概念はそれ単独では存在しない。猿でもわかる Easy を求めることは理解が伴わないので意味がない。猿を教育するのは自分の役割ではない。求めるのは、第一に「理解すること」。理解しない人間は読者ではないので。第二に「不明瞭な点を浮かび上がらせる質問」。第三があるとすれば「どう書いてあれば理解に要する時間が省けたかという提案」。Easy が主観だからこそ複数の視点に意味がある。

しかしその提案が「ヨーダ記法は目が受け付けないから NG」や「条件演算子は見慣れないから NG」や「unless は一旦 if に変換しないとわからないので NG」や「for や while に付く else は流れがよくわからないので NG」のレベルであれば合意はできないでしょうな。自分だって「大なり記号が混じると条件式が理解しにくくなるから右が正の数直線上に変数と数値を並べるようにしてほしい」とは言わない。そんなのは慣れや癖や縛りの類であり、自分にあるのと同じように他人にも馴染んだルールがあり、それが一部の判断を安全に短絡させ理解を早めるのである。ジャイアニズムには抵抗する。数を恃んで来ようものなら決裂は決定的だ。

俺は数が力だということを否定したいのだと思う(20181228, 20130228)。だから受け入れられなくなる。面白いよね、逆ではないんだ。否定するために受け入れないのではなく、受け入れられない現実が先にあって、その原理に対する理解があとから来る。これをこじつけと言う？

 悪ノリしたが空白を詰めただけでは変態ゴルファーの背が遠い (188 Byte)

るびまのゴルフ記事がめっちゃ楽しみだった。Rubyist Magazine 0021 号が第一回。著者の日記もゴルフ場もすでに知っていたけどゴルフに興味はなかった。でも解説記事は表層的な意味をはぎ取った言語への(身も蓋もない)理解が深まる楽しい読み物だった。さっき書いた「やることは関数の仕様を変えない関数内部のコード変換なので、機械になったつもりで意味をはぎ取った記号(ビット列)を操作して、入力と出力を最短で結ぶイメージ」にも通じる。「意味」に縛られて「実質」が見えないようでは、「抽象化」が覚束ないと思うのだ。これがまたさっき書いた、「変数名や注釈で意味を与えること」との間でバランスをとるもう一方の考え。

連載を読み直していたら最終回にいいことが書いてあった。「我々が努力して、そして楽しんでいる部分は、基本的なテクニックを抑えた上での膨大な時間を投下して行なう 論理的思考や発想の転換の勝負 なのです。」 基本的なテクニックっていうのが記号盛り盛りの変態的な見た目になってしまうアレ。アレの先にゴルフの真髄があるのだと。

しかし、ゴルフでも Python (191 Byte) に勝ってしまったのだなあ。>「すべての AC (コード長 昇順)」

塗り替えるのが早い！！！ (Python / 182 Byte)

燃えるね。(160 Byte) タイムが約60msから約90msに増えてるのは、入力に対して String#to_i(2) を都度都度呼び出しているせい。ゴルフに魂を売ったようで心苦しい。パフォーマンスを追求する余録で無駄が削ぎ落とされたスクリプトが手に入った、という体でいたい。表記が変態的になるのは「本質」には影響しないから心が痛まないのだけど。

たぶん Perl 勢が参戦してきたらどちらも勝てないね。

ゴルフもまた沼なのか…… (146 Byte)

どっぷりはまっている。(144 Byte)

最終更新: 2020-05-06T23:26+0900

♪ [AtCoder] AtCoder Beginner Contest 138／E問題 Strings of Impurity

Project Euler の人、という認識の人の日記でこの問題が触れられていた。参加していなかった回。「なんということもない問題」だが Python で TLE とのことなので、Ruby で挑戦。

 提出 #7886543 (AC / 432 ms / 10364 KB)

これが、Ruby の力！(違う)

ICache 変数抜きの提出では見事に(同じ)轍を踏みました>提出 #7886442 (TLE)。

ちなみに Ruby での最速タイムはちょうど３分の１の時間だった>144 ms。文字ごとに出現位置リストを作ってバイナリサーチらしい。魔法は無しか。

あるいはメモリをケチらずに文字列全長に渡って文字種ごとに次の出現位置を……、というのも魔法ではないな。オーバーヘッドでかいし。

最終更新: 2020-05-06T23:25+0900

♪ [AtCoder] AtCoder Beginner Contest 142／E問題 Get Everything

アルゴリズムがどうとか、タイムがどうとかではない。答えが出たのが嬉しい！ WA (Wrong Answer) はもう見飽きた！

 初めてのAC (AC / 1886 ms / 3960 KB)

全然実装方針が固まらなかった。何について繰り返し、どうなれば終了していいのか、さっぱりわからなかった。だから初めてまとまった数の AC が出た提出は総当たりだったし、AC でなければ当然 TLE だった。

そのうち N の上限が12と非常に小さいぞ、とか、コスト(a_i)の上限(10^5)は14ビットだぞ、とか気がついて、鍵を32ビット整数(※)にエンコードすることにした。※Ruby の埋め込み整数は32ビットないかもだけど>http://www.a-k-r.org/pub/2016-09-08-rubykaigi-unified-integer.pdf<実装依存ということでスクリプトからは隠されたらしい。

その鍵をどうすれば答えにつながるかという点 は、20110826p01.02の記憶がうっすら影響してる。今回は間違えずに、不安から慎重(無駄)な処理をすることは避けられたと思う。

あとは AC の数より多い WA を潰す長い長い迷路。もうお疲れなのであとは他人の提出を見てネタバレを楽しむのみ。

 Ruby による提出一覧

Ruby でも 500 ms を切ることができるらしい。200バイトちょっとのスクリプトで答えが出るらしい。ネタバレはもうちょっと先にしよう。

 ２番目のAC (AC / 565 ms / 2684 KB)

タイムとメモリの代表値には最悪の数字が選ばれる。条件式をひとつ付け加えたら、最悪だった 1886 ms が 223 ms に縮まった。これはしてやったり。

鍵の包含関係は気になっていたんだけど(※このときの経験から。「他ののサブセットになってるのがあったら除外できる」)、チェックして除外する適所がわかっていなかった。WA を潰すのでそれどころではなかったし、そのために処理と負荷が増えては本末転倒だし。

あとはこの、完全に手続き指向で長ったらしい解答を根本から覆す天啓が降っては来ないものか。

 他人の提出を見た。

使われている変数名 dp がすべてを語っているのではないだろうか。このパターンは何度も経験している。「それ DP で」案件だったのだろう。でも DP(動的計画法)の一語で理解できたことがないまま今に至ってるんだよなあ。持つデータに対して頭の整理が追いつかないもので。

平均タイムで見ると自分の解法も悪くないと思う。Ruby の提出で一番速いタイムが 481 ms だから、最悪タイム(565 ms)を記録した最後の入力に対策できれば一矢報いられるのでは？

 チューニングした (AC / 476 ms / 3836 KB)

狙い通りに最悪タイムだった 565 ms が 476 ms に改善した。スクリプトって書けば書くほど遅くなるのが普通だから珍しい。

しかし、多くの入力で実行時間とメモリ使用量が微減している中、02-random-17 という入力だけ特異的に 1788 KB が 3836 KB に増大している。これってつまり何が起こっているんだろう。大量の使い捨てオブジェクト？ どこから？ Array#shift(n)？

 さらにチューニングした (AC / 25 ms / 2424 KB)

桁が違っていて効果に自分でびびっている。「インタープリタ型言語でトップクラスの速さ」。やったぜ。でもやっぱり、ソースが長たらしくて汚い。

(組み合わせではなくコストによる)順序をつけて、不要な処理をスキップし(※nextステートメントの数を見よ。あ、<= にできるところが１か所 < になってる。無駄だ)、ソートにコストをかけないように２本目３本目のキューを細かに操作し(※あ、bsearch_indexの条件が潜在的にバグってる。+ を | にして <= を < にしないと)、答えが見つかり次第打ち切るからこその速さであって、(１本のキューと)手続きが中心になるのは避けられないとは思うが……。

ちなみに、Corvvs という人の提出(https://atcoder.jp/contests/abc142/submissions/7795963)を参考にした(「あ、全適用は S の要素だけでいいんだ」)。この人の ID はもう覚えてしまっていて、この前「あとで知ったのだけど、Ruby には Integer#bit_length という便利メソッドが予め用意されていた」と書いたのだけど、その「あとで」がこの提出だった>https://atcoder.jp/contests/abc141/submissions/7557027。ひと味違った解答を書く人だと思う、それを Ruby で。

そうそう、最初の遭遇はこれだった「Rubyで一番速いのはこれ」。それが「「Rubyで一番速いの」を真似して勉強」へと繋がり、現在の AtCoder との付き合い方が決まった。「自ら取り組み考えた「問題・課題」に対する異なる方向からのアプローチは、よく身に付く貴重な学びの機会」の実践。優れたお手本に事欠かないし、自分の方でもそれを理解する準備が整っている。

最終更新: 2020-05-06T23:25+0900

♪ [AtCoder] AtCoder Grand Contest 038／B問題 Sorting a Segment

A 問題よりは難しい B 問題。C, D, E, F は一目見て問題文の理解を諦めたよね。

 最初の提出 (WA/TLE/AC 混在)

TLE(時間切れ)は潜在的な AC だという期待が持てるから、はっきり WA (Wrong Answer)だと告げられる方が問題。AC と混在しているあたり、微妙なケースの考慮が漏れている。

問題にあたる方針はこう。長さ K のウィンドウを数列 P に重ねて１ずつスライドしながらウィンドウの中の要素をソートするとする。

スライドに伴いウィンドウからはみ出た要素が直前のウィンドウの中で最小(最大)の要素であったかどうか、また、新しくウィンドウに入った要素が現在のウィンドウの中で最大(最小)の要素であるかどうか。この２点に注目するだけで全体の数列の並びに変化があったかどうかがわかる。

ただしこれだけでは足りない。

 ２番目の提出 (WA/TLE/AC 混在)

pm という変数によりウィンドウ内の要素が最初からソート済みだった場合の考慮を試みている。だがまだ整理し切れておらず、AC が WA になったケースや、逆に WA が AC になったケースがある。

 ３番目の提出 (TLE)

WA がなくなり、AC と TLE のみに。ちなみにこの時点でコンテストはとうに終了している。

 ４番目の提出 (TLE)

答えが得られる main 関数が確定しているのであとは TLE を解消すべく、意味を変えないように注意しながら効率の良い実装に置き換えるリファクタリングに励むだけ。

……なんだけど、３番目より効率が落ちて TLE が増えた。しかし頭の中を整理する役には立った。ウィンドウ内の要素をソートしない手法への転換もこのとき。これが５番目の気づきにつながった。

 ５番目の提出 (AC / 427 ms / 30132 KB)

ウィンドウの中で最大(最小)の要素かどうかを判定するのに、先日の20190907p01.03のデータ構造が使えると気づき、Next メソッドと Gen メソッドをコピペして利用したところ AC に。

ウィンドウ内の要素の並びが最初からソート済みかどうかの判定には、右方向に単調増加の要素がいくつ続くか、というデータを利用した。これを作成するループは、やはり先日の「小細工」としてのデータ LX と RX を作成したものと同じ構造をとっている。

 ６番目の提出 (AC / 329 ms / 42816 KB)

同じく先日の20190907p01.06で使ったインデックスの作成方法とソート方法を利用してタイムを改善した。

係数がいくつでも O(N) だとはいえ、長さ N のフルスキャンを４回も５回もやり、長さ N のデータ配列を10も11も作成すればオーバーヘッドはいかばかりか。一部の入力に対しては初期の提出に比べて３倍の時間をかけているし、メモリ使用量は倍以上。

他からの流用そのままではなく、この問題に最適化した手法であるとか、根本から別物の優れた手法であるとかがないものか。No Idea なんだけども。

 ７番目の提出 (AC / 295 ms / 36544 KB)

主として NextIndex メソッドの無駄と NextIndex メソッドの変数名の間違いを修正したリファイン。ちょっと速くなってちょっと省メモリだが、まあ、小細工。

 Ruby による提出一覧

 Ruby で一番新しい提出>https://atcoder.jp/contests/agc038/submissions/7648285

WA が２つある以外は AC で、タイムもメモリ使用量も優れている。

cnt_up, cnt_k は自分の提出における UP に相当するものだけど、min_deq, max_deq を中心としたその他の大部分は、ちょっと見当が付かないくらい違っていて面白い。どういう着想を持つとこういうコードになるんだろう。

ウィンドウをスライドするものとして扱うのではなく、両端の要素に着目してウィンドウを分類し、カウントしているのだろうか。このあたり(ウィンドウの処理順)、適当な制限条件を付けて最適化が可能な雰囲気がなきにしもあらず。

 他の提出を見てると多いのは

最大値、最小値それぞれについて待ち行列を用意するものみたい。「Ruby で一番新しい提出」もそう。ポイントは

• 待ち行列の要素数は K 以下。
• 追加する要素との大小関係によって、待ち行列の末尾から、永遠に最大要素(最小要素)としての順番が来ない要素を追い出す。

８番目の提出 (AC / 243 ms / 19124 KB)

いいね。時間もメモリ使用量も「７番目」からさらに改善した。

気がついてる提出を見なかったけど(※主に見たのは Python。Ruby とは提出数が桁違いなんだよなあ)、最小値の方の待ち行列の長さを見れば最初から昇順にソート済みだったかどうかがわかる。

Queue から追い出す処理に while 文が使われてるけど、そこと Array#shift に目をつむると(※)、N 回のループ１つで終わり。余分なメモリ要求も計 2×K 要素の配列だけ。

※キュー１つあたり push がループ全体で N 回なので、pop/shift を合わせた回数も全部で N 回以下にとどまる。Array#shift がどうしても気になるなら、メモリ要求を 2×K でなく 2×N にすれば定数時間にできる。

９番目の提出 (AC / 243 ms / 18428 KB)

Array#shift を定数時間の処理に置き換えようとしたら追加のメモリ要求が 2×N になるどころか N だけになったが、2<=K<=N なので 2×K と N の大小関係は一概には言えない(※最悪の場合がマシだとは言える)。しかも Ruby では速度の改善にはつながらず……。

ところで、C配列のシフト操作と、Ruby の Array#shift の実装が別物なのは言うまでもない。あくまでも原理的な話であって、タダで手に入るオールマイティはないのだから気にして損はないだろうということ。Ruby 1.9 の array.c を見たら内部ポインタのインクリメントで済ませているようだったので、得することもなかったみたい。(そうか。unshift はダメだけど shift は気易く使っていいのか)

最終更新: 2020-05-06T23:25+0900

♪ [AtCoder] AtCoder Beginner Contest 141／D 問題 Powerful Discount Tickets

Ruby による提出一覧

1. 最初の提出 (TLE)

   問題文に書かれた操作をそのままコードにしたらほとんどが TLE で全然ダメだった。ソート済み配列に find_index を使ったのが間違い。

2. ２番目の提出 (TLE)

   find_index を bsearch_index に置換したら３つを除いて AC になったが、やはり時間をかけすぎている。

3. 後日の提出 (AC / 221 ms / 30216 KB)

   Ruby で一番スマートな解法にくらべてメモリも時間も倍以上かかる力業。例によって例のごとく風呂場で思い付いた。

   あとで知ったのだけど、Ruby には Integer#bit_length という便利メソッドが予め用意されていた。Ruby 1.9 にはなかったメソッドだ。しかしこの前ランタイムエラーを食らったから、AtCoder の Ruby(2.3.3) には Array#sum なんていかにもありそうなメソッドがまだ実装されていないことは知っている。参照してるドキュメントのバージョン(複数)も、ローカルにインストールしてる Ruby のバージョン(複数)も、全部がばらばらなんだよなあ。

4. 後日の提出(bit_length を使った版) (AC / 149 ms / 11776 KB)

   少し前(20190628)に見かけた MSB 関数をコピペ利用する代わりに組み込みの Integer#bit_length を使うようにしたら、アルゴリズムの優劣は覆せないものの、メモリは同程度、時間は倍に至らない程度にまで改善した。たぶん２回ソートしてるのが良くない。割る２をシフト演算に読み替えて応用が利かなくなってるのに、速さで負けてるあたりがなお良くない。

5. 番外１：最初の提出でソート済み配列の代わりにヒープを使っていたら (AC / 803 ms / 13604 KB)

   TLE(２秒越え)にくらべたらまあまあ悪くないタイムでやんの。

   訂正：提出したスクリプトに max, min = @h[0], @h.pop という行があるが、min は最小の要素ではない。単に末尾の要素。

6. 番外２：番外１のチューニング (AC / 549 ms / 10252 KB)

   1. loop メソッド を while 文に。(Q#up_heap, Q#dn_heap)
   2. 要素の交換を繰り返すのではなく、位置が確定してから一度だけ代入するように。(Q#up_heap, Q#dn_heap)
   3. @h.size 値をキャッシュ。(Q#dn_heap)

   これで３割ちょっとの時短。でも JavaScript(Node.js)の提出でもヒープを実装してるのだけど、そちらは 100 ms 台で完了しているのだな。それも値の合計に Q.pop を使用していながら。値の取り出しとそれに続くノードの降下が一番時間を食うというのに。

 Ruby で一番速い解答に学ぶ

２本目の待ち行列(FIFO)を用意すればそれをソート済みに保つのは雑作もない(※)、というのがこの問題の肝であった。長さ M を確保しておけば固定長配列で十分でもある。

１本でやろうとするから、余計な面倒と時間コストがかかる。

※やっぱりまだちょっとわかってないかも。割る２をして２本目の待ち行列の末尾に加える要素と、それまで末尾だった要素の大小関係が一見ではわからない。これがわからないから、毎度のソート(順序維持)操作をしてしまう。

たぶん２番目の待ち行列に飛び込むタイミングがキー。そこから導かれる。でも、うーん、はっきり見えない。操作の前後で２本目の待ち行列の全要素が重なりなく前後に位置するというのが。