git checkout -b myBranch 本家/master、git push -u myGitHubRepo myBranch、git rebase 本家/master [myBranch] というフローで作業をするために、「自分のではないリモートリポジトリへのプッシュをできなくする」「
新しく作成したブランチが自動的に設定する、分岐元との繋がりを断つ(--no-track を既定値にする)」という下準備をローカルリポジトリで行っていた。そもそも「
(クローンしたなら)リモート名 origin を削除する。余計な自動化も自分が管理しない名前もない方がまし」という考えによってリモート名 origin が存在しなかった。■だって origin ってリポジトリ名なの？ ブランチ名なの？ 本家なの？ フォークなの？ そういう曖昧なものの上で作業をしたくない。ましてそれ(origin)が他人(git)のお膳立てなら、助けではなく余分な複雑さを持ち込むようにしか思えない。定型のタイプの繰り返しに倦んできた頃に提案してくれたなら考えないこともない……かな？ それでもやっぱり自分は pull は使わないので(許容できるのは checkout や add までであって、自動で merge/rebase は乱暴だ)、origin もいらないんだよな(本家リポジトリにはその代わりにわかりやすい名前を付けます。「
ブランチ名とひと目で区別できるように、リモート名は @ を付けたり大文字にしたりしようかな」)。■自分にとって３つのリポジトリの関係は「本家―ローカル―フォーク」として捉えられている。でもひょっとしたら「本家―フォーク―ローカル」の想定もあるのかもな、と考えてみた次第。でも自分で GitHub にフォークリポジトリを持たなくても「本家―ローカル(フォーク)」の２者間でもフォークは成り立つので、中心に GitHub 上のフォークリポジトリを置くのは、GitHub の中の人の立場としてならともかく、個人としては順序が違うと思う。メンタルモデルはひとつで十分だ。そのとき GitHub 上のフォークリポジトリは３番目に位置するオプショナルな存在となる(だから意識しなければこれを忘れる>「
フォークする。プルリクエストを出すためには GitHub 上でフォークしたという事実が大事」 新規作成した空のリポジトリにプッシュしても PR は出せないのである)。■しかし GitHub のアップデートによって今後は、GitHub と origin を必須の前提として作業フローからリモートの区別・存在感を消すのがある種最適な選択になるのかもね。本家とフォークの２つのリモート名を使い分ける必要がなくなるのなら、単純化がなされるのなら、割り切りによる制約がむしろメリットと感じられる人もいるだろう。さもなければ無駄に複雑化して面倒なことをしているなと自分は思います。
最終更新: 2021-04-30T21:11+0900
「10分間３問早解き」回だったわけなので４問目(D 問題)は時間中に解けなかった。90 分使っても解けなかった。辺がないケースで TLE が避けられなかった。
AC のきっかけはこのツイート。
chokudai(高橋 直大)ナス@chokudai
D問題、非連結ですって言うだけでDiff400くらい落ちそう
chokudai(高橋 直大)ナス@chokudai
非連結ですって言っても落ちないわ（サンプルにあるし）
連結で出題しないと400落ちなさそう。
「連結で出題しないと落ちない
」がよくわからないけど、ともかく、非連結なら問題を分割できるじゃん、と気がつきました。ツイートを読んで初めて気がつきました。
サンプル４つのうち２つが辺がゼロのケースだったんだけど、極端すぎてそれが全体としては非連結なグラフであること、個々の頂点としては最も簡単な連結成分を構成している、ということがわかりませんでした。そんなことってある？
テストケースが公開されていないので、提出前のテストには一直線の木を使っていた。連結成分の数を増やしても、辺の数を増やしても、探索を助ける制約が増えるだけだと思ったので。
しかしまだ TLE。どういう木が嫌か考えると、この提出は次のような入力に弱い。
だけど次のように番号の付け方を変えただけで問題が問題でなくなる。
たぶん頂点を次数でソートしてから DFS をすれば緩和されたと思う(が、AC 提出では違う方法(先読み)をとった)。
ソートするにせよ先読みするにせよ、２番目の問題に対処するには非連結なグラフを連結成分に分割する必要があったが、それをしないまま DFS の処理量を削減する方法を考えていた、というのが失敗に終わったコンテスト中の時間の使い方だった。
DFS の処理順を次数の降順にしたら悪くなりにくいのか、343 ms からタイムが大いに改善した。このムラが DFS の沼であり抜け出せない楽しみなんだよなあ>20201101p02、20201107p01.05。
最終更新: 2021-06-11T11:27+0900
以前書いた。「最初に右辺を評価して、それから左辺の評価と代入を左から順番に実行していく感じかな？ 右辺の一時記憶が必要？ 多重代入は遅くて時々評価順が難しい、というのが現在の評価。」「クイズです。a の結果を確認してから予想してカンマを付けたら予想通りの結果になったので驚きはないけど、やっぱり普通の代入とは違うんだなあ」
そしてこの PR が多重代入について>Evaluate multiple assignment left hand side before right hand side by jeremyevans · Pull Request #4390 · ruby/ruby マージされている。
3.1.0 から変わりそう？ 評価順が変わってパフォーマンスがさらにちょっと遅くなる？ 新しい評価順っていうのが、
従来は２が最初にあって、１と３がインターリーブされていた。……ということが PR の概要欄と NEWS の修正に書いてある。
パフォーマンス劣化の理由は左辺の評価結果を一時的に蓄える必要があるからか？
いやあ、あっさり変えるし変えられるもんなんだなあ。まあたぶん、Ruby ユーザーの 1 % も変化に気がつかないだろうとは思う。
非効率だしバグらせやすいし、作り込む価値がないと言っている？
自分はもうこの仕様について(穴にはまった実体験から)知っているので、常に穴を意識して書くし、逆に評価順を利用することもあるけど、これまで幸運にも意識せずに来られた大多数のユーザーが、将来的潜在的には驚きとともに多重代入の評価順の詳細を理解させられるんだろうな、ということを考えると、「作り込む価値はある。ただしうまく実装できる限りにおいては」という評価が妥当かなと思う。
最終更新: 2021-06-08T15:01+0900
昨日あった ABC。D 問題は覆面算。たまたま何か月か前に「FDCAJH × IBCFEH = FBAECIIJEGIH」というのを解く機会があったのだけど、時間制限がないせいで雑に総当たりをして済ませてしまっていた。
本番中は TLE で終わってしまった。E 問題を 15 分で片付けて戻ってきたけど、ついに通せなかった。
制限時間が大盤振る舞いの５秒なんだよね。
桁を１つ２つ減らすだけで時間がだいぶ違うだろうという予測はできたけど、減らし方がわからなかった。なんといっても目の前に文字で書かれた式があるわけではなく、色々なケースが入力されるわけなので。
TODO: Array#all? の中のテストは l<=r より l==r||l+1==r の方が厳しくて良い。
TODO: 和の先頭の桁が１だとすぐにわかる場合がある。
TODO: 列挙してから弾くより列挙しない方がいい。(確定桁が１つあったとして、未確定桁(=文字種-1)の順列の数だけ弾くのは手間だから)
TODO: ループの中の処理がシンプルになるように入念に事前準備をした方がいい。
現在 Ruby での AC 提出は 20。実行時間が 109 ms から 4845 ms までと幅広い。中央値は３秒台です。
たとえば(４桁 ms では最も速い)約 1.6 秒のこの提出>#21688714
先頭桁が０のケースを弾くと同時に、末尾の桁が一致するかどうかだけ特別にチェックしている。一致しないケースでは文字式の全体を数値化する無駄がスキップできる。このひと手間が効果的なのだと思う。
それと、全くの想定外だったのだけど、文字が 11 種類以上使われている式が入力されるケースがあったのだろうか(上の 1.6 秒の提出がチェックして UNSOLVABLE を出力している)。AtCoder の問題は入力や条件がきれいに整理されていて枝葉の手間が省けるように作られているだろう、という甘えがあるのは否めない。
３つある３桁 ms の提出が何をやっているのかは、さっぱりわかりません。
４つの TODO を意識して書いたけど、妥協した部分もある。
とはいえ、これを深さ優先探索で妥協なく書き換えただけで２桁 ms になる？ そう、Ruby で現在最速の提出は 71 ms になっている。
根本的なところで、列挙してから弾くか、可能性のある組み合わせだけを列挙するかという違いがあるのかな。そっち方面で書こうとしたときは、ある桁を見たときに未確定文字が０なのか、１個あるのか２個か３個か、未確定文字があるのはどの項か、繰り上がりはあるのか、ということを考えるのが面倒くさくなって(=脳のキャパシティをオーバーして)、書けなかったんだよね。
書けなかったのをがんばって書いた。時間は申し分ないけども１つの WA。たぶん答えがないケースだと思うんだけど……。
WA の原因は非ゼロチェックが１つ抜けていたこと。それと、想定外だと書いた「文字が 11 種類以上使われているケース」はサンプル４がそうだった。コピペするだけで全然読んでいない。
雑に総当たりしていたのを反省して(TLE は嫌だ！)、数か月ぶりに書き直した。提出 #21743445 をベースにして、掛け算に対応させた。prd の計算が難しかったのですよ。ありえたかもしれないもうひとつの筆算のかたち。すっごく縦長になるけども。
A = 'FDCAJH'.bytes.to_a # to_a is for Ruby 1.8/1.9
B = 'IBCFEH'.bytes.to_a
P = 'FBAECIIJEGIH'.bytes.to_a
C2D = [nil]*91
D2C = [nil]*10
NZ = [-1]*91; NZ[A[0]] = NZ[B[0]] = NZ[P[0]] = 0
F = lambda{|i,carry,aa,bb,zz|
next carry<1 if i<-P.size
a = (c = A[i]) ? C2D[c] : 0
b = (c = B[i]) ? C2D[c] : 0 if a
next D2C.each_with_index.any?{|e,d|
next if e || d==NZ[c]
C2D[c],D2C[d] = d,c
next F[i,carry,aa,bb,zz] || C2D[c] = D2C[d] = nil
} unless b
prd = a*bb+b*aa+a*b*zz+carry
if p = C2D[c=P[i]]
next p==prd%10 && F[i-1,prd/10,a*zz+aa,b*zz+bb,zz*10]
else
p = prd%10
next if D2C[p] || p==NZ[c]
C2D[c],D2C[p] = p,c
next F[i-1,prd/10,a*zz+aa,b*zz+bb,zz*10] || C2D[c] = D2C[p] = nil
end
}
raise unless F[-1,0,0,0,1]
puts [A,B,P].map{|a|'%*d'%[P.size,a.inject(0){|b,c| b*10+C2D[c] }]}
最終更新: 2021-06-02T21:11+0900
緑がほぼ埋まってきて残っているのは解けなかった問題ばかり。そこで水色下位に手を出すも下位とはいえ水色はぱっぱっと解ける雰囲気ではない。あれもこれも行列の問題で、問題のその操作で何ができるのかさっぱりわからない。
だから青色。難しかったん。１年くらい前に ABC004 を埋めようとしたときは力が及ばず C 問題までしか提出に至っていなかった。
今回も一発 AC とはいかなかった。原因はすぐに推測できて、緑色が原点から離れない想定が誤っていたのだと思った。
たとえば赤か青の片方が極端に多いとき、外側に広がっていくよりも中心にある緑色の全体を移動させてでも中心に向けて移動する方が低コストになる分岐点がある。
しかしそれを想定するとコードにするのがさらに難しくなりそうで困った。
ちなみにこの提出の方針は……。赤と青をそれぞれ -100 と 100 を中心にして原点の左右で平らに並べる。原点は超えない。数が多ければ外側により大きく広がる。そのあとで緑色を原点を中心として配置していく。左右のコストを比較して赤と青を押しのけながら。
提出に至らなかった１年前の方針は、RGB の数から重心を求めて云々という感じ。ひょっとすると緑の配置拠点を原点に限らず適切に移動することで、WA だった方針のまま AC に持って行けた可能性が？
「J - 長い長い文字列」(提出 #19035422) とか、「K - 転倒数」(提出 #18029328)とか、脳みそに余裕がなくなるとクラスや日本語変数がソースに現れる傾向があるみたい。今回は両方出てきた。(クラスのメソッドの並びが不揃いなのが気になる。左を先に書くで統一しておきたかった)
イメージとしてはビー玉をざらざらと流し込んでから、抵抗の強弱を感じ取りつつ右に左に均す感じ。最大で900個程度の広がりしか考えなくていいからなんとかなっている。
Ruby の他の提出を見るとゴルフをしていなくても 300 バイト台の短い提出がいくつもあるし、内容も、候補を並べて最小値を選ぶ、二分探索で解(極小値)を探すなど、特に大層な道具は必要としていない。それは、頭の中で十分に理解して整理できているから書けるんだよなあ。
できないからソースコード上でメソッドと複数のインスタンスに分割して整理しています。結果としてひと味違った解法になったと思う。
たぶん抗力の計算が間違ってるんだよね。
押した力を上限として０以上それ以下の力しか発生しないはずだけど、なんだか負の抗力によって隣の障害物に引っぱられていきそうになってる。それだと引っぱってる方はともかく引っぱられる方は、必ずしも安定した、低いエネルギー状態にあるとはいえなくなる。
これが問題にならない理由もわかるけど、それはクラスの外部、インスタンスの利用方法にあるのであって、クラスの、メソッドの定義としては間違っている。