/ 最近 .rdf 追記 設定 本棚

脳log[2019-10-06~]



2019年10月06日 (日)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

同じく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 138E問題 Strings of Impurity

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

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

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

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

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

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


2019年10月02日 (水) "simple"と"easy"はどう違う? Simple Made Easyを解説 Part1 - ログミーTech」「Part2」※Made Easy は常套句らしく、雰囲気で読んで間違えた。過去形にする理由がないし、実は p.p. らしい。「本のタイトルなどの...made easyの意味 - IT系の英語表現を学ぶ」■要点。Simple と Easy は対立概念ではないってことと、Simple こそが目指すべき価値であるということ。そのために Easy を手放す必要はないが、Easy のために Complex を選ぶ(Simple から離れる)のはどうかという問い。とても良い。20190218でも似たような趣旨のスライドへリンクを張った。■ブコメがひとつあるがこれをどう取り扱うか。「両者を比較してsimpleの方が良いなんて奴は、アセンブリ言語でもやってなさいってこった。 - mz88av40のコメント / はてなブックマーク」 比較して一方を選ぶという考え方はおかしい。Part 1 で強調されていたことが読めていない。ではアセンブリが Simple という価値を大事にしている尊ぶべき言語というのは事実だろうか。アセンブリは極めて限定された局面でしか現実的な選択肢ではないので、Simple の行き着く先がこれでは論から説得力・影響力が失われる。■結論がどこにあるにせよ、おそらく、抽象化がキーワードとして出てくると思う。抽象化が Simple を助けるものであり、Easy/Complex とは必ずしも結びつかないことを示せなければ、Simple を Easy より優先させようという主張が弱いものになると思う。で、実際のところは?■■■問題に対処するのに対照的なアプローチがあって、深く潜って基礎の歪みを修正してその影響(1か所ではないかもしれないし、問題が発生した元の場所とは違うかもしれない)を手当てするものと、表面に現れた亀裂を埋めるだけで問題がなかったことにするものと。リンクしたログで触れられていたけど、Simple は客観的な性質で、Easy は主観だという。静的な性質から自ずと生じる Easy は悪くないが、猿でもわかる Easy を目的にしてしまうと、針路を見失うのは必至、良くて怪我の功名だと思う。■元の話題との関連がわからない? Simple を追求することがどのような姿勢であるかと、主観概念である Easy を目的にするとどのように道を誤ることがあるかがわかると思って。抽象化というキーワードは出てこないけど連想してアセンブリにも言及すると、何もしないこと、簡単に済ませることは Simple でも何でもない。だってそれが「Simple な何」であるというのか。■無能ゆえに Easy な対処しかできなくて、問題を解決する代わりに一度あらわになった問題を隠そうとする現象が見られる。見えている。そもそも問題を解決しない問題に対する対処というのが、Simple に対する攻撃であるという点で付け加えられた別の問題に他ならない。船が沈むのは時間の問題だろう。マッチをどうにかせずに懸命にポンプを動かす徒労など御免蒙る。問題を解決する、Simple を追求するってつまり、マッチをどうにかしてポンプを不要にすることであり、俺は火を消せなかった。だから対岸に避難した。■客観と主観を Simple と Easy の区別・対比に関連づけたことはなかったけど、対象から分離すべき Easy の主観性を過去の一文が示していた。「Easy は端から眼中にない。それは道具を使いこなせない、対象を理解できない、自分の問題。」「~するところの解読がまだ。プログラム全体としては無駄がなくて、そういう意味ではわかりやすいんだけど。」■■■ちょっと逸れるけど Simple と Easy を包含する「わかりやすさ」についてはこれも関連する。「ドキュメントについて」。お客さんが相手なら Easy が求められるのは否定しない、お客さんが相手なら。とはいえ俺は客の立場でも仕組みから説明されたい。「要するに同じことなんだろうけど、仕組みと指示の理由を説明するダイキンの方が俺は好き。」「シマノのハブの説明書にクイックリリースのハンドルの向きを規定する記述があって、それに続けて、茂みに突っ込んだりしたときに強制的に開放されないためだとかなんだとか、そうする理由が一緒に書かれていた。とてもとても素晴らしいと思います。」 つまるところ、自分にとって Easy を含む「わかりやすさ」は、Simple な構造・仕組みからしか出てこない。Simple でなければ、Easy ではない。全てを覆い隠して無知であることを許されても、それを Easy とは受け取れない。Complex はもちろんわかりやすくない。■ちょっと話題が戻るかな? 本当に、機械が Simple であるかどうかは客の立場からはうかがい知れない。そこは問うていない。ここで、(メンタル)モデルと抽象化が出てくると思う。抽象化が Simple を助けるって話だ。それがどういうことかは考えたことがないので説明できない。ひょっとしたら「Easy とは抽象化の果実である」なんて予想外の論がもっともらしく語られる可能性だってある。だけどそれは間違いであるか、良くて飛躍した結論でしかないと思ってる。


2019年09月29日 (日)

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

[AtCoder] AtCoder Beginner Contest 142E問題 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バイトちょっとのスクリプトで答えが出るらしい。ネタバレはもうちょっと先にしよう。

 2番目の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ステートメントの数を見よ。あ、<= にできるところが1か所 < になってる。無駄だ)、ソートにコストをかけないように2本目3本目のキューを細かに操作し(※あ、bsearch_indexの条件が潜在的にバグってる。+ を | にして <= を < にしないと)、答えが見つかり次第打ち切るからこその速さであって、(1本のキューと)手続きが中心になるのは避けられないとは思うが……。

ちなみに、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 との付き合い方が決まった。「自ら取り組み考えた「問題・課題」に対する異なる方向からのアプローチは、よく身に付く貴重な学びの機会」の実践。優れたお手本に事欠かないし、自分の方でもそれを理解する準備が整っている。


2019年09月22日 (日)

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

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

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

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

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

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

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

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

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

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

 3番目の提出 (TLE)

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

 4番目の提出 (TLE)

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

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

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

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

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

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

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

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

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

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

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

 Ruby による提出一覧

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

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

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

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

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

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

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

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

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

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

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

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

9番目の提出 (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 は気易く使っていいのか)


2019年09月16日 (月)

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

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

Ruby による提出一覧

  1. 最初の提出 (TLE)

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

  2. 2番目の提出 (TLE)

    find_index を bsearch_index に置換したら3つを除いて 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 を使うようにしたら、アルゴリズムの優劣は覆せないものの、メモリは同程度、時間は倍に至らない程度にまで改善した。たぶん2回ソートしてるのが良くない。割る2をシフト演算に読み替えて応用が利かなくなってるのに、速さで負けてるあたりがなお良くない。

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

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

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

  6. 番外2:番外1のチューニング (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)

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

 Ruby で一番速い解答に学ぶ

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

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

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

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


2019年09月08日 (日) この会社は最後の選択肢だけど、一応目を通しておこう。「“ソフトバンク”、契約期間も契約解除料もない料金プランに刷新 | プレスリリース | ニュース | 企業・IR | ソフトバンク」■「基本プラン(音声)980円」OK。「1回5分以内の国内通話が無料になる「準定額オプション(月額500円)」」5分を超過した通話が全体としてどういう扱いを受けるかを明らかにする必要があるが、OKOK。「データプラン100MB 300円 ※使用量がデータ容量を超過した場合、請求月末まで通信速度を送受信時最大128kbpsに低速化します。」MVNOだと超過後は200kbpsになることが多いと思う。それより遅いがまあ(ISDNで倍速?)、OK。■3つ組み合わせて1800円で、条件付きでも無料通話がついてくるのはかなりいい。問題はデータプラン100MBの対象にスマホが含まれていないことだ。俺は今月からスマホを使い始めたけど、今月今日までのデータ使用量が2MBなんだよ。用量超過が想定され条件に含まれているのに、スマホとケータイを差別する根拠はなんだ? そして俺のスマホは100MBを超過しそうにないときてる。合わないプランを押し付けられ余計な金を払わされるのはまっぴらだ。解散!■■■端末購入補助については興味もないし理解する気も毛頭ないけど、ソフトバンクと au が発表したものは「割引」ではないよね。車で聞いたことのある「残価設定型自動車ローンとは? 元自動車営業が徹底解説! | SmartDrive Magazine」と同じものでしょ。先立つものがないのに高額機種が使いたいというなら、一部の支払いを先送りして目先の負担を軽減するためか、未来の選択肢を差し出しひもにつながれ続けるかを選んで利用すればいいけど、得した気になってるなら危ない。■理解が間違ってるかもしれないけど(だって難しいんだ)、だからこそ、関わり合いになりたくないのだ。賢い人だけで何かやってないで、こっちの頭で理解できる内容のサービスを出してくれよな。■「端末代金を最大半額免除」という記事タイトルを見た。割引でなく免除。年金の免除制度の免除と同じような意味では、たしかに免除されるのかもしれん。免除され一部を支払わなかった代わりに、端末は手元に残らないし、年金給付額はしっかり減るわけだ。


2019年09月07日 (土) あなたの性格タイプ: 管理者 ISTJ-T/外向(3%)↔内向(97%)/直感(17%)↔現実(83%)論理型(76%)↔道理型(24%)/計画(76%)↔探索(24%)/自己主張(35%)↔慎重(65%)」■自分に当てはめてみてなかなかのことが書いてあるけど、他の分類にも似たり寄ったりの感想を持つ可能性がないではない。何より、こういうのってセルフイメージしか明らかにできないと思うんだけど、どうなんだろう。こう答えたからこう書いてあるわけで、言い換え以上の何かが得られているのだろうか。そしてそれは実像に一致しているのだろうか。■日本語で論理型↔道理型と翻訳されていた軸は英語ではTHINKING↔FEELINGだった。え、「道理」ってそういう意味? 絶対に解り合えない人種がこの訳語の背後に垣間見えたんだけど、ただの間違いだったと言って。■琴線に触れたフレーズ「他人が瞬時に状況を飲み込み、行動することを期待します。優柔不断な人には我慢できませんが、自分が選んだ方針が空理空論で対抗されると、さらにすぐに苛立ちます。特にその異論が重要な詳細を無視している場合はなおさら」「自分の評判を重んじるのなら、質の高い人間と交際すべし」「悪い仲間といるよりも、一人でいる方が良い」■不寛容で、体裁を取り繕うことにも意欲がない人間なので、器の小ささ、性格の悪さを露呈させられる、自覚させられる人間からは、距離を置きたいと思っている。■建築家型の性格ページで引用されていた。「意見は認められない。情報に基づいた意見は認められる。誰も無知になる資格はない。――Harlan Ellison」 最高にかっこいいセリフじゃあないか。関連しない?>20190815■■■これもやった。「16Test - 精密性格診断テスト」 結果(443KiB)>「フクロウ型(INTP).png」■解説の「フクロウ型のように未来や抽象的な世界を常に探求している人」という文言は理解に苦しむ。未来より現実、理論より経験を選んだし、直観型(29%)↔感覚型(71%)の解説はこうだ。「直観型はイメージや概念を取り扱うことが得意であり、感覚型は五感を通した体験を得意とする傾向があります。」■「かなり高い創造性」の一方「閃き力がない」というのも矛盾するようでどう捉えていいのかわからない。創造性に対する閃きっていうのは即興性に比重があるのだろうか。たしかにそれは皆無。■そして残念なことに性格診断なので「全動物タイプの中でも最も高い知性を持っていると言われている研究者のようなタイプです」と言われても、知性を計られたわけではなく……。

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

[AtCoder] AtCoder Beginner Contest 140 E問題

 E - Second Sum

Rubyによる提出一覧

  1. 終了時刻までに Ruby で AC(Accepted) を取った提出はひとつもなかった。
  2. 自分は TLE(時間切れ) はおろかひとつの正解にも届いていなかった。

    Ruby で1秒未満で終了するのはシンプルな100万回くらいのループだという感覚があるから、100000の2乗になりうるループをそのまま書いても無理だという予想は最初からあった。

  3. 例によってお風呂の中で考えました。
  4. 最初の提出は sorted と almost_sorted に分類される入力が TLE(時間切れ)だった。他はAC。
  5. ちょっとした小細工を付け加えた次の提出で AC になった。(753ms)

たいへん嬉しい。Beginner には Beginner なりの達成があるものよ。

 Rubyで一番速いのはこれ。345ms>https://atcoder.jp/contests/abc140/submissions/7415625

自分は sorted/almost_sorted に対策した余分なデータを「小細工」として追加したけど、この投稿では問題に最適なインデックスを作って利用してるんじゃないかと思う。そこの差が large に分類される入力を処理する時間の差として現れている。

  • 保存してる値が違う。検索のための補助データでなく、検索結果を保存してる。
  • scan メソッドで ps を rs にマップする際に、その処理の最中に、rs の値を利用している。

    たぶんここで処理時間に差が出た。

    しかし変数jがあまりに謎めいていて、よくわからん。

    あ、値としてのjと、添え字としてのjがあるのか。でもわからん。

    Pの要素を順になめてインデックスを作成していく。ある要素のインデックスを作成するとき、すでに処理済みの隣の要素を見る。その要素が処理中の要素より大きければ、インデックスでポイントすべきはそれ。小さければ、それのインデックスが指す要素が次に見るべき要素。それが処理中の要素より~(以下同じ)。

 「Rubyで一番速いの」を真似して勉強。318ms>https://atcoder.jp/contests/abc140/submissions/7444759

中身はパクりだけど形式にはちょっとした違いを加えた。

元のコードの scan メソッドにはひとつ思うところがあって、ref パラメータが実質的にフラグとして機能しているのではないかと、異なる2種類のコードを scan メソッドとしてひとつに融合するために使われているのではないかと、思わないではなかった。

2回分の手続きをまとめたものではなく、関数として抽出できる機能は何かと考えた結果が Next メソッド。Gen メソッドはささいなトリック(※)を自動化するだけ。※Next メソッドの3つのパラメータ _O1, _I, o の多重化に関すること。

時間制限がある中で考えることではないけども。

 C++で驚異の提出がこれ。7ms>https://atcoder.jp/contests/abc140/submissions/7391384

C++だから速いのではなく、長さ N の一重ループしかないから速い。加えて何がすごいって、C++ なのに Ruby で書いたのより短いこと。

そうなのだ。アホの子は余計なことをして自分から問題を難しくするのだ。

 C++は置いておいてPythonのこれ。173ms>https://atcoder.jp/contests/abc140/submissions/7411285

これもループは一重。ただし最初のソートが重い。

戦略は、P の要素を小さい順に処理すること。そういう限定条件をつけることで、LU, RU という自分のこれまでのスクリプトでおなじみのインデックスを、随時局所的にアップデートするだけでも有効性を保ちながら使うことができる。有効性は限定されていて、インデックスの正しい要素を参照すれば正しい結果が得られる、というもの。

  1. LU と RU のすべてのインデックスが、P の左隣(右隣)の要素をポイントするように初期化する。(これは P の最小の要素については正しい)
  2. P の要素を処理するたびに、その要素をポイントしていたインデックスを張り替える。(処理済みの要素をインデックスから除外することで、未処理の P の要素のうち最小の要素について、インデックスは常に正しい)

まねまね。172ms>https://atcoder.jp/contests/abc140/submissions/7499717

実のところ + [N, N]+ [-1, -1] は完全なるコピペ。+ [N]+ [-1] ではダメだったものがどうしてこれで正しい答えにつながるのか、さっぱり理解していない。RU[N] と LU[-1] に番兵を1個置くのと2個置くのの違いとは。

 真打ち。C++ のあれ

Pythonので本質は語られている。それに付け加えるのは、P の要素に関する前提知識を利用すればソートにかけるコストを減らせるよねってこと。

99ms>https://atcoder.jp/contests/abc140/submissions/7499891

インタープリタ型言語でトップクラスの速さになった。

 まとめ。Rubyによる実行時間の変遷。

TLE(sorted/almost_sorted)P の各要素についてナイーブに LU, RU を検索。
753 msソート済みの入力に対策して LX, RX を導入し、LU, RU の検索を早期に打ち切るように。
318 msLU, RU の検索順を前提に組み込み、それまでの検索結果を利用することで検索時間を短縮。
172 msP の要素の処理順を小さい順と決め、インデックスが有効な対象を未処理の P の要素のうち最小のものに限定することで、インデックスは検索して作成するものではなく、初期化し(決まったエントリを)更新するものに。
99 msP の要素を小さい順に並べるのに、P の要素がとりうる値を利用する。

与えられた条件を貪欲に利用することと、データが有効な条件を限定して無駄になることをしないこと、かな。

最初から結論が見えていては自分ほどにはこの問題を楽しめまい。ふっふっふ。


2019年09月06日 (金) 「Xperia 5」と「Xperia 1」のスペックを比較する サイズ以外の違いは? - ITmedia Mobile」■自分が使ってるのは Xperia 10 なので、Xperia 10 と比較した Xperia 5 のスペックを。液晶->有機EL。長さ+2.3mm。厚さ-0.2mm。重さ+2g。バッテリ+270mAh。メモリ+50%。ストレージ+100%。Snapdragon強化。レンズ+1個。■4K を除いた Xperia 1 といった風情で、Xperia 10 を選んだ理由である大きさ、重さに寄せているうえ、Xperia 1 のうらやましい特長であった有機ELを残している。桜色はないが藍色も悪くない。■これらの違いが36000円で買った Xperia 10 (4か月後の現在は30000円)からどれだけ上積みされた価格につながるのかが焦点。思いのほか安かったら決断を早まったと後悔するかもしれないが、上限が Xperia 1 の10万円として、Xperia 10 の倍は下らないだろう。じゃあ「お守り」としては高すぎる。そのお守りはドコモ、au のネットワークに十分に対応していないのが、お守りとして最大の泣き所ではある。電波1本とか普通にあるし、つかみが悪いとバッテリーにも影響しそう。


2019年09月05日 (木) #クソ現場祭り2019 に投稿された「解体現場に派遣されていったら人間扱いされなかった話」がエグ過ぎる - Togetter」■5人いた派遣の一人は大学一年生らしいし、一人は「ドカタ現場初めての不慣れな子」。解体現場について何を知っているわけでもないけど、なんというか、異文化交流という感じ。派遣会社を通してしまったせいで生涯踏み入ることがないはずだった人外魔境へ迷い込んでしまった、みたいな。現場の人間の方でも派遣されてきた人らを一目見て何かを察してしまった部分があるのでは? 正当化はされないけど、まあそうなるかもね、という予想が立つ状況ではあったかも。マッチングが悪い。まあ、まともに考えるとマッチが成立しそうにない。


2019年09月03日 (火) この前鍵を忘れたまま出先で自転車をロックしてしまった。そういう事情とともに2時間以上かけて歩いて帰るか、という話をしたら、期待以上の熱心さで親身になってくれ、「家まで送るようにもうじき帰宅する人に頼む」「駅まで送るようにもうじき帰宅する人に頼む」「本人が家まで送る」と、矢継ぎ早に行動し、提案を出してきた。なぜひとつに決まらないかと言えば、自分が遠慮するからだ。「頼まれた人は車で1分の所に住んでいるが自分は20分であり、帰宅のついででも何でもない」「本当に2時間以上歩いて帰ったりはしない。電車を使う」「最寄りの駅までなら送るのにそう大した距離ではないと言うが、そう言うなら駅まで歩くのも大したことではないことになる(※実際のところ徒歩15分)」■結局まだ勤務が残っていた本人が車を出して送ってくれるというのに甘えて乗っかってしまったのだった。提案されて自転車まで一緒に運ばれてしまった。■自分の行動はすごくずるかったと思う。そこまでの反応を期待していなかったというのは言い訳だ。言い訳を続けるなら、自分はそのときの相手のようには行動できないから、そこまでの反応を想像できなかったという事情がある。自分は言葉で提案を却下していた。それには及ばないと。でも相手が言うには、遠慮してるのがわかるから、その言葉は受け取らないのだと。自分の解釈・判断を相手の言葉より優先することは、自分にはできない。■できないというのをやらないことの言い訳にしてきたのではなかったか。自分の要求・期待を言葉にできる人間、ある種厚かましい人間ばかりではないし、そこにつけ込むように、言い訳にしてきたのではなかったか。■いずれこうなる? わかっててもできないよね。「かりかりさんのツイート: "いつもツイート興味深く拝見しています。夫がこのタイプで、ふだんからこちらを気遣ってくれ色々してくれますが、自分が同じ程度気遣いをしてもらえないと思うと怒りまくります。そして私は全然気遣いができないタイプなので、結構大変ですw… https://t.co/gbAKGW03yG"」■余談。「徒歩15分」の解釈がたぶん分かれる。その人は200メートル離れたマクドナルドにも車を出そうとする人だが、自分は家から徒歩30分の最寄り駅まで歩くのを何とも思わないので。徒歩で数分の距離のために車を出したり、それで一号線に右折合流したり、バス停で駅までのバスを待ったりする方が、歩くよりどれほど面倒か。もちろんその日の炎天下を歩かないで済んだのは大いに助けられたところ。■この同じ人に以前出産祝いを(巧妙に)要求され、それに乗っかる形で自分がありだと考える範囲で渡したということがある(※一部が高級チョコレートになって返ってきました)。自分は「奉仕部」でリハビリが必要な人間なので、要求されなければ何もなかった。してみるとタイプが違うというよりは、未熟な自分に合わせてくれているだけなのだな。これが人たらしコミュニケーション巧者というものか。


2019年09月02日 (月) SMSで送信元を偽装したメッセージを送る · Akaki I/O」■SMSの送信者名は送りつけられてきただけの文字列らしい。メッセージアプリではその文字列を元にしてメッセージがスレッド表示されることから、送信者が同一であると錯覚させやすい、と。送信元文字列と送信元電話番号は排他でありどちらかしか送られてこない。国内では送信元電話番号は信用していいし、文字列で電話番号を装うこともできないらしい。■愚かな。俺はてっきり受信者側で電話帳を参照して送信元電話番号をわかりやすく送信者名として表示するのだと思った。自称だったとは。■昨日からスマホを使い始めてメッセージアプリに初めてのSMSが飛んできたんだけど、その送信元は「DoCoMo SMS」を自称するだけで電話番号の情報がなかった。2通目は電話番号の情報があり、その送信者名は電話帳から取られているようだった。しかしこの電話帳への登録名を自称する者からのメッセージは2通目のSMSと連続して表示されるのだろうな。■メッセージアプリの方で返信することのできない自称○○さんからのメッセージをすべてドロップしてくれてもいいんじゃないか。それで使えなくなる2段階認証があっても知らん。俺の理解では SMS は文字を使った「通話」だから、非通知拒否設定にあたるものを SMS に適用できてもいいだろう。■メッセージアプリの自動プレビューは昨日の今日でオフに設定済みだった。リンクやDNSの先読みとか、頼んでもいないことを実行する自動化はいらないし、やってほしいとも思わないから。■■■これも SMS。それも送信元電話番号が関係する。「SIMスワッピングによるTwitter CEOアカウントのっとりについてまとめてみた - piyolog」■Twitter は投稿に際して SMS の送信元電話番号を認証手段として認めているが、AT&T といったモバイルキャリアによる認証が甘かったせいでなりすましが起きた、ということ?■■■「携帯会社の偽メッセージに注意 IDなどだまし取られる被害増 | NHKニュース」「ショートメッセージの中には発信元の名前だけでなく、電話番号まで偽装され、本物の携帯電話会社から届くメッセージと見分けがつかないケースもあった」ってどういうこと? 番号を偽装っていうのは具体的にどういうメッセージだった? 「つまり、"NTT DOCOMO" を詐称したSMSは送ることができるが、東京都の電話番号を詐称したSMSは廃棄されるということです。日本国内のネットワークでは、発信元が実在の電話番号の場合、詐称できない(キャリアで廃棄される)仕組みになっているからです。 海外ネットワーク経由は詐称できる場合がありますが、日本国内の電話番号を詐称したSMSは日本国内のネットワークで廃棄されます。」というのを信じるなら、日本のキャリアを通じて日本の携帯電話会社の番号をSMSの発信元として偽装することは不可能なんだけど。■重箱の隅をつつくと、「ショートメッセージの中には発信元の名前だけでなく、電話番号まで偽装され」というのは原理的に不可能であって(※送られてくる発信元「文字列」と「電話番号」は排他であり、ひとつのメッセージではどちらかを偽装することしかできない)、好意的に解釈するなら、そういう偽装メッセージもこういう偽装メッセージもあった、ということになるけど、表現することに対して脇が甘い。


2019年09月01日 (日) au と決別した日。A1301S と W53S と W53S(2台目)を使ってちょうど16年間契約していた。W53S(2台目)はまだ5年以上使うつもりだったのだが、内蔵カレンダーが今年末までであり、au の3G停波が2022年に迫っていることもあり、そろそろ潮時かと。au とはようやく手が切れて清々したという感想しかない>20100705p01。それでも au を使い続けていたのは、他がドコモとソフトバンクだったからだ。模範を示せるとしたらドコモだと期待してるんだけどな。■理解できない条件ごたごたの端末割引はいらない(※初期費用は問題ではない)。ごく短期限定の割引価格はただのノイズ(※契約期間の大部分に継続する支払額こそが重要)。データ通信は最低最小限でいい(※それを契約プランによる制約としたい。スライドはいらん)。無料通話枠があると嬉しい。そういう、お守りとして携帯電話を持ちたい元ガラケーユーザーに向けたプランを用意しないのだから仕方がない。■月々1300円少々で1000円分の無料通話(※Eメールで使うパケット代にも充当できる)が付いてくる au のガラケープランが満足のいくものだった。スマホのお漏らし通信を避けられないものとしてパケット定額に相当する金額が余計にかかるのは仕方ないとする。でもその結果が月々2000円(~3000円~4500円)プラス従量制(=無料枠なし)の通話料金というのでは、プランの通信部分にも通話部分にも不満がある。■2000円固定で500円分でも無料通話枠があれば au に残っていた。移った先は1500円固定で従量制(=無料通話なし)の通話料金という内容。使ったら使っただけ通話料金がかかるというのは心理的負担が大きいので、500円なり1000円なりの無料枠の存在もまた大きい。1000円分もしゃべらないから、実質的に通話料金が基本料金に含まれていたも同然だった。


2019年08月25日 (日) テレ朝、ATMに忘れた2万円を盗んだ男を警察24時で大犯罪者のごとく放送 → やりすぎでは?と批判殺到 : 暇人\(^o^)/速報 - ライブドアブログ」■俺の感覚では「落ちてる2万円拾った。ラッキー」なんだよね。ポケットや鞄の中からお金を抜き取ったわけではない。他人の持ち物(※)を自分の物にしたわけではない。だからラッキーで済ませてしまいそうになる。※お金が人の手から手へ受け渡されていくものだから、「持ち物」「所有物」だという感覚が薄くなるのではないか。鞄の中、財布の中、肌身から離れたらもうそれまでよ。それが手元に戻ってくるラッキーもあっていいとは思うけどね、それも所詮はラッキーなんだな。■関連。20170329「使い切れそうにないお金を持っている人が近くにいたら、そりゃ、代わりに使ってあげるのが義務であり使命ってもんでしょう。持ち主、使い手、周囲の経済圏、三方良しの win-win-winで誰が文句を言う?」■実際問題自分がどういう行動をとるかを考えると、たぶんお金には触らない。行員に教えるか、手近にいなければ知らないふりで他の ATM を使う。うっかり自分の財布にしまおうものなら、背後が気になって気になって精神的に耐えられない、ということが子供の頃の経験で身に染みている。