/ 最近 .rdf 追記 設定 本棚

脳log[2020-11-01~]



2020年11月01日 (日)

最終更新: 2020-11-06T01:42+0900

[AtCoder] AtCoder Beginner Contest 181/D,E,A

 D 問題 Hachi

ほんの一瞬、1,10,100,1000,10000,... を8で割った余りに与えられた数字を掛け合わせて8の倍数を作るゲームかと思ったけど、組み合わせが膨大で無理そうだった。

こういうのって8の倍数が千とか万とかキリのいい数字になったらそれより上の桁の数字が何であっても千とか万の倍数であり8の倍数だから無視していいんだよねってことで irb で実験したら、4桁目から上はもう無視していいみたいだった。1000 = 8×125。3桁で8の倍数が作れれば良し。

 提出 #17805410 (TLE)

物量に頼った雑なやり方で TLE を食らった。

 提出 #17808009 (AC)

お留守だった脳みそをなんとか働かせて tally メソッドで集計をすることにした。

 E 問題 Transformable Teacher

とくに悩むところはなかった。全体にペアの差を最小にしたいならソートして隣同士で組み合わせるしかないと思った。あとは妖怪先生(え?わたし?)をどこに潜り込ませるかだけ。

データ構造も悩まなかった。右の人と組む場合と左の人と組む場合の2種類の階差数列が必要だな、定数時間である範囲の数列の和を求めるには累積和だな、と。

 提出 #17820870 (AC)

惜しむらくは提出時刻がコンテスト終了の6分後だということ。

こうなってみると B 問題 Trapezoid Sum で等差数列の和の式を悠長に組み立てていたのが悔やまれる。何回やっても全然答えが合わねーの! いま検索したら Wikipedia に n(a1+an)/2 みたいな、自分が考えてたのよりずっと簡単な式が書いてあったりして、あほくさくなってくる。ちがう、お前があほなんだ。この式に16分かけた>#17793713。展開して整理する時間も惜しかった。最後なんて式はもう合ってるのにサンプル入力のコピペに失敗して答えが合わないせいで式の検討をやり直したからね。

次の C 問題 Collinearity ではさっさと2点を通る直線の式(軸に平行な直線にも対応したもの)を検索している>#17796631。7分かかってるのはタイピングとサンプルを使ったテストの時間。

 A 問題 Heavy Rotation

こういうコードをゴルフ的だと考えるとしたら、それは考え違いだと言いたい(誰に向かって言っているのか謎だが)。

puts %w(White Black)[gets.to_i&1]

比較対象は例えばこんな感じ。

if gets.to_i.even?
	puts 'White' 
else
	puts 'Black'
end

2番目のようなスクリプトを書く前に自分が考えること……

  • 出力は1回1行だけしか行われないのに puts が2つ見えるのは読み手にやさしくない。
  • もし~ならこうする、さもなければこうする、という構成はあまりに手続き的。もうすこし進んだパラダイムを学んでも良い頃合いでは?

    そうする理由はかっこいいからとか新しいからとかではなく、変更に強くなるのとコードの複雑化を抑えることができるから。

    何度かこの日記に書いてるけど、バリエーションを表現するのにコードではなくデータを使うということ>2015051420181029

  • データ(Black と White の文字列配列)が用意できたらあとは入力(gets.to_i)と出力を最短で結ぶシンプルで無駄のないコードを書くだけ。2の剰余を添字にすればよい。あえて迂遠な書き方をする普遍的な理由なんてない(バカと可読性は個人の属性)。これまで if (a == b) return true; else return false; などと書いてきたなら今すぐ悔い改めよ。

    ま、それは極端だとしても、コアとなるコードは「何かを出力する」となるべきであり、その何かを作るのに if 文を書いたり、if 文を含んだ関数を一度だけ呼び出したり、事前に用意しておいたデータファイルを読み込んだりするのが良い。

  • 「もし~ならこうする、さもなければこうする」という型のコードは2つの「こうする」に無制限に無関係な処理が書けるし、何もしないこともできるし、目的に対して自由度が高すぎる。もっと制限の強い型にはめれば読み手にいらぬ想定を強いることがない。

    だけどアクセス制限にしろ型にしろ、制限を強める方向で書くには頭を使うのだな。おつむが弱いとカオスをばらまくことが避けられないのだな。

最終更新: 2020-11-05T19:41+0900

[AtCoder] AtCoder Beginner Contest 181F 問題 Silver Woods

コンテストは終了しているので落ち着いて考えた。

  1. それぞれの点について、取り得る選択肢は上を通るか下を通るかの二択。
  2. 上を通ることを選択した点と下を通ることを選択した点のペアについて考えれば、必ずその2点の間を通過している。
  3. 総当たりだと最悪の場合に 2^{100}(=約126穣)通りになって大変。
  4. 見込みのある選択肢を優先すればなんとかならんか?

 提出 #17835277 (TLE×11 / AC×49)

ダメでした。まあね、優先度を付けても裏をかくような難しいケースが良くなるわけじゃないからね。

Python の提出一覧を見たら2桁 ms の AC 提出がいっぱいあった。これはコードを書く前にもうちょっと考えなければいけないな。


F問題は、直感的に「釘と直線をグラフの頂点として、ユークリッド距離をコストにして辺を貼り、パスのコストを「通る辺のコストの最大値」としたときに直線から直線への最短距離÷2」が答えだと感じたので、それをダイクストラで実装したら通った。

ええっとですね、まずそれが直感的にわからないし、そのわかったことを読ませてもらってもそれがどういうことなのかわからないのですね。(そもそもユークリッド距離の概念が曖昧。名前だけ知ってる編集距離なんかと比べて一番普通の距離だと思うけど、そう思うだけ)。

前半はまあまあ想像できる。全頂点を一筆書きして通路を左右に分ける線を引いたとき、最も広い点と点のあいだに円を通すということだろう。だけど第3の点が邪魔をして最も広い点間を通れないことがあると思う。そこから後半の「最短距離÷2が答え」につなげられない。

 @2020-11-04

邪魔をしている第3の点が最も広い点間を挟むどちらかの点と直接繋がる経路というのが、より小さいコストを持つ経路なのであり、(でないと邪魔できない)、最短経路というのはそういう邪魔が入らない経路のことなのだろう。たぶんね。

答えが示されているからこそ、こうしてこじつけ気味にでも納得のいく解釈がひねり出せたけど、これが「直感的に」ねえ……(遠い目)。


@kyopro_friends「アライグマ「F問題は……「半径rの円が通れる」っていうのは、「円の中心が障害物からr以内にならない」ってことだから、逆に障害物の方を半径rの円にしちゃえばいいのだ!」

@kyopro_friends「アライグマ「道がふさがったらダメだから、障害物同士の距離を全部計算しておいて、距離が短いところから順にくっつけていって、上の壁と下の壁がくっつくときが答えなのだ!」

これはわかる気がする(図もあるし)。でも逆にこのツイートを読んでもダイクストラ法で実装することがわからないね。

 提出 #17842898 (AC / 819 ms)

上のツイートとは関係なくさっきの TLE 提出を微修正したら AC になった。事前に XY 配列をソートするだけ。二択による手戻りを最小限にするために、選択肢の優劣が明らかで覆りにくいものを最初に選ぶようにした。

いつの間にか Ruby でも AC をとっている人がいて、しかも実行時間が2桁 ms なんだけど、UnionFind を使っているみたいだった。どういうこと?

あ、連結成分の管理か。コストの低い辺からつないで最小全域木ができあがったときに最後につないだ辺のコストがそのまま答えになる。へー、クラスカル法と UnionFind が今初めてつながった。UnionFind とグラフに関連があるらしいのを今まで見て見ぬふりをして考えてこなかったツケであるな。こういう問題(「Reachable Towns」「Line++」)が全然グラフの問題に見えないんだよなあ。

そうしてみると問題文中で(N 本の)釘とされているものを Silver Woods と表現した問題名は、「木だよ、森だよ、グラフだよ」というヒントだったのだな。おしゃれ。

ところで、自分の提出も2つのケースが 819 ms と 170 ms なのを除けば2桁 ms で済んでいる。オーダーが劣ってもだいたい良好ってことでどうですか?

 提出 #17848105 (AC / 93 ms)

ソート方法でガチャを引いたら2桁 ms になった。オーダーは変わっていないので入力の引きとソート方法の組み合わせが悪いとやっぱり遅くなるはず。ランダム入力を使って実行時間を体感でテストしてるんだけど、逆順にするだけで十数秒が一瞬になったりする。

メインの処理で if-else-end を省いて2+2行だったものを3行にまとめたけど、実は再帰呼び出しの回数が多少増える無駄がある。だけど事前のソートで無駄が生じにくいお膳立てはしてあるつもりだし、ストレートで整然とした文字の並びが他には代え難い。

メインの処理2行目の d2 変数への代入だって変数の使い回しで省略できるし*、3行目で再代入している d1 変数はそれから使っていない。しかしストレートで整然とした文字の並びが……。


たぶん通ると思う。265 バイト。$$ が 200 以上だったらいいなという運任せ(※多少小さくても入力次第で問題なし)。単に minify しただけで見るべきところがない。リテラルとか長いメソッド名とか多くの変数とか似たような型の処理とか、1個あればたくさんなものが多すぎるよね。

_,*z=$<.map{_1.split.map &:to_f}
Y=z.sort!.map{|x,y|[y+100,*z.map{Math.hypot x-_1,y-_2},100-y]}
F=->i,d,a,b{
z=(t=Y[i])?(*c=i+=1
e=F[i,e,a+c,b]if z<e=[*t.values_at(*b),d].min
F[i,d,a,b+c]if z<d=[*t.values_at(*a),d].min
z<e&&F[i,e,a+c,b]
z):d}
p F[z=0,$$,[0],[-1]]/2

うーん、どうだろう。219 バイト。答えの確かなテストケースがないと自信ない。

e,*z=$<.map{_1.split.map &:to_f}
Y=z.sort!.map{|x,y|[*z.map{Math.hypot x-_1,y-_2},100-y,y+100]}
A=[-1],[-2]
F=->i,d{(t=Y[i])?[A,A.rotate].map{(_1<<i;F[i+1,e];_1.pop)if z<e=[*t.values_at(*_2),d].min}:z=d}
F[z=0,$$]
p z/2

 提出 #17867027 (AC / 220 Byte)

よく考えたら AC 提出とランダム入力で答え合わせができるのだった。

$$ はダメだったので(#17866997)、1バイト増えて 220 バイト。Windows ではプロセス ID は4桁だったんだけど。

まあしかし、これだけ長いとこのスクリプトひとつとっても、いくらでも縮めどころが見つかりそうではある。

 提出 #17868705 (AC / 217 Byte)

3文字減。ちなみに、変更に伴って入れ替わった2数を、どっちでもいいだろうとそのままにした結果は TLE だった>#17868682。「実は再帰呼び出しの回数が多少増える無駄がある。だけど事前のソートで無駄が生じにくいお膳立てはしてあるつもり」が裏目に出た当然の結果なんだけど、わからんもんかなあ。

3文字減った理由がなかなか味わい深い(と思う)。Ruby って C++ などと違ってあらかじめ配列のサイズを決めておいたり、あらかじめ読み込む行数を想定しておいたりせずに、いきなり入力を配列に読み込んで行数は配列のサイズで後から知ったりする。だから後続の行数を知らせる一行目は読み捨てても困らない。

この問題もそうだったんだけど一行目だけ列数が異なっていることも多くて、そうすると共通のルーチンで読み込めないせいで取り扱いに手がかかる(文字数を費やす)から、やっぱり読み捨てたくなったりする。

今回も一行目は読み捨てていて、ただそれにも gets やらプレースホルダとしての変数名が場所を取るわけなので、脚注に書いた不都合を回避するための変数の先行定義を兼ねさせていた。

そのプレースホルダであり先行定義である変数の、本来用のない中身(定数 N を唯一の要素とする配列)が役に立ったよ、という話。


ゴルフせずに普通に書くとこうなる(普通の定義が狂い気味)。

_,*XY = $<.map{|ln| ln.split.map(&:to_i) }
D = XY.sort!.map.with_index{|(x,y),i|
	[*XY[0,i].map{|x1,y1| Math.hypot(x-x1,y-y1) },1e2+y,1e2-y]
}
F = lambda{|x,d,i,up,dn|
	next d unless di = D[i]
	d1,a1 = [*di.values_at(*dn),d].min,up
	d2,a2 = [*di.values_at(*up),d].min,dn
	d1,a1,d2,a2 = d2,a2,d1,a1 if d1 < d2
	_,x, = a1<<i,F[x,d1,i+1,up,dn],a1.pop if x < d1
	_,x, = a2<<i,F[x,d2,i+1,up,dn],a2.pop if x < d2
	next x
}
p F[0,200,0,[-2],[-1]]*0.5

メインの処理が3行から2行へと、ゴルフをする過程で気がついた無駄が省いてあるのと、ゴルフをしていると省略せざるを得ない d1,a1 と d2,a2 のスワップが再帰呼び出しを多少減らす見込み。ゴルフをしているとまとめざるを得ない2つの似た処理は、並べた方が速い。しかし誤差程度にしか違わない。むしろ入力次第でひどく悪くなるのがクラスカル法とは違うところであり、覆せないオーダーの差。

深さ優先探索はひとつの経路に縛られるし、幅優先探索はひとつの深さに縛られる。辺に優劣がないならそういうひとつの決まりに従って網羅的に探索して咎められないとしても、そうでない場合は、もっと一般的なグラフアルゴリズムを使うのが効果的だということなんでしょう。さっきは UnionFind についてだけ触れたけど(「UnionFind とグラフに関連があるらしいのを今まで見て見ぬふりをして考えてこなかったツケであるな」)、DFS と BFS がグラフアルゴリズムだっていう認識も実は全然持っていない。見えないんだよなあ。

* while/until などの条件節で初登場する変数が、なぜか後置修飾される本体処理で利用できないのが不思議で不満。条件式はループに先立って必ず評価されているはずなのに。begin ~ end while ~; とは違うのに。


2020年10月31日 (土) 過去を振り返ると「あの頃の俺は賢かったなあ」という感想がよく出てくる。例えば AtCoder を始めたばかりで ABC の E 問題の難しさ加減や ABC と AGC の違いがわからなかった頃。例えば高校生の頃。所詮自分なので高が知れているということはあるけど、それでも今となってはついていけない感じがする。集中の度合いが違うだけかな。だといいな。


2020年10月30日 (金) 胸ポケットから落ちたシャーペンが戻ってきた。ドアの外の地面に落ちてたことがあるし、車内に落ちてたこともあるし、机の下の段ボールにナイスキャッチされていたこともあるのだけど、今度こそもうだめだと思っていたら、拾った人が封筒に入れて郵送してくれていた!!! どなたかわかりませんがありがとうありがとうありがとう。■さすがに落としすぎだと思ったので「胸ポケット用ペンケース」なる商品を買うことにした。ポケットはボールペンのインクで黒くなってるし、クリップで挟むフチはほつれてるし、穴が空いたのを補修してあるくらいなので、一挙四得ねらい。


2020年10月23日 (金) 「しんごうが青のときにわたりましょう」という看板を道路脇に見かけた。あまりに当たり前の内容。だけど小学生の、それも低学年のうちはそういうことを学ぶ段階なのかもしれないね。目の前が小学校だったし。ところで、信号が青でさえあればいいのなら、わずかな時間を除いて交差点のどこかに必ず青信号を見つけることができると思う。「しんごうが青のときにわたりましょう」で大丈夫?(ひねくれ者) 「正面の信号が青の……」ならいいだろうか。いいや、そんなことが書いてあった日には自分はカニ歩きを始めてしまうような子供である(おちょうし者)。「進行方向の信号が青の……」を一応の結論とした。進行方向にある2つ目3つ目の信号を見るような子供の面倒までは見きれません(そんなばか者はいない)。


2020年10月21日 (水) 最近肉食を覚えました。半額で1000円以上するお肉(国産、白い部分がそこそこ目立つ)と、普通に500円を切るお肉(米産、白い部分はほぼなし)を食べ比べたけど、米産の方が自分は好きかな。おいしい食べ方を知らないだけだと思うけど、知らないのだからおいしく食べられてしかも安い米国産を選んでしまうな。肉が主食の民ではないので胃にもたれる肉と脂をご飯で中和しながら食べてます。


2020年10月19日 (月) どうしてあの人はいつもいつでも人の動線を遮るような邪魔な場所に物を置くのかという疑問に対する完璧な答え。人が通らない所の床はすでに物で覆われている。


2020年10月18日 (日)

最終更新: 2020-10-31T00:45+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 に規正することができていなかった。

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


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

いや違う。比較対象は上限が 10^9 の 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 で間違いない。

2^N2^{N-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 がある。そういうのは Crystal (Ruby に似たコンパイル型言語)で投稿するという手があるらしいが知らないので。

 提出 #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 のような整数型を使うより比較にコストがかかる。

    余計なコストがかかるはかかるんだけど、今の段階に至っては初期値は nil で構わないのだった。比較されない。

  • こんな感じの配列を事前定義すると手元ではちょっと速いようだけど、スマートじゃないので却下。

    01 = [[[0],[]],[[],[0]]]
    (1...N1).each{|n|
    	01.concat 01.map{ next (_1<<n)[0,_1.size-1],_2+[n] }
    }
    (1<<N1).times{|v|
    	c = CV[v]
    	0,1 = 01[v]
    	0.each{|f|
    		f2 = C[f]
    		CV[v|1<<f][f] = 1.map{|t| f2[t]+c[t] }.min||s2[f]
    	}
    }

2020年10月17日 (土)

最終更新: 2020-10-16T23:56+0900

[WR250R] バイク走行動画 (合計 6 分)

1号線を走るくらいならこういう道を選ぶよね。このルートに仮免許練習中の教習車を送り込むコースが存在している模様(よく見かける)。そんな教習うらやましいにも程がある。

音・サイズ(100 MiB 超)注意。

116 MiB / 3 分

127 MiB / 3 分


2020年10月16日 (金) Twitter で LED シーリングライトの焦げ(?)に関する話題を読んでいたら、「さすが業物様」とか「業物さんの影響力」とかのやりとりが目に入って、どこの2人目のギョーブツたんかと思ったらアイコンが電柱から半身でそのものだった。なつかし。■中の人が同じかまでは知りようがないけど、偶然の名前かぶりではないということへの感想>なつかし。


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年10月12日 (月) [AtCoder] Twitter での企業コンの話題。自分も最初は企業コンは対象外だと思ってスルーしていた。■知らなかったこと1。企業コンに ABC 級と ARC 級があること。社長さんのツイッターで知りましたよ。■知らなかったこと2。ARC と企業コン(の難しい方)が別物だということ。最近 ARC 開催の土壌が整ったとかで立て続けに開かれたけど、自分が AtCoder に参加して1年以上も ARC が途絶えていたから、ARC は終了した名前で、企業コン(の難しい方)として存続しているのだと理解していた。ABC 級の企業コンがあることも知らなかったし。■知らなかったこと3。問題の難しさを A~F ではなく配点で予測すること。配点が(見積もりとはいえ)絶対尺度だということ。AtCoder をはじめたての頃は恐ろしいことに、AGC の A 問題と ABC の A 問題を区別する基準を持っていなかった。「A 問題よりは難しい B 問題」とか「たかだか B 問題に一日散々苦しんでおいて」とかの感想がそれを反映している。700点問題と500点問題なんだよなあ……(最近は400点問題も解けない)。


2020年10月07日 (水) [AtCoder]「【お知らせ】AtCoderの問題文が表示されない不具合が報告されておりますが、ブラウザのバージョンを最新のものにアップデートすることで、正常に表示されるかと思います。 なお、Internet Explorerはサポート対象外となっております。ご了承ください。」■うん、見えない。atcoder.jp と cloudflare.com のスクリプトだけを許可してたけど、他の、google-analytics.com 以外のスクリプトを許可しても見えない。インストールできる最新版が Firefox ESR 52.9.0 なんだけど、これでは見えない。CSS を切ったら見えたけど、数式が読みにくくなる。■今の段階でエラーになるスクリプトは次の1か所だけで、ページ埋め込みスクリプトの <script>$(function(){$('var').each(function(){var html=$(this).html().replaceAll('<sub>','_{').replaceAll('</sub>','}');$(this).html('\\('+html+'\\)');});});</script> が「replaceAll is not a function.」というエラーになっている。これ1か所だけに対応するコードは String.prototype.replaceAll = function(s,r){ return this.split(s).join(r); }; とか、グローバルフラグを付けた正規表現パターンを第1引数にして String.prototype.replace を replaceAll の代わりに呼び出すとか。■atcoder.jp から送られてくるページの埋め込みスクリプトを書き換える方法がわからなかったので、replaceAll 関数を事前にブラウザに定義することにする(userChrome.js)。しょうもないもんに引っかかってるなあと思うけど、おかげで対策が簡単で助かる。今はまだ?■……と思ったら、「@chokudai「さすがにこの対応状況で入れるのは時期尚早でしょ、ってことでちょっと修正コミット入ったっぽい caniuse.com/?search=replac…


2020年10月03日 (土) 平均寿命と平均余命。■社会科か家庭科か忘れたけど、学校で習ったときは結局よく理解できなかった。教科書には平均寿命とは0歳時点での平均余命である、みたいな定義が書いてあるんだけど、そのことの意味が腑に落ちなかった。今でもうっかりするとあやしい。■どういうことか。今年の発表で日本人の平均寿命が86歳(仮)ですよ、みたいなことが言われるとする。60歳の人が、じゃああと26年は生きられそうだなと考えるのは、概ね間違いではないけど、期待に一方的な偏りがある。現在60歳の人は60年生き延びてきた実績を持つ選ばれし者なので、平均して26年以上生きることが期待される。それが60歳の平均余命であり、0歳の平均余命である平均寿命との違い。たぶんね。■しかし、平均寿命の根拠となるデータは過去のデータであって、生まれたばかりの赤ん坊の寿命はこれからの環境に左右される。平均寿命が当てになる根拠って何だろう。大きな変動がない? トレンドを加味した予想(外挿)?■平均寿命は86歳(仮)ですよ、86歳の平均余命は何年ですよ、というのが最も当てになる数字ではなかろうか。ま、こんな素人考えの及ばないところまで保険会社の人は考えていることだろう。儲けに関わるからな。■平均寿命のイメージって、人口を年齢別に分けて、それぞれに平均余命を足して平均したものって感じ。実際どうなんだろう。