最終更新: 2020-11-06T01:42+0900
ほんの一瞬、1,10,100,1000,10000,... を８で割った余りに与えられた数字を掛け合わせて８の倍数を作るゲームかと思ったけど、組み合わせが膨大で無理そうだった。
こういうのって８の倍数が千とか万とかキリのいい数字になったらそれより上の桁の数字が何であっても千とか万の倍数であり８の倍数だから無視していいんだよねってことで irb で実験したら、４桁目から上はもう無視していいみたいだった。1000 = 8×125。３桁で８の倍数が作れれば良し。
物量に頼った雑なやり方で TLE を食らった。
お留守だった脳みそをなんとか働かせて tally メソッドで集計をすることにした。
とくに悩むところはなかった。全体にペアの差を最小にしたいならソートして隣同士で組み合わせるしかないと思った。あとは妖怪先生(え？わたし？)をどこに潜り込ませるかだけ。
データ構造も悩まなかった。右の人と組む場合と左の人と組む場合の２種類の階差数列が必要だな、定数時間である範囲の数列の和を求めるには累積和だな、と。
惜しむらくは提出時刻がコンテスト終了の６分後だということ。
こうなってみると B 問題 Trapezoid Sum で等差数列の和の式を悠長に組み立てていたのが悔やまれる。何回やっても全然答えが合わねーの！ いま検索したら Wikipedia に n(a1+an)/2 みたいな、自分が考えてたのよりずっと簡単な式が書いてあったりして、あほくさくなってくる。ちがう、お前があほなんだ。この式に16分かけた>#17793713。展開して整理する時間も惜しかった。最後なんて式はもう合ってるのにサンプル入力のコピペに失敗して答えが合わないせいで式の検討をやり直したからね。
次の C 問題 Collinearity ではさっさと２点を通る直線の式(軸に平行な直線にも対応したもの)を検索している>#17796631。７分かかってるのはタイピングとサンプルを使ったテストの時間。
こういうコードをゴルフ的だと考えるとしたら、それは考え違いだと言いたい(誰に向かって言っているのか謎だが)。
puts %w(White Black)[gets.to_i&1]
比較対象は例えばこんな感じ。
if gets.to_i.even? puts 'White' else puts 'Black' end
２番目のようなスクリプトを書く前に自分が考えること……
もし～ならこうする、さもなければこうする、という構成はあまりに手続き的。もうすこし進んだパラダイムを学んでも良い頃合いでは？
そうする理由はかっこいいからとか新しいからとかではなく、変更に強くなるのとコードの複雑化を抑えることができるから。
何度かこの日記に書いてるけど、バリエーションを表現するのにコードではなくデータを使うということ>20150514、20181029。
データ(Black と White の文字列配列)が用意できたらあとは入力(gets.to_i)と出力を最短で結ぶシンプルで無駄のないコードを書くだけ。２の剰余を添字にすればよい。あえて迂遠な書き方をする普遍的な理由なんてない(バカと可読性は個人の属性)。これまで if (a == b) return true; else return false; などと書いてきたなら今すぐ悔い改めよ。
ま、それは極端だとしても、コアとなるコードは「何かを出力する」となるべきであり、その何かを作るのに if 文を書いたり、if 文を含んだ関数を一度だけ呼び出したり、事前に用意しておいたデータファイルを読み込んだりするのが良い。
「もし～ならこうする、さもなければこうする」という型のコードは２つの「こうする」に無制限に無関係な処理が書けるし、何もしないこともできるし、目的に対して自由度が高すぎる。もっと制限の強い型にはめれば読み手にいらぬ想定を強いることがない。
だけどアクセス制限にしろ型にしろ、制限を強める方向で書くには頭を使うのだな。おつむが弱いとカオスをばらまくことが避けられないのだな。
最終更新: 2020-11-05T19:41+0900
コンテストは終了しているので落ち着いて考えた。
2^{100}(=約126穣)通りになって大変。ダメでした。まあね、優先度を付けても裏をかくような難しいケースが良くなるわけじゃないからね。
Python の提出一覧を見たら２桁 ms の AC 提出がいっぱいあった。これはコードを書く前にもうちょっと考えなければいけないな。
F問題は、直感的に「釘と直線をグラフの頂点として、ユークリッド距離をコストにして辺を貼り、パスのコストを「通る辺のコストの最大値」としたときに直線から直線への最短距離÷2」が答えだと感じたので、それをダイクストラで実装したら通った。
ええっとですね、まずそれが直感的にわからないし、そのわかったことを読ませてもらってもそれがどういうことなのかわからないのですね。(そもそもユークリッド距離の概念が曖昧。名前だけ知ってる編集距離なんかと比べて一番普通の距離だと思うけど、そう思うだけ)。
前半はまあまあ想像できる。全頂点を一筆書きして通路を左右に分ける線を引いたとき、最も広い点と点のあいだに円を通すということだろう。だけど第３の点が邪魔をして最も広い点間を通れないことがあると思う。そこから後半の「最短距離÷2が答え
」につなげられない。
邪魔をしている第３の点が最も広い点間を挟むどちらかの点と直接繋がる経路というのが、より小さいコストを持つ経路なのであり、(でないと邪魔できない)、最短経路というのはそういう邪魔が入らない経路のことなのだろう。たぶんね。
答えが示されているからこそ、こうしてこじつけ気味にでも納得のいく解釈がひねり出せたけど、これが「直感的に
」ねえ……(遠い目)。
@kyopro_friends「アライグマ「F問題は……「半径rの円が通れる」っていうのは、「円の中心が障害物からr以内にならない」ってことだから、逆に障害物の方を半径rの円にしちゃえばいいのだ！」
@kyopro_friends「アライグマ「道がふさがったらダメだから、障害物同士の距離を全部計算しておいて、距離が短いところから順にくっつけていって、上の壁と下の壁がくっつくときが答えなのだ！」
これはわかる気がする(図もあるし)。でも逆にこのツイートを読んでもダイクストラ法で実装することがわからないね。
上のツイートとは関係なくさっきの TLE 提出を微修正したら AC になった。事前に XY 配列をソートするだけ。二択による手戻りを最小限にするために、選択肢の優劣が明らかで覆りにくいものを最初に選ぶようにした。
いつの間にか Ruby でも AC をとっている人がいて、しかも実行時間が２桁 ms なんだけど、UnionFind を使っているみたいだった。どういうこと？
あ、連結成分の管理か。コストの低い辺からつないで最小全域木ができあがったときに最後につないだ辺のコストがそのまま答えになる。へー、クラスカル法と UnionFind が今初めてつながった。UnionFind とグラフに関連があるらしいのを今まで見て見ぬふりをして考えてこなかったツケであるな。こういう問題(「Reachable Towns」「Line++」)が全然グラフの問題に見えないんだよなあ。
そうしてみると問題文中で(N 本の)釘とされているものを Silver Woods と表現した問題名は、「木だよ、森だよ、グラフだよ」というヒントだったのだな。おしゃれ。
ところで、自分の提出も２つのケースが 819 ms と 170 ms なのを除けば２桁 ms で済んでいる。オーダーが劣ってもだいたい良好ってことでどうですか？
ソート方法でガチャを引いたら２桁 ms になった。オーダーは変わっていないので入力の引きとソート方法の組み合わせが悪いとやっぱり遅くなるはず。ランダム入力を使って実行時間を体感でテストしてるんだけど、逆順にするだけで十数秒が一瞬になったりする。
メインの処理で if-else-end を省いて２＋２行だったものを３行にまとめたけど、実は再帰呼び出しの回数が多少増える無駄がある。だけど事前のソートで無駄が生じにくいお膳立てはしてあるつもりだし、ストレートで整然とした文字の並びが他には代え難い。
メインの処理２行目の d2 変数への代入だって変数の使い回しで省略できるし*、３行目で再代入している d1 変数はそれから使っていない。しかしストレートで整然とした文字の並びが……。
たぶん通ると思う。265 バイト。$$ が 200 以上だったらいいなという運任せ(※多少小さくても入力次第で問題なし)。単に minify しただけで見るべきところがない。リテラルとか長いメソッド名とか多くの変数とか似たような型の処理とか、１個あればたくさんなものが多すぎるよね。
_,*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
よく考えたら AC 提出とランダム入力で答え合わせができるのだった。
$$ はダメだったので(#17866997)、１バイト増えて 220 バイト。Windows ではプロセス ID は４桁だったんだけど。
まあしかし、これだけ長いとこのスクリプトひとつとっても、いくらでも縮めどころが見つかりそうではある。
３文字減。ちなみに、変更に伴って入れ替わった２数を、どっちでもいいだろうとそのままにした結果は TLE だった>#17868682。「実は再帰呼び出しの回数が多少増える無駄がある。だけど事前のソートで無駄が生じにくいお膳立てはしてあるつもり」が裏目に出た当然の結果なんだけど、わからんもんかなあ。
３文字減った理由がなかなか味わい深い(と思う)。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
メインの処理が３行から２行へと、ゴルフをする過程で気がついた無駄が省いてあるのと、ゴルフをしていると省略せざるを得ない d1,a1 と d2,a2 のスワップが再帰呼び出しを多少減らす見込み。ゴルフをしているとまとめざるを得ない２つの似た処理は、並べた方が速い。しかし誤差程度にしか違わない。むしろ入力次第でひどく悪くなるのがクラスカル法とは違うところであり、覆せないオーダーの差。
深さ優先探索はひとつの経路に縛られるし、幅優先探索はひとつの深さに縛られる。辺に優劣がないならそういうひとつの決まりに従って網羅的に探索して咎められないとしても、そうでない場合は、もっと一般的なグラフアルゴリズムを使うのが効果的だということなんでしょう。さっきは UnionFind についてだけ触れたけど(「UnionFind とグラフに関連があるらしいのを今まで見て見ぬふりをして考えてこなかったツケであるな」)、DFS と BFS がグラフアルゴリズムだっていう認識も実は全然持っていない。見えないんだよなあ。
* while/until などの条件節で初登場する変数が、なぜか後置修飾される本体処理で利用できないのが不思議で不満。条件式はループに先立って必ず評価されているはずなのに。begin ～ end while ～; とは違うのに。