/ 最近 .rdf 追記 設定 本棚

脳log[AtCoder: 2021-02-03~]



2021年02月03日 (水)

最終更新: 2021-05-04T20:49+0900

[AtCoder] AtCoder Beginner Contest 190

先週末の ABC。例によってお風呂で考えるも頭が爆発して無理だと思われた F 問題が、なぜか今日取りかかってみれば解けたので日記にする。

 A 問題 Very Very Primitive Game

すごく難しくて、じっくり 10 分の時間をかけた。

 提出 #19784439 (AC / 119 Byte / 63 ms / 14260 KB)

Aoki と Takahashi の文字列を2回書いているところに余裕のなさが見える。間違えるくらいなら全パターンを網羅して並べればいいんですよ(言っていることが違う>20201101p01.03)。

 B 問題 Magic 3

A 問題より簡単だった。条件を満たすものが1つでもあればいい。Array#any? メソッドの出番です。

 提出 #19786803 (AC / 106 Byte / 68 ms / 14316 KB)

ところで空配列に関して、[].all? は true を返し、[].any? は false を返す。この違いによってメソッドの選択が制限されることがあるかなと一応警戒するんだけど、特にそういう違いは生まれないみたい。むしろそうならないようにデフォルト値が選ばれている。罠があるとしたらそこではなく、穴に落ちるときは all? を選んでも any? を選んでも落ちる。

 C 問題 Bowls and Dishes

制約が K に関して全探索しろと言っている。

 提出 #19795600 (AC / 276 Byte / 1129 ms / 15200 KB)

Ruby で最も速い提出(492 ms)より倍以上遅いんだけど、どういうことなんでしょうね。

本当は今日は F 問題をやるつもりはなくて、この C 問題を速くするつもりで取りかかったのだけど、優先順位をつけた深さ優先探索でやろうとしてうまくいく見通しが立たなかったのだった。

 D 問題 Staircase Sequences

45 分考えた。等差数列の和の公式に2種類あることはこのときに確認済みなので(20201101p01.02.01)、今回は使いやすい方を選ぶことができた。

 提出 #19810009 (AC / 316 Byte / 177 ms / 14400 KB)

珍しく解答の中にコメントがあるのは、書いておかないと脳みそからあふれて何度でも最初から考え直しになるからです。紙と鉛筆を用意すべきなんだよなあ。

 E 問題 Magical Ornament

本番中は残り時間が 30 分しかなかったので問題文が短い F 問題に先に取りかかっていた。同じように考えたかどうかはわからないが、E 問題より F 問題の方が多くの人に解かれていたようだ。自分はどちらも解けなかった。

制約が3重ループを許すと言っている。

解答の後半はもう3回目になるあの形。実行速度にハンデを背負った Ruby でのタイムの詰め方は、このときに研究し尽くした>E 問題 Traveling Salesman among Aerial Cities

 提出 #19823594 (TLE×1 / 2032 ms)

惜しい。とても惜しい。時間制限が2秒なのだけど、実行を打ち切られたときは 22xx ms というタイムになる。32 ms 詰めれば AC になるぞ。

 提出 #19825354 (AC / 656 Byte / 1754 ms / 124536 KB)

ハッシュ表を使っていたところで配列を使ったら余裕の AC。

必然性があってハッシュテーブルを選んでいたわけではなくて、Hash のデフォルトプロックありきでスクリプトを構成していたから、使っていた。TLE は邪道の報い。

 提出 #19825691 (AC / 690 Byte / 1585 ms / 64636 KB)

実は唯一の TLE は最も重いケースではなかった。この提出では TLE だった 21_large.txt のタイムが 135 ms だ。

前半部分で選ばれた魔法石がどうがんばっても連結できないとわかれば、後半の3重ループはスキップできる。そういうこと。

 提出 #19839422 (AC / 834 Byte / 1560 ms / 63468 KB)

前半部分で距離の確定を双方向からやらずに片方向で済ませてみたら、平均的には速くなったけど、一番遅いケースでは 25 ms しか違わなかった。不毛(けがない)

 「研究し尽くした」?

Integer#times を while ループにするだけで 200 ms 縮んでやんの。そんなに違うの? times はイテレータの中では速い方だと思ったけど。

 F 問題 Shift and Inversions

転倒数って固有名詞なのかな。公開された PAST の過去問をやったときに見た>20201111p01。K 問題。それが解いてあった(提出 #18029328)からといって、何かが役に立ったということはない。残念。

最初に、k を増やして数列の初項を最後尾に送り込んだときに、転倒数がどのように増減するかがわかった。わかったからわかったとしかいいようがない。こねくっていたら、転倒数の増減が簡単な計算で求まることがわかった。

それから、転倒数の初期値の求め方を考えた。BIT で殴るのではない、頭のいい方法があるのではないかと考えたが、思いつかなかった。

 提出 #19905237 (AC / 342 Byte / 789 ms / 48888 KB)

BIT です。Ruby や Python で速い提出も同じだったので、転倒数はこう求めるのだ! という頭のいい方法はないのかも。

 提出 #19905970 (AC / 293 Byte / 717 ms / 48844 KB)

実は A 数列をスキャンして作成していた配列 I は不要だった。

BIT を使って転倒数を求める手順も、考え方次第でひと通りではないということ。ソート列を必要とする方法よりは必要ない方法を、BIT へのお伺い(対数時間)が2回になる方法よりは1回で済む方法を選びたい。脳みそはタダだけど計算資源は有限。


2021年01月23日 (土) [AtCoder] NoSub に関して @evima0 さんのこのツイートがえらいと思う。「現在の AtCoder ではコンテストで一度も提出しなかったら (できなかったら) 不参加扱いですが、問題を読み始めた瞬間に参加扱いにすることを検討しているようです。」■ NoSub 即不正みたいな論調ばかりで想像力の足りない連中に言いたい。NoSub したくてする奴なんざいねーんだよ。いつだって誰だって全完できるなら全完したいしそうするに決まってんだよ。A 問題のサンプルを通す解答すら用意できなかったから NoSub になるんだよ。もちろん戦術的 NoSub の選択肢は知っている。でもそれが?■パフォーマンスの良かった回だけピックアップすることでレイティングが上振れするとしても、その範囲は精々色半分程度ではないか。自分の場合、緑が水色にはなるかもしれない。でも青パフォ黄パフォなんて見たこともないから、粉飾しても青黄の目はない。■にもかかわらず NoSub を含む戦術を駆使してレイティングを良く見せようとする人間は、自分がその程度伸びる未来も描けない終わった人間だと俺は思う。何を気にかける必要がある? そんな他人の足なんざどうでも良かろう。

最終更新: 2021-05-07T14:34+0900

[AtCoder] AtCoder Beginner Contest 189/C,E

今日の ABC。

 C 問題 Mandarin Orange

制約がよく見かける 10^5 ではなくて 10^4 だから雑なやり方でも通る気がしたんだけど、そんな仏心が期待できるはずがなくて、時間が厳しいからこそ制約が緩めてあるのだなあ。Ruby では D 問題よりも解かれてないみたい。

 提出 #19612283 (AC / 190 Byte / 88 ms / 15720 KB)

AtCoder のことを初めて日記に書いた記念すべき日「脳log[20190907p01] AtCoder Beginner Contest 140 E問題」を思い出して書いた。

不安だからそのままにしたけど、今回は更新と更新のあいだに参照が1回だけだから、番兵も1つで足りたと思う(これに対する答え>「実のところ + [N, N]+ [-1, -1] は完全なるコピペ。+ [N]+ [-1] ではダメだったものがどうしてこれで正しい答えにつながるのか、さっぱり理解していない。RU[N]LU[-1] に番兵を1個置くのと2個置くのの違いとは。」)。

 提出 #19649425 (AC / 167 Byte / 68 ms / 15644 KB)

ソートで配列を比較するのが贅沢で余分な時間を使ってるみたいだったのを修正した。88 ms → 68 ms

多重代入部分を読み解く参考に>20201124p01, 20200428p01.08.01

主流の解き方ではデータを蓄えたり捨てたりしながら数列を前から一度だけスキャンするみたい。何を蓄えて何を捨てるんだろう。わからない。ピークの情報は残しておいてもしかたないな。現在の要素をピークとして左側への広がりが知りたいかな。上昇トレンドでは広がりに意味がないな。

 提出 #19675442 (AC / 201 Byte / 69 ms / 15096 KB)

2 WA のち AC。数列を1回通り抜けるだけ。上昇トレンドでインデックスを記録しておいて、下降局面で幅を確定する。

あ、これ8行目の if が常に true でバグってる。

 提出 #19679788 (AC / 199 Byte / 66 ms / 14984 KB)

これが(バグ修正済みの)本当の O(N) 解答。バグといっても等しい要素が多いときに無駄がある、という程度だったみたいだけど。

C 問題でこれをイチから考えるのはあまりに酷だけど、実は O(N^2) が通る制約だったらしい。Ruby で 10 メガや 100 メガが秒未満は無理だと思うけど。

 ヒストグラム中の最大長方形の面積を求める

ここで紹介されている方法が O(N)。自分の(前2つ)はソートしてるから O(NlogN)。

 提出 #19680172 (AC / 297 Byte / 69 ms / 15104 KB)

さっきリンクしたのと同じ日記だけど、「Rubyで一番速いのはこれ。345ms」として参照したのと同じ解法。愚直に検索する O(N^2) 解法の改善案として素直に理解しやすいと思う。

数列がソート済みであればあるほど改善効果がなくなるのではないかな。クイックソートみたい。

 提出 #19700600 (corazon さん / AC)
#ここがよくわからない
#●●●しない限り、次に来る高さと取り出した長方形の最後のインデックスをスタックの中に入れる

わからないのがよくわかる。自分が O(N) 解法を書くにあたって 2 WA した原因がここだから。

要するに、「取り出した長方形」は「次に来る高さ」よりも高い要素なわけだから、次に来る高さの上位互換であるわけ。その「最後の」(=最も左の)インデックスを、次に来る高さの左方への広がりとして記録している。

 E 問題 Rotate and Flip

 提出 #19644038 (TLE×6 / AC×24)

アフィン変換を検索して見よう見まねで書いた。1時間かかった。TLE だった。これ以上はもう余力も時間もなかった。無念。


対称移動のための行列は3つの積ではなく2つの積で表現できるし、それも自分で計算して1つにできる。でもそれだけでは TLE のままだろうな。行列の掛け算をただの配列同士の掛け合わせとして自分で書いてみたりもしたけど、7秒が6秒になるだけだった。


競技プログラミングをするフレンズ @kyopro_friends Jan 23

アライグマ「E問題は、(0,0),(1,0),(0,1)の3点だけシミュレーションすれば全部計算できるのだ!」

な、なんだってー。

汎用的に点を動かそうとするのでなく、具体的に基底を動かすってことなんかな。だけどそのシミュレーションをするのに行列を使ったら元も子もないので、どうするの? 頭が働かないから行列におまかせしていたんだけど、どうしたらいいの?

軸に平行な直線で折り返すのはまあできる。90度回転は x と y を入れ替えたり符号を入れ替えたりで、たぶんできる? 個々の点の座標を求めるのは……?

まあ、TLE 提出を見れば行列って形で式が見えてるんだから、計算できないはずがないんだよなあ。

 提出 #19690206 (AC / 619 Byte / 1497 ms / 103080 KB)

いやー、厳しい。ヒントがあってもいくつも穴にはまって時間がかかる。「まあできる」とか言っていた折り返しも実はできなかった。


ここでやったことと蟻本に書かれていた(けど解らない)「実は、m 項間漸化式の n 項目は行列を用いるのではなく、各項を初項の線形結合で表して繰り返し二乗法を行うことにより、O(m^2log(n)) で計算することも可能です。興味のある人は考えてみるとよいでしょう」に関連はありますか?

 @2021-02-06

移動後の点の X 座標ないし Y 座標を求めるのに、a+x*(b-a)+y*(c-a) の式を使うと遅い。どうせ同じ数の係数を蓄えておくなら、a+b*x+c*y で答えが求まるような係数を用意したい。

でも何を考えて係数を変換していけばいいのかわからない。

a,b, c,d, e,f の初期値を 0,0, 1,0, 0,1 として、操作1~4でどのようにマッピングしていくか。

遅い方速い方備考
操作1b,-a, d,-c, f,-eb,-a, d,-c, f,-e同じ
操作2-b,a, -d,c, -f,e-b,a, -d,c, -f,e同じ
操作3p2-a,b, p2-c,d, p2-e,fp2-a,b, -c,d, -e,f 一部 p2 の省略
操作4a,p2-b, c,p2-d, e,p2-fa,p2-b, c,-d, e,-f 一部 p2 の省略
移動後の座標(a+(c-a)*x+(e-a)*y, b+(d-b)*x+(f-b)*y)(a+c*x+e*y, b+d*x+f*y)引き算が不要

遅い方は各操作で余計なことをしていて、移動後の座標を求めるときにも余分なことをさせられている。そりゃあ遅くなるはずだけど、何を念頭に置けば速い方の式が書けるのかわからない。

遅い方を書くときは、基底となる2つのベクトルを定める3点を移動していくつもりで書いていた。

速い方でも (a,b) の意味はただの点なのでわかる。でも (c,d) と (e,f) に何のイメージを割り当てればいいのかわからない。それこそ向きと大きさだけで位置を定めない、ベクトルそのもの? そうかもね。そうなんですか?


2021年01月17日 (日) いつの間にかセンター試験が終わっていた。なくなったという意味で終わっていた。時代は共通一次……ではなく共通テストらしい。

最終更新: 2021-03-02T17:55+0900

[AtCoder] 緑diff精進4問

AtCoder Regular Contest 100C 問題 Linear Approximation
提出 #19496296 (AC / 124 Byte / 173 ms / 36900 KB)
ソートすることに気付けたらあとは基準線をどう上下させるかだけ。
最初は平均をとって考えていたが中央値だった。ひとつだけへっこんだ極端な要素に下駄をはかせようとして、他のすべてがそろってでっぱったら意味がない。+1 するか -1 するか、改善する要素が多い方を選び続ける、その均衡点。
AtCoder Beginner Contest 115D 問題 Christmas
提出 #19497044 (AC / 480 Byte / 63 ms / 14280 KB)
2020年12月にあった PAST の J 問題 長い長い文字列を思い出した。提出 #19035422
ということはこの問題も、クラスも入れ子にしたインスタンスも(つまりは再帰関数が?)不要で解けるということなんだけど、それは解らないので答えはプログラムに聞いた。
天下一プログラマーコンテスト2012 予選CB 問題 ロイヤルストレートフラッシュ
提出 #19497447 (AC / 169 Byte / 65 ms / 14320 KB)
これは簡単。最大でも50枚ちょっとしかないカードなんていかようにも処理できる。
Tenka1 Programmer Beginner ContestC 問題 Align
提出 #19498159 (AC / 215 Byte / 182 ms / 16952 KB)
よくわからない。雰囲気で答えらしきものを求めた。
これを提出するときに1年以上前に D 問題 Crossing に挑戦していたことを知った。提出 #8100494。え? さっぱりわからないんだけど。当時と同じように1時間ちょっと考えてどうにかなる気もしない。

2021年01月15日 (金)

最終更新: 2021-01-16T18:37+0900

[AtCoder] 緑diff精進3問

Coprime はまた解けなかった。WA ではなくなったけど TLE が解消しない。

AtCoder Grand Contest 023A 問題 Zero-Sum Ranges
提出 #19447872 (AC / 107 Byte / 176 ms / 43452 KB)
以前に一度挑戦して TLE になっている。今となってはどうやって TLE を出すのかわからない。
半年前(20200615)まで累積和という概念・単語を知らなかったから、それが理由だろうな。
AtCoder Beginner Contest 160E 問題 Red and Green Apples
提出 #19448291 (AC / 114 Byte / 192 ms / 42816 KB)
リアルタイムで参加した ABC だけど D 問題で詰まったからこの問題は初見。こんなに簡単でいいのだろうか。X≦A、Y≦B という制約がまた親切で、面倒な場合分けを取り除いている。
提出 #19457324 (AC / 94 Byte / 242 ms / 41108 KB)
引数付きの max メソッドを使うチャンスだと気がついて再提出してみたら 25 % くらい遅くなった。用意された罠なの?
diverta 2019 Programming Contest 2B 問題 Picking Up
提出 #19449145 (AC / 184 Byte / 65 ms / 14404 KB)
2019年と2020年に一度ずつ提出して同じように1つの RE と3つ4つの WA をもらっていた。RE は N=1 のケース。WA はたぶん軸に平行な傾きをうまく扱えなかったんだろう。今回は読めていた。

2021年01月13日 (水)

最終更新: 2021-05-04T21:04+0900

[AtCoder] 緑diff精進5問(+α)

AtCoder Problems がお勧めする Moderate な問題(緑difficulty)を上から順に解いた。半年前に解けなかった問題も1年前に解けなかった問題も解けた。だから0完だったこの前の ARC 111 は忘れよう。

AtCoder Beginner Contest 178E 問題 Dist Max
提出 #19414840 (AC / 137 Byte / 319 ms / 28476 KB)
わかるようなわからないような感じが今でもするんだけど、y=x に沿って対極にある2点と、y=-x に沿って対極にある2点を抽出して比較すればいいらしい。コンテスト後に解いた人の感想が目に入っていたのでチートといえばチート。
AtCoder Beginner Contest 152D 問題 Handstand 2
提出 #19421375 (AC / 312 Byte / 63 ms/ 14260 KB)
面倒くさく計算で解いたんだけど、N 個の数を列挙して先頭の桁の数字と末尾の桁の数字でクラス分けして数えて掛け合わせるので解けたらしい。たぶんそちらの方が間違えない。
AtCoder Beginner Contest 114C 問題 755
提出 #19420198 (AC / 210 Byte / 81 ms / 17972 KB)
さっきのと似た問題。これは計算と列挙のハイブリッドで解いたんだけど、そうすると速くもなくシンプルでもなくどっちつかずになった。
そうすると? これを見よ>提出 #15048046 (jajapop さん)。シンプルに列挙して速い。
AtCoder Regular Contest 006C 問題 積み重ね
提出 #19420356 (AC / 95 Byte / 69 ms / 14280 KB)
謎の段ボール。重さと丈夫さが1つの数字で同時に表されている。1の上に2は乗せられないけれど、1と1と1を3つ乗せることはできる。謎の段ボール。
あ、大きさだと考えればいいのかも。小が大を支える不安定な重ね方が NG だと。でも重さって問題文に書いてあるなあ。←どうでもいいから解け。
最適な置き場所は1つなので貪欲法で。
AtCoder Beginner Contest 039D 問題 画像処理高橋君
提出 #19421120 (AC / 242 Byte / 86 ms / 29364 KB)
最近の ABC-D はこういう素直に実装するだけの問題ってなくない? 数学でいじめられたり制約でいじめられたりばっかりじゃない? この問題が今の ABC で出たら difficulty が緑ってことはまずなくて、灰茶がいいところだと思う。世知辛いなあ。

 アナクロニズム

過去問はテストケースが利用できる。DropBox からダウンロードするとコンテストの各問題ごとに in フォルダと out フォルダが解凍される。

ARC111_A フォルダの中がこうなっているとする。

  • in/
  • out/
  • my_answer.rb

そこで次のように実行する。(ARC111_A> はプロンプト)

ARC111_A> attc my_answer.rb

attc.bat の中身がこう。

@echo off
for %%F in ("in\*") do (
	call :run "%~1" "%%~F"
)
exit /b 0

:run
	echo %~1 ^< in\%~nx2
	call ruby27 "%~1" < "in\%~nx2" > "out\%~n1.out.txt"
	fc /A "out\%~n1.out.txt" "out\%~nx2"
	del "out\%~n1.out.txt"
	echo.
exit /b 0

カレントディレクトリの in フォルダの中身を入力として引数のスクリプトを ruby27 コマンドで実行する。出力を out フォルダの同名のファイルと fc コマンドで比較する。

call ruby27 という風に call が付いてるのは ruby27 が exe の名前ではなくて、C:\Program Files\Ruby27\bin に PATH を通してから ruby.exe を呼び出すバッチファイルの名前だという固有の事情から。

別に call でなくて当たり障りのないコマンドならたぶん何でもいいんだけど、call|ruby27 という風にパイプを通すと新しいコマンドインタープリタが起動するので、呼び出したバッチが setlocal してなかったとしても現在の環境(PATH 変数とかカレントディレクトリとか)が汚染されなくなるというハックがある。cmd /C "ruby27 ..." と同じことなんだろうけど、そっちは引数が引数になって二重の引用符が面倒の種だよね。

tc は Test Case の略だけど、 AtCoder の略が at か ac かで定まらないから、attc と actc の両方の名前でバッチを用意してる。ハードリンクにしたら中身の同期に手間もかからないし。

アナクロだけどそれなりに便利。


2021年01月03日 (日)

最終更新: 2021-01-03T19:49+0900

[AtCoder] AtCoder Beginner Contest 187E 問題 Through Path

PAST 第4回の M 問題 筆塗りを思い出したよね>20201111p01.01

制約が 10^5 の組み合わせだというところが同じ。だから何について繰り返すかというところが核心。繰り返しの繰り返しは許されない。N-1 本の辺を順序よく1往復か2往復すれば答えが出そうな気がするんだけど、全然ループの軸が見えなかった。まだ見えていない。テキトーにキューに突っ込んで処理できる順に処理しても間に合うかと考えてみたけど、メモするデータが定まらなくて完成しない。こういうところだよ。こういうところが緑色で燻っている理由だよ。


2020年12月22日 (火)

最終更新: 2020-12-23T00:48+0900

[AtCoder] パナソニックプログラミングコンテスト(AtCoder Beginner Contest 186)E 問題 Throne

まだ AC をもらっていないし、それどころかひとつの提出もできていないけど、外堀が埋まってきた気がするので経過を書く。

 シミュレーションした。(未提出)

gets
puts$<.map{|ln|
	n,s,k = ln.split.map(&:to_i)
	ss = {0=>m=0}
	until ss[s]
		ss[s] = s
		m -= (s-n)/k
		s += (s-n)/k*-k
		s %= n
	end
	next s == 0 ? m : -1
}

これはサンプルの4つのケースのうち、3番目を除いて正しい答えを出す。3番目の 998244353 897581057 595591169 にもたぶん正しい答えを返すだろうけど、答えがおよそ 250 メガなので数分単位の時間がかかるはず。

N と S と K の3つの数字があるけど、N と K が近接していてしかもべらぼうに値が大きい。ループ1回のイテレーションで全周 N のうち1点だけをテストするのでは最悪 N 回繰り返す。N の上限は1ギガだ。

 たとえば K = N-1 の場合

1回のイテレーションで S-1 の地点に移動する。S 回のイテレーションで玉座に移動することが即座に理解できるが、スクリプトにそれは反映されていない。

 たとえば N と K が偶数で S が奇数の場合

K が2より大きければ(N との関係にもよるが)すべての偶数地点を網羅できるとは限らないが、K が最小の偶数2であっても、スタート地点 S から奇数席離れた玉座に移動できないことはすぐにわかる。これもスクリプトに反映されていない。

 それで?

N と K と S の関係をどういう式で表すのかなあ。LCM だか GCD だかのキーワードは目に入ってるんだけど。


K = N%K という風に再帰的に K を更新していくと最後は 0 に落ち着く。K が 0 になるまでに S をどうにかしたものが K で割り切れれば答えは N/K の倍数±α になりそうなんだけど、S をどうするのか、N-S をどうにかするのか、よくわからない。


2020年12月06日 (日)

最終更新: 2020-12-08T16:28+0900

[AtCoder] 鹿島建設プログラミングコンテスト2020(AtCoder Regular Contest 110)/A,B,C

ARC 級の企業コンであることがわかりやすい表記になった。企業コンだけどいつもの ARC と同じ気構えで挑戦してもいいことがわかりやすい表記になった。

鹿島の名前はブルーバックスの『図解 超高層ビルのしくみ 建設から解体までの全技術』の編者としてと2冊の SD 選書『近代建築の失敗(著:ピーター ブレイク)』『建物のあいだのアクティビティ(著:ヤン ゲール)』の出版社(鹿島出版会)としてだけ目にしたことがある。ジャンルが同じだから関連があるのでは?

 A 問題 Redundant Redundancy

題意を満たすような数のうち脳死で求められるものはすべての数の積+1なんだけど、答えに制約があって N 以上 10^{13} 以下のものを出力しなさいと。

2 から N の数を素因数分解してマージする。素因数がそれぞれいくつあれば 2 から N の数を表現するのに足りるのか。16 なら 2 が 4 つ必要だし、27 なら 3 が 3 つ必要。6 や 18 など複数の素因数を持つ数はとくに考えなくていいかな。

 提出 #18579266 (AC)

ひょっとして求めたものを最小公倍数と呼ぶのだろうか。Integer#prime? なんて便利メソッドを使ってごにょごにょするくらいなら Integer#lcm を使うのが直接的だったんだろうか。

 B 問題 Many 110

入力例1の解説を注意深く読めばわかるはずですが、注意すべき点があります。110 を 100 個連結した文字列の中に、110110 という部分文字列は 99 個見つけることができます。決して 50 個ではありません。

この勘違いを正すのに多大な時間を要した。難しい問題ではないとわかるのに答えが全然合わなくて、神経衰弱になりそうだった。

 提出 #18593923 (AC)

とりあえず答えは出た。

 C 問題 Exoswap

前回より悪くて(20201202p01.04)、3問目にして 20 分しか時間が残っていなかったけど、考えるだけ考えた。

  1. 同じ操作が高々1度しか許されていないので、ある数を適正な位置に移動するのに冗長な操作は許されない。
  2. まずは数ごとに必要な操作の列を作った。
  3. すべての数を満足させるよう操作の順番がひっくり返らないようにしながら、すべての操作列を一列にマージすれば良さそう。
  4. 行きすぎて戻るということはできないから、操作が少なくて済む場合は即座に NG。
  5. 同じ操作を要求する3つ目の数があれば、それも即 NG。
 提出 #18611107 (TLE×6 / AC×56)

TLE です。メモリの使用量に比例した時間がかかっているような雰囲気。testcase_10.txt は提出によっては TLE にならないことがあり、TLE といえども 22xx ms ではなく 20xx ms であるあたりちょうどボーダーライン上のケースだといえる。そのメモリ使用量が 560 MB。その他の TLE は 570 MB から 632 MB のメモリを使用している。全然ダメって感じではなくて何割か改善したら AC になりそうな期待が、ないかなあ。

特に頭の悪いことをしている部分があるとは思わないんだけど、だからこそ、根本から発想の転換が必要だと言われたら困るなあ。

大量のメモリって、前半の操作列の列挙部分で使ってるのかなあ。見え見えのダメケースを前半部分で拒絶するべきなのかなあ。さっき書いた「同じ操作を要求する3つ目の数があれば、それも即 NG。」とか、今考えたけど「i,i+1 という操作と i+1,i という操作を要求する2数があれば、操作列のマージが不可能なので NG。」とか。

前半部分の列挙について考えていると、後半部分のキューが不要にできそうな気がしてくるなあ。問題の制約って想像よりかなり厳しくて、可能なケースが限られるし、可能な操作列もいくつか考えられる中から一番簡単なものを出力するのに手間はかからなそう。

つまり、数列に対応した(※)配列に右向き左向きをメモして、山と谷があって、高いところ(流れの発するところ)から低いところ(流れの集まるところ)へ向かってテキトーな順番で列挙するだけなのではないかという……。

※数に対応させるのか数と数の間に対応させるのかで迷ってコードにならない。今は「間」かなという気がしている。

 提出 #18639675 (AC / 424 ms)

とりとめなくいろいろ書いたけど、結局、前半部で見え見えのダメケースを拒絶して AC になった。

もっと鮮やかに解けるはずなんだけど、当面のモチベーションは消えてしまった。


2020年12月02日 (水)

最終更新: 2020-12-03T19:37+0900

[AtCoder] AtCoder Regular Contest 109/A,B,C,D

先月28日土曜日の振り返り。ARC なので A 問題が 300 点からスタートする。2問解けたらまあまあという感じ。配点が同じ 300 点、400 点でも、ABC のと比べるとちょっと手強い印象を持っている。

時間は長めの2時間。ABC と違って C、D、E、F 問題にはだいたい取り付く島さえないので、時間が足りなくなるということはまずない。簡単すぎるテストと難しすぎるテストは時間が余るという点で共通する。

 A 問題 Hands

上の階に上がるのに階段と廊下の2種類の手段があるというのが不思議な設定だが、床の高さが半階分ずれた2棟が上りと下りのスロープで結ばれていると解釈するツイートを読んだ。なるほど。ところですべてのフロアが渡り廊下で連結されているなら、それも水平1本ではなく三角形で繋がっているなら、2棟は一体の構造物として設計されているのでは? そのとき「廊下」はどのような形態になりますか?

 提出 #18452990 (AC)

11分ちょっとで提出している。こうだったらこうだな、こうだったらああだなと考えながらとりあえず書き出してみてそれをそのまま提出した。

 B 問題 log

考えたこと。

  • 長さによらずコストが同じであるし、切れ端を捨ててもいいのだから、とりあえず長い方から買えば良い。
  • そしてもちろん、長い丸太から切り出して買うのを節約する丸太は、短い方から順に揃える。
  • n がいくつのとき、何本分の節約ができるかが問題。
    • 順番に書き出してみれば、長さ1を1本分節約するのに1本の購入が必要。(n=2)
    • そこからもう1本節約するには長さ2を1本用意しなければいけないので、追加で2本の購入が必要。(n=2+3=5)

節約する本数 k から n (の下限)を求める式が n ≧ Σ(k+1) = k+k*(k+1)/2 だということはすぐにわかったけど、n が与えられたときに k の最大がいくつになるのかを求めるのに、sqrt を使ってずっと考えていた。B 問題に取りかかってから最初の提出まで 46 分。

 提出 #18463725 (AC)

n の制約上限は 10^{18} であり、(10**18).bit_length は 60。なんだ探索すればいいじゃないと気がついたらもう問題は残っていなかった。

 C 問題 Large RPS Tournament

RPS って Rock, Paper, Scissors なんだな、たぶん。本番中はよく考えなかったけど。

k の上限は高々 100 ではあるけれど、2^k 通りの勝敗を考えるには大きすぎる数だ。まあ頭の中で考える分にはあまり関係がないので、トーナメントをシミュレーションして、その際に文字列 s のどの部分を参照するのかを確かめていた。優勝者の手、準優勝者の手、準々優勝者の手……がどこからやってくるのか、逆方向のシミュレーションもした。

 提出 #18467915 (AC)

最初の提出まで 30 分。C 問題という段階で解けなくてもともとなので、あせる理由はどこにもない。

 D 問題 く

残り時間は 30 分だったけど考えるだけ考えた。

  • 移動方法は3通り。軸となる2つの石を選べば決まる。
  • 石の配置は単位正方形を基準にして分類できる。すなわち、ある一角(たとえば左上)の座標と、くの字の折れ曲がり部分の位置(左上、右上、左下、右下)の組み合わせで決まる。
  • さて最小の移動回数は?

四角形の座標移動をまず考えた。

  • 水平方向、垂直方向に1移動するには2手かかって、くの字の向きが変わる。
  • 水平垂直同時に1ずつ移動するには3手かかって、くの字の向きはそのまま。

ここまで考えたが、この安定した移動に入る前と出るときに何手かかるのか数え切れなかった。B 問題のことを思い出して探索すればいいじゃない、ということには気がついたが、その探索がどういう形になるのかおぼろにも想像ができなかった。

というわけで D 問題はひとつの提出も用意できないまま放置している。


あ、3通りじゃないや、5通りある。じゃあいろいろ変わってきちゃうね。

え? 7通りある? だから最初から最後まで機械に数えさせるべきなんだな。


2020年11月22日 (日)

最終更新: 2021-05-07T14:51+0900

[AtCoder] AtCoder Beginner Contest 184/C,D,E

 C 問題 Super Ryuma

超竜馬の移動ルールを読み解くのが難しすぎると思うんだ。数学の言葉が通じない人のことを考えてほしい。なんとか解読した結果は、マンハッタン距離が3までの菱形の中と傾きが ±1 の直線上を移動できる、だと思った。

 提出 #18323156 (AC)

これ以上ない可読性を誉めてほしい。可読性とはこういうことだ。(他人が言う、ただの手癖レベルの)可読性なんぞいらない(どうして自分が書いたコードを、あなたにとって読みやすく自分にとってはそうではないように書き直さなければいけないのですか?)。この提出の可読性も認めてもらわなくて全然構わない。

 提出 #18373736 (WA×1)

先の AC 提出と全く同じ内容だが after_contest_01.txt という入力だけ WA になった。テストケースが弱かったので追加されたらしいのだが、みごとそれに甘えた嘘解答だったことが明らかになったということ。

 提出 #18374012 (AC)

after_contest_01.txt を通して本当の AC。可読性は維持している。

もちろん誇大表現は話半分に受け取らなければいけない。数学の言葉が通じない人向けに日本語で移動ルールを書けば曖昧さが入り込む余地が大きくなる。同じように、定義式を見て理解できることに日本語のラベルを付けたところで、ラベルの妥当性には疑問の余地がある。可読性(ラベル)は誰のためのものか。正確な理解ができない人間のためではない。時間がなくて式を読む時間を省略したい人に向けた補助である。時間があれば定義式を読むべきだし、時間がなくても即座に読み解ければそれに越したことがない。

異なる可読性もあると思う。読者を惑わせる無駄や回り道、曖昧さがなく目的に直結する、論理的で考え抜かれたシンプルなコードだ。そちらは追求していきたい。考え抜かれた結晶を、目で字をなぞっただけで読み解けるはずがない。読みやすさとは密度の薄さのことではない。一行を読むのにかける時間を変えればいいだけのこと。薄い内容をいっぱい読むだけ読んでも理解ができていなければ意味がない。理解するには知識と考える頭が必要だ。その時の対象はごく小さく限られている方が集中できて良い、というのが自分の考えであり性質。読むときも書くときもそちらを追求していきたい。

 D 問題 increment of coins

期待値? 定義しかわかりません。試行回数が不定? 一瞬で放り投げかけたが踏みとどまった。

A, B, C 3つも変数があると頭がパニックなので A*10000+B*100+C と1変数にエンコードしてみたらやや落ち着いた。試行を繰り返す遷移を書いて計算して足し合わせたら答えになった。求めたのではなく「なった」のである。

ただし += とすべき確率を = で上書きしていたためになぜかサンプル4だけ答えが合わなかった。「なぜか」はサンプル1から3の答えが合ったことに対する疑問。これのデバッグに30分ちかく溶かした。

 提出 #18339328 (AC / 867 ms)

同じ Ruby で 300 ms 台の提出があるのと比べると 867 ms はかなり遅い。しかしもう考えたくない。

 E 問題 Third Avenue

10分しか残っていなかったのでコンテスト時間中の提出は適わなかった。ただやるだけだと思ったけど、それを手早く正確にやる能力がなかった。多少の時間の余裕があってもダメだったろう。

 提出 #18348009 (WA×1 / TLE×3)

TLE はいいけど WA はいただけない。今日は寝る。

 提出 #18371108 (AC / 2995 ms)

はい、やるだけでした(だがそれができなかった)。TLE まであと 5 ms なのは改善の余地があるだろう。

WA の原因は再訪防止のマーキングを、行こうとするときにチェックを付けるか、着いたときにチェックを付けるかの差だと思う。効率を優先して先走ると間違える。過去に何度も同じやらかしをしているので多分そうだと思う(今ここでよく考えないから次もまた同じミスをするんじゃないか?)。

 提出 #18397451 (AC / 1883 ms)

30% あまり速くなったがあまり本質的ではない改善要因(予想)が5つあるだけである。

  • 再訪防止フラグ(配列 T)のインデックスを誤って使用していた。

    問題として与えられるグリッド文字列に番兵として1行1列を加えていたのだけど、再訪防止フラグはそうではなかった。それにもかかわらず番兵込みのインデックスを使って(予防的な)再訪チェックをしていた。

    訪れるべき所を訪れ損なっていなかったのは運が良かっただけだし、訪れなくてもいいところを無駄に再訪していたと思われる。

  • 壁のあるマスにも再訪防止フラグをセットするようにして、予防的な再訪チェックに引っかかるようにした。
  • テレポーターの前処理をする際に正規表現を引数にした String#index を使っていたのだけど、パターンを /[Sa-z]/ から /[a-z]+/ にした。

    S の有無は関係なくて、連続するテレポーターをひとまとめに処理対象にした。

    String#each_char で1文字ずつ文字種をテストするのにくらべて正規表現という仰々しい道具を持ち出した String#index が有利になる条件は、テレポーターが疎に配置されていて処理対象外の文字を大きくスキップできる場合だと思う。

    逆に言えば、テレポーターが密に配置されていて index が1ずつしか増加しないとき、ただの文字種比較とパターンマッチングを伴うメソッド呼び出しの1回あたりのコスト差が顕在化する。

    index メソッドの呼び出し回数を減らすためのパターン変更。

  • 上下左右の移動先を処理する4要素の配列のイテレーションを展開してべた書きした。
  • 使用済みのテレポーターの処理に関して、空の配列を concat しないように事前にチェックするようにした。結果が同じでも、記述が煩わしくても、パフォーマンスのためには事前にチェックする方が良い。

    インクルードガードにも内部インクルードガードと冗長インクルードガードの2種類があって、冗長でもインクルードそのものをスキップするように書けばファイルを開いて閉じる手間が省略できてコンパイル時間が短くなる。最新のコンパイラ、プリプロセッサがそんな愚直なやり方をしていると信じる理由はないけども、原理的にはそういう差がある。

 提出 #18446644 (AC / 1490 ms)

もう 20 % ほど速くなった。

  • 添字を使った文字列へのアクセスと配列へのアクセスは倍ちょっと速さが違う(Ruby 2.7)。添字の大きさは関係ないみたい。ちなみに Ruby 1.9 は 10 倍違った。
  • 再訪防止フラグを早めに立てるようにしたからキューが長くなりにくいと思う。予防的なチェックが本式のチェックになったからメインループでのチェックも不要になった。
  • 前処理に正規表現を使うのをやめて1文字ずつ細かく準備できるようになったから、再訪防止フラグを利用してメインループの when 節が1つ分減った。

それから、1つだけの WA の原因はよくわからなくなった。少なくとも再訪防止フラグをセットするタイミングが必ずしも理由になるわけではない(今回の提出では移動しようとする先のフラグを立てるようにしたから)。何かをミスればそれを咎めるテストケースがちゃんと用意されているというだけ。別の提出では別のケースが1つだけ WA になった。


2020年11月21日 (土)

最終更新: 2020-11-22T08:26+0900

[AtCoder] AtCoder Regular Contest 108C 問題 Keep Graph Connected

コンテスト中に問題文は理解していたと思う。文は。問題まで理解していたかは知らない。

  1. 頂点対抗で辺の奪い合いをする。
  2. 各頂点は自身に繋がる辺からこれはと思うグループをひとつ選び、それら辺に共通する番号を名乗る。
  3. このときその頂点に直接繋がる他の頂点は同じ番号を名乗ることができなくなる。
  4. そうして全頂点がちょうどひとつの番号と辺(のグループ)を選び取ったとき、選ばれた辺で全体がひとつに繋がっていればそれが答え。

これを DFS で探索しようとした。だめな選択に早々に見切りをつけて手戻りを減らすために、選択肢の少ない頂点に優先して選ばせようとした。

あとで提出して確かめる。TLE になるならさらに考えないといけない。WA になるなら問題文を読み直さないといけない。


あ、選ばなくていい頂点もあるのか。木の根に相当する頂点。選ばれる辺の数は N-1 以上になるから必ずなにがしかの木+余分な辺になるわけだけど、それがどういう意味を持つのか。最後の頂点だけ選べなくてもいいってだけ? わからなくなってきた。


2020年11月11日 (水)

最終更新: 2021-02-20T23:02+0900

[AtCoder] 第四回 アルゴリズム実技検定

自分の提出第一回第二回第三回

今回は K 問題までたどり着けなくて、J 問題で詰まった。まだ解けていない。特定のカテゴリの入力が全滅しているから、見落としているパターンがあるし、それを除いてもまだ AC は遠そう。だけど ABC184の E 問題 Third Avenue は解けてるんですよ>20201122p01.03。不思議だなあ。

その後 K 問題は解けたし、なんなら L 問題も解けたけど、時間はかけた。そして M 問題。

 M 問題 筆塗り

まだ3つの TLE に阻まれている。

何について繰り返すか、その通りがかりに素早く答えを出すためにどんな最適化されたデータが準備できるか、というのが考えどころ。

実行時間の制限が長めの4秒ではあるけど、制約上の上限がどれもこれも 10^5 だから、何かについて繰り返しているあいだに探索やら配列埋めやら時間がかかる処理をするわけにはいかない。

たとえばクエリごとに色記録配列を埋めるとか、辺(=頂点集合を左右に分ける)ごとに関与するクエリを逆順に検索するとかは間に合わない。Ruby では間違いなく。

 提出 #18035280 (TLE×18 / AC×16 / 4419 ms / 234280 KB)

Array にはない ^ メソッドが使いたくて require 'set'; した。「対称差」を求めるメソッドらしい。しかし遅い。

 提出 #18036165 (TLE×9 / AC×25 / 4445 ms / 1224160 KB)

3つの演算子(+, -, &)を使って自分で Array#^ メソッドを実装した。+ の代わりに | メソッドを使うこともできるが速くなる気がしない。まだ遅い。

 提出 #18053537 (TLE×3 / AC×31 / 4416 ms / 210696 KB)

bsearch_index と concat で Array#^ メソッドを実装した。演算子を使ったシンプル実装より必ずしも速くなるわけではないが、遅くなるのは TLE になるほどではない小さいケースだし、直線に近い(色リストが長くなりやすい)木では有利になるためか TLE が減った。しかし残った3つの TLE (random_17.txt, random_19.txt, random_28.txt) はどの提出に対しても実行時間が上限に張り付いたままで、打開するヒントが見えない。どういう形の木なのか。

 方針
  1. 根を1つ決めて、木全体を葉から根へ遡るように処理する(なぜか根が上)。
  2. ノードは色リストを持っている。色は z-order で識別する。z-order は 1 から Q の範囲の値をとる。
  3. 子が持つ色リストを親のものにマージしていく。マージする過程でペアができればリストから取り除く。
  4. ノードが持つ色リストのうちもっとも手前にある(z-order が大きい)色が、そのノードと親を結ぶ辺の色となる。

N 個のノードについて繰り返しながらソート列(色リスト)のマージを繰り返すのが、時間的にもメモリ的にも厳しい。だけどこれが嘘のように時間制限をクリアできる魔法があるとも思えない。十分にストレートで迷いのないコードだと思う。この方針のままなんとか滑り込みたい。

「打開するヒントが見えない。どういう形の木なのか」と書いたけど、直線の反対ということで子供が 100, 1000 あるような木を用意したらてきめんに遅くなった。どうしようかな。

 提出 #18059514 (TLE×2 / AC×32 / 4418 ms / 201508 KB)

変更点はソート済み配列から最大値を取り出すのに max メソッドを使っていたうっかりの訂正と、子の色リストを得るのにランダムアクセスをやめてスタックから連続する領域を取り出すようにしたこと。これで1減って残る TLE は2個。

4400 ms が 4200 ms になったりするとあとちょっとだとわかるんだけど……。

あるノードに合流してきた色リストは LCA と z-order がともに昇順になるように並べ替えることができて、そこから外れる色は色塗りの出番がなくて無視できるんだけど()、それで良くなるものか……。

z-order が大きければ他の色より前に出られる。LCA が小さければ前にある色が LCA に到達して退場するのを待てる。どちらでもなければ前に出る前に退場させられる。

 提出 #18069462 (AC / 1394 ms / 106192 KB)

やった!!!

LCA が正解だったみたい。木を遡りながら色リストをマージするのは同じだけど、LCA を利用してリストを短くしたら TLE が解消した。

うれしい。とってもうれしい。ここ2、3日トイレでもお風呂でもふとんの中でも考えていた。あっさり AC されているとやる気が萎えるので見ないようにしていたが、Ruby で AC 一番乗り。

ところで PyPy3 のこのシンプルかつ Python 系で一番速い提出 #18047488 (819 ms) はなんの魔法だろう。半分以上が入力の処理で、残りでヒープの出し入れをしているだけ。

JIT で速いから余計な手をかけないで済むということなら Ruby には関係のないことだけど、考察が足りていなくて自分のアルゴリズムがヘボだというなら、学ばなければいけない。

それはそれとして、LCAの確定を待つ色のリストはソート済み配列をやめてプライオリティキューにすべきだし、lambda M の中の Array#slice! と Array#insert は配列に相応しいメソッドではない。配列を酷使しすぎている2点に改善の余地がある。

 提出 #18102965 (Crystal / 559 ms / 56432 KB)

初めて Crystal を書いた。色々言いたい。

  • Web で見られるランゲージリファレンスがない。ドキュメントがあることとアクセスしやすいことは必須。リファレンスだけあればいい。getting started はいらない。
  • Ruby を知っているからこそ罠が多い。
    • delete_if と inject メソッドがない。reject! と delete_if は完全に同じではないし、reduce と inject がただのエイリアスなら用意しないのは罠でしかない。

      inject は配列の各要素のあいだに演算子を挿入するイメージのメソッドらしい。それを読んでから inject の仕様に悩んだことはない。

    • lambda メソッドがない。テキトーに Proc.new と書いてみたけどダメだったので -> () {} と書いた。アロー記法は好きではない。

      パラメータには型注釈が必須だったけどコロンの前か後ろか両方にスペースが必要だったらしい。詰めて書いたら「ダメだ。我は ) を所望する」と怒られ、素直に ) を書いたら型注釈を付けろと怒られる無限ループ。

      後付けするなら記号は選ばなければいけない。Ruby の仕様(メソッド名と文字リテラル)なら条件演算子はむしろないほうがいいし、だけど条件演算子とシンボルリテラルは現実に存在しているし、記号は選ばなければいけない。

    • each メソッドが self を返さない。なぜ?
    • ブロック変数名に _ が使えない。なぜ?
    • 定数に多重代入ができない。なぜ?
    • 定数と変数が同じスコープ、見た目通りの実行軸にないように思う。

      n,q = gets.split.map(&.to_i)
      N = n; Q = q

      これは変数 n が定義されていないというエラーになった。

      (追記:下の方で答えを書いてたかも。「map が遅延評価? .to_a を付けないと期待したタイミングで副作用が起こらない。」 map が遅延評価であることと代入が行われないことは別だと思うのだが違うのか。違う(別ではない)なら大変に興味深い Crystal の特徴だと思う)

    • &:to_i と書いていたものを &.to_i と書かせる。

      .to_i が Crystal という言語を構成する部分として定義されており、プログラマが操作可能な対象であるなら評価は変わるけど、単に & という目印のバリエーションとして &. を追加したなら、ただの好き嫌いでただの罠。

    • ブロックパラメータは必ず1つ? {|i,|} とか {|i,j|} とかできない雰囲気。それとも StaticArray だったから?
    • map が遅延評価? .to_a を付けないと期待したタイミングで副作用が起こらない。
    • Enumerator のチェインができない。具体的には map.with_index と書くと map にブロックパラメータが必須だというエラーになった。スペックを読んだら map_with_index というメソッドがあったので使ったが、map だけ?
    • nil が非常に煩わしい。Ruby はすべての変数が Nullable だし、偽と評価される値が nil と false だけなのもあってあらゆる部分に nil が現れる。そのすべての nil に対応を迫られる。一例が gets.to_i とは書けなくて gets.to_s.to_i と書かされるところ。たぶん (gets||"").to_i でもいいとは思う。

      実行時エラーをコンパイルエラーにしたいのだとしよう。だけど視野が狭い。こちらは gets が nil を返すかどうか、そのような入力が与えられるかどうかに関する知識を持っており、nil が返るような入力が仕様違反であることを知っている。バグがあったときに修正すべき対象は Crystal のソースコードではなく、そのような入力を与えた外部にある。事の決定権はコンパイラにはない。

      &. によるメソッド呼び出しに対応していれば話は違った。

    • 空の配列から pop できない。空の配列を reduce できない。これらも nil がらみであろう。
    • 空の配列、空の Hash の作成がめんどくさい。[] とか {} とか書けない。とりあえず領域を確保するために [nil]*N と書くのもタイプミスマッチで都合が悪い。
    • "1(スペース)2".to_i がエラーになった。1 を期待していた。0 をデフォルトとして解釈できるところまで解釈することを .to_i には期待している。

すべてドキュメントの不足が悪い。スペックしか頼れるものがなかった。


俺は人類の手には多少余るとしても、プログラマを信頼し、力を与えてくれる言語が好きだ。安全のためと称して枷をはめようとする言語は選ばない。安全な(なまくら)は退屈だ。

では Ruby の切れ味は? Ruby はプログラマがやりたいことの邪魔をしないのがいい。Ruby がコードゴルフに向いているということとも関連する。キーワードやら形式やら、本筋の処理と無関係でありながら書かなければいけないお約束が少ないということ。

Crystal の型はどうか。プログラマに力を与えるためではなく、処理系が力を得るためにプログラマが受け入れる枷だというのが、少し触っての印象。枷を受け入れるなら C++ が選択肢に入る。

const 教の信者というのは最も“const と書きたくない”人種のことだと自認している。const という当たり前のことを、どうしてあちこちそちこちに書いて回らなければいけないのか。所有権も魅力的だけど、const と書かなくてもいいという1点でまず、Rust の評価が高い。

C++ も Ruby も好きだけど弱点がある。Rust には期待ができる。でもコンパイラが起動できないんだよなあ。「rustc.exe - エントリ ポイントが見つかりません。プロシージャ エントリ ポイント K32EnumProcessModules がダイナミック リンク ライブラリ KERNEL32.dll から見つかりませんでした。」 本でも読むか。

 別解@2021-02-20 提出 #20275440 (AC / 1168 Byte / 1081 ms / 73084 KB)

#18069462 と比べて、-1016 Byte / -313 ms / -33108 KB。短くて速くて省メモリ。

先に書いたように、「クエリごとに色記録配列を埋めるとか、辺(=頂点集合を左右に分ける)ごとに関与するクエリを逆順に検索するとかは間に合わない」のはたぶん間違いないけども、2つを混ぜてクエリの逆順に効率良く色記録配列を埋めるところまでは考えが及んでいなかった。

時間軸を反転することで、一度塗ったところを再度塗らないでスキップしたい

その方針でやってみれば、前半はほとんど同じことをやってるんだけど、下準備を終えたあとのメインループでは、ソート済み配列をマージする代わりにスキップしながら親をたどっていた。親をたどる方が短く書けて簡単!


2020年11月07日 (土)

最終更新: 2021-05-07T15:06+0900

[AtCoder] AtCoder Beginner Contest 015D 問題 高橋くんの苦悩

DP の基本形といっていいほど典型的な DP。見え見えの誘いに乗りたくなくて他の解法を考えてみたけど思い付かなかった。それに心配しなくても Ruby ならではのお楽しみポイントがちゃんとあった。

実行時間の変遷が見どころ。

 提出 #17933561 (TLE×7 / AC×40)

N×K×W のループは上限が2500万回であり、Ruby で TLE を避けようと思ったら桁を1つ減らさないといけない。予想された結果。

 提出 #17934141 (AC / 1033 ms)

N のループが K 回に達するまでは K のループを K 回まわす必要がないよねっていう節約作戦で AC になった。制約は K <= N <= 50。

 提出 #17934762 (AC / 554 ms)

提出一覧が 1000 ms を超えるグループと超えないグループに分かれていたので中を見たら、添字と値が入れ違っていた。

  • 遅い方 - Array[K][W] = sum of B (K<=50, W<=10000)
  • 速い方 - Array[K][sum of B] = W (N<=50, B<=100, sum of B<=5000)

B の値域が(W にくらべて)かなり狭い範囲に限定されているのがポイントで、速い方はループで走査する DP 配列のサイズがおよそ半分で済む。

 提出 #17935118 (AC / 111 ms)

2番手以降の集団をダブルスコアで突き放す zazaboon さんの提出 #11417636 (150 ms) を調べた結果。

  • DP 配列のサイズを制約上の上限ではなく、テストケースに応じた必要最小限のサイズにする。
  • B を小さい順に処理することにより、ループの初期に更新する DP 配列の範囲を限定する。
  • 答えを見つけたら即終了する。

以上の点を真似したのに加えて、考えられるこちらのアドバンテージが

  • Ruby のバージョンが上がっている。(2.3 → 2.7)
  • 最初に簡単なチェックで N を減らした。
  • 初期値を整数にした。(「とりあえず大きな数としての初期値に Float::INFINITY を使うと、10**9 のような整数型を使うより比較にコストがかかる」)
  • 演算子を極力書かないようにした。(vsum+1 は美意識とボキャブラリに起因する例外)
  • 配列参照を極力書かないようにした。特に二重のものはひとつも書かなかった。
  • 見た目がださくても a = [a,b].min と書くより a = b if b < a と書いて代入を省略できる方が速い。(だけど本当は宣言的な変数定義がしたい。操作ではなく結果について書きたい)
  • よくわからない処理を真似しなかった。41 行目の if と 44 行目。

前後のリストを比べると後ろは問題と関係のない比較的どうでもいい内容が並んでいるね。

 Python のこの提出 #287540 (AC / 66 ms)

いまのところの Python 最速。AB 配列を幅対重要度比でソートしてからの DFS なんだけど、すごいのが _greedy_by_width と _greedy_by_num という先読み関数で探索の打ち切りを判断しているところ。それでペイするんだってところと、1枚のスクリーンショットを刻む発想が(だって刻んだ画像の価値はゼロですよ。常考)。

使う使わないの二択だと比率がちょっと悪くても残った隙間にぴったり収まる方が重要度を高められることがある。先読みでその可能性を取りこぼしては答えを誤る。だからあくまでも比率のいいスクリーンショットから使う。ぴったり収まらないなら切り取って収まる分だけ使う。そういう考え。

最近別の問題を自分が DFS で解いたときのことだけど、「さっきの TLE 提出を微修正したら AC になった。事前に XY 配列をソートするだけ。二択による手戻りを最小限にするために、選択肢の優劣が明らかで覆りにくいものを最初に選ぶようにした」なんてぬるいやり方よりずっと突き詰めている。すごいなあ。