/ 最近 .rdf 追記 設定 本棚

脳log[AtCoder: 2019-09-22~]



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月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 の要素がとりうる値を利用する。

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

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