/ 最近 .rdf 追記 設定 本棚

脳log[2021-04-27~]



2021年04月27日 (火)

最終更新: 2021-04-30T21:11+0900

[AtCoder] AtCoder Beginner Contest 199(Sponsored by Panasonic)D 問題 RGB Coloring 2

10分間3問早解き」回だったわけなので4問目(D 問題)は時間中に解けなかった。90 分使っても解けなかった。辺がないケースで TLE が避けられなかった。

 提出 #22101036 (AC / 343 ms)

AC のきっかけはこのツイート。

chokudai(高橋 直大)ナス@chokudai

D問題、非連結ですって言うだけでDiff400くらい落ちそう

chokudai(高橋 直大)ナス@chokudai

非連結ですって言っても落ちないわ(サンプルにあるし)

連結で出題しないと400落ちなさそう。

連結で出題しないと落ちない」がよくわからないけど、ともかく、非連結なら問題を分割できるじゃん、と気がつきました。ツイートを読んで初めて気がつきました。

サンプル4つのうち2つが辺がゼロのケースだったんだけど、極端すぎてそれが全体としては非連結なグラフであること、個々の頂点としては最も簡単な連結成分を構成している、ということがわかりませんでした。そんなことってある?

 AC 前の提出 #22100473 (TLE×2 / 1つは after_contest)

テストケースが公開されていないので、提出前のテストには一直線の木を使っていた。連結成分の数を増やしても、辺の数を増やしても、探索を助ける制約が増えるだけだと思ったので。

しかしまだ TLE。どういう木が嫌か考えると、この提出は次のような入力に弱い。

だけど次のように番号の付け方を変えただけで問題が問題でなくなる。

たぶん頂点を次数でソートしてから DFS をすれば緩和されたと思う(が、AC 提出では違う方法(先読み)をとった)。

ソートするにせよ先読みするにせよ、2番目の問題に対処するには非連結なグラフを連結成分に分割する必要があったが、それをしないまま DFS の処理量を削減する方法を考えていた、というのが失敗に終わったコンテスト中の時間の使い方だった。

 提出 #22109995 (AC / 238 ms)

DFS の処理順を次数の降順にしたら悪くなりにくいのか、343 ms からタイムが大いに改善した。このムラが DFS の沼であり抜け出せない楽しみなんだよなあ>20201101p0220201107p01.05


2021年04月25日 (日) [AtCoder] 昨日の ABC199 で10分間3問早解きの結果、吹けば飛ぶようなょゎょゎ水色になっていた。次はないな。■「「#ボケちゃいMAX https://t.co/DpY5sB73Os」 / Twitter」 ちなみに座れるような椅子はない。キーボードは布団の上である。「PC 前でスタンバイ」とはそういう体勢である。■■■ついに後編。「アルゴリズム・AtCoder のための数学【後編:数学的考察編】 - Qiita」 対象読者だと思いたいが、次の一文に海より深い断絶を感じる>「この問題も規則性を使うことができます。実際、A301=1,A302=1A301=1,A302=1 であるため、」 待って待って、説明がすっぽり抜けてるよ! A301=1,A302=1 なんてどこにも書いてないよ! それを導くところがこの問題の難しさだと思うよ! 「数列の任意の項が直前の 2 項によって決まっているので、連続する 2 項が既出の値をとるとき(たとえば初項である 1 と 1)、数列は循環している」「ある項の取り得る値が 100 種類に限定されているので、連続する2項が取り得る値も 100^2 通りに制限され、数列は必ず循環する」とはっきり宣言してもらってはじめてこちらは「へー、そうなんかー。そんなん考えたこともなかったなー。漸化式で定義された数列が循環するってそういうことかー」と反応できるんですよ。実際今初めて考えたからね。■同じようなことが以前にも>「『kを使った場合のコストは、k-1以下のすべてを使ったコストより高い』 これって要は 100000 > 11111 (2進数) と同じことなんだけど、自分のような人間は「この一連の操作のコストは(書き換えた要素の数によらず)2^k である」という問題文を読んだだけではたどり着けなくて、上のように事実として示されて2進数で考えてみて初めて了解できることだったりする。」■べつに噛んで含めるような解説が読みたいというわけでもない。ABC の一文解説とか好きなんである>20210224p0120200520p0120200428p01。これだけ書いてあれば十分でしょ、もう他に書くことないよ、と突き放される感じ。実際それで通じる人には通じるだろうし、ならばこちらもそれが理解できる人間でありたいと意地になるよね。程度を低く見積もってもらっては自尊心が傷つくのです。一寸の虫でもお馬鹿ちゃんでも。


2021年04月24日 (土) 「『あなたの iPhone はハッキングされました』みたいなメッセージが表示されたー。このアプリをインストールしたらいいの? 診断っていうボタン押したらいいの?」とか言って明け方に起こされた。突っ込みどころだらけで取り合うのもあほらしい手口ではないか。■そのメッセージは“何が”表示している? インターネットを閲覧していて表示されたものでしょう? そのメッセージが「お前はもう死んでいる」だったらどう? わーたいへんだー死んでしまったー。■OS が表示してるメッセージなら話がちょっと違うけど、「ハッキング」なんてチャラい用語をユーザーに提示する OS なら即座に今後の使用を考え直すレベルなのでそれは考えない。■英語ばっかりで説明されているそのアプリの画面で唯一の日本語であるレビューを読んでみ? 明らかに日本人が書いたものでないカタコトのサクラ。本気でだますつもりなら日本語を勉強してからおととい出直して来やがれ、って言うべき場面なんだよ。なんでおろおろしてんの?■もうすこし頭を使う奴ならメッセージに信憑性を持たせるために「あなたの iPhone をハッキングしました。その証拠に私はあなたのメールアドレスを知っています。それは○○ですね!!!」くらいのメッセージを出すんだよ。もちろんそれは User-Agent による自動補完なんだけど。■俺以外の現代人は「広告をスキップ」とか「広告を閉じる」といった操作に慣らされすぎていてマヒしてるかもしれんけど、こういうアホなメッセージを無視するためにメッセージとともに表示されている「閉じる」ボタンをクリックしてはいけないのだよ。iPhone だったら Safari か? ブラウザを操作して消すべきだ。広告が釣りに引っかかるユーザーを誘導している。フィッシングサイト同様に汚らわしい広告にも普段から一切触れないのがいいと俺は思う>20170403。■眠い。


2021年04月22日 (木)

最終更新: 2021-06-11T11:27+0900

[Ruby] 多重代入の評価順

以前書いた。「最初に右辺を評価して、それから左辺の評価と代入を左から順番に実行していく感じかな? 右辺の一時記憶が必要? 多重代入は遅くて時々評価順が難しい、というのが現在の評価。」「クイズです。a の結果を確認してから予想してカンマを付けたら予想通りの結果になったので驚きはないけど、やっぱり普通の代入とは違うんだなあ

そしてこの PR が多重代入について>Evaluate multiple assignment left hand side before right hand side by jeremyevans · Pull Request #4390 · ruby/ruby マージされている。

3.1.0 から変わりそう? 評価順が変わってパフォーマンスがさらにちょっと遅くなる? 新しい評価順っていうのが、

  1. 左辺の変数、レシーバ(メソッド引数も?)を左から
  2. 右辺の値を左から
  3. 左辺の変数代入、代入メソッドを左から

従来は2が最初にあって、1と3がインターリーブされていた。……ということが PR の概要欄と NEWS の修正に書いてある。

パフォーマンス劣化の理由は左辺の評価結果を一時的に蓄える必要があるからか?

いやあ、あっさり変えるし変えられるもんなんだなあ。まあたぶん、Ruby ユーザーの 1 % も変化に気がつかないだろうとは思う。

 新展開@2021-05-06

  1. https://bugs.ruby-lang.org/issues/4443#change-91847
  2. https://bugs.ruby-lang.org/issues/15928#note-10

非効率だしバグらせやすいし、作り込む価値がないと言っている?

自分はもうこの仕様について(穴にはまった実体験から)知っているので、常に穴を意識して書くし、逆に評価順を利用することもあるけど、これまで幸運にも意識せずに来られた大多数のユーザーが、将来的潜在的には驚きとともに多重代入の評価順の詳細を理解させられるんだろうな、ということを考えると、「作り込む価値はある。ただしうまく実装できる限りにおいては」という評価が妥当かなと思う。


2021年04月12日 (月)

最終更新: 2021-06-08T15:01+0900

[AtCoder] AtCoder Beginner Contest 198D 問題 Send More Money

昨日あった ABC。D 問題は覆面算。たまたま何か月か前に「FDCAJH × IBCFEH = FBAECIIJEGIH」というのを解く機会があったのだけど、時間制限がないせいで雑に総当たりをして済ませてしまっていた。

 提出 #21665467 (TLE×6 / AC×34)

本番中は TLE で終わってしまった。E 問題を 15 分で片付けて戻ってきたけど、ついに通せなかった。

 提出 #21721083 (AC / 3703 ms)

制限時間が大盤振る舞いの5秒なんだよね。

桁を1つ2つ減らすだけで時間がだいぶ違うだろうという予測はできたけど、減らし方がわからなかった。なんといっても目の前に文字で書かれた式があるわけではなく、色々なケースが入力されるわけなので。

TODO: Array#all? の中のテストは l<=r より l==r||l+1==r の方が厳しくて良い。

TODO: 和の先頭の桁が1だとすぐにわかる場合がある。

TODO: 列挙してから弾くより列挙しない方がいい。(確定桁が1つあったとして、未確定桁(=文字種-1)の順列の数だけ弾くのは手間だから)

TODO: ループの中の処理がシンプルになるように入念に事前準備をした方がいい。

 Ruby によるすべての提出

現在 Ruby での AC 提出は 20。実行時間が 109 ms から 4845 ms までと幅広い。中央値は3秒台です。

たとえば(4桁 ms では最も速い)約 1.6 秒のこの提出>#21688714

先頭桁が0のケースを弾くと同時に、末尾の桁が一致するかどうかだけ特別にチェックしている。一致しないケースでは文字式の全体を数値化する無駄がスキップできる。このひと手間が効果的なのだと思う。

それと、全くの想定外だったのだけど、文字が 11 種類以上使われている式が入力されるケースがあったのだろうか(上の 1.6 秒の提出がチェックして UNSOLVABLE を出力している)。AtCoder の問題は入力や条件がきれいに整理されていて枝葉の手間が省けるように作られているだろう、という甘えがあるのは否めない。

3つある3桁 ms の提出が何をやっているのかは、さっぱりわかりません。

 提出 #21741214 (AC / 921 ms)

4つの TODO を意識して書いたけど、妥協した部分もある。

  • 妥協1:確定した1を他の非ゼロと混ぜて列挙した。
  • 妥協2:列挙を正と非負の2つに分けたがどちらにも permutation メソッドを使いたかったがために、配列の引き算やら配列の2段参照がループの中にある。

とはいえ、これを深さ優先探索で妥協なく書き換えただけで2桁 ms になる? そう、Ruby で現在最速の提出は 71 ms になっている。

根本的なところで、列挙してから弾くか、可能性のある組み合わせだけを列挙するかという違いがあるのかな。そっち方面で書こうとしたときは、ある桁を見たときに未確定文字が0なのか、1個あるのか2個か3個か、未確定文字があるのはどの項か、繰り上がりはあるのか、ということを考えるのが面倒くさくなって(=脳のキャパシティをオーバーして)、書けなかったんだよね。

 提出 #21743144 (WA×1 / 90 ms)

書けなかったのをがんばって書いた。時間は申し分ないけども1つの WA。たぶん答えがないケースだと思うんだけど……。

 提出 #21743445 (AC / 66 ms)

WA の原因は非ゼロチェックが1つ抜けていたこと。それと、想定外だと書いた「文字が 11 種類以上使われているケース」はサンプル4がそうだった。コピペするだけで全然読んでいない。

 「FDCAJH × IBCFEH = FBAECIIJEGIH」

雑に総当たりしていたのを反省して(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年04月06日 (火)

最終更新: 2021-06-02T21:11+0900

[AtCoder] AtCoder Beginner Contest 004D 問題 マーブル

緑がほぼ埋まってきて残っているのは解けなかった問題ばかり。そこで水色下位に手を出すも下位とはいえ水色はぱっぱっと解ける雰囲気ではない。あれもこれも行列の問題で、問題のその操作で何ができるのかさっぱりわからない。

だから青色。難しかったん。1年くらい前に ABC004 を埋めようとしたときは力が及ばず C 問題までしか提出に至っていなかった。

 提出 #21534453 (WA×2 / AC×83)

今回も一発 AC とはいかなかった。原因はすぐに推測できて、緑色が原点から離れない想定が誤っていたのだと思った。

たとえば赤か青の片方が極端に多いとき、外側に広がっていくよりも中心にある緑色の全体を移動させてでも中心に向けて移動する方が低コストになる分岐点がある。

しかしそれを想定するとコードにするのがさらに難しくなりそうで困った。

ちなみにこの提出の方針は……。赤と青をそれぞれ -100 と 100 を中心にして原点の左右で平らに並べる。原点は超えない。数が多ければ外側により大きく広がる。そのあとで緑色を原点を中心として配置していく。左右のコストを比較して赤と青を押しのけながら。

提出に至らなかった1年前の方針は、RGB の数から重心を求めて云々という感じ。ひょっとすると緑の配置拠点を原点に限らず適切に移動することで、WA だった方針のまま AC に持って行けた可能性が?

 提出 #21541500 (AC / 1246 Byte / 65 ms)

J - 長い長い文字列」(提出 #19035422) とか、「K - 転倒数」(提出 #18029328)とか、脳みそに余裕がなくなるとクラスや日本語変数がソースに現れる傾向があるみたい。今回は両方出てきた。(クラスのメソッドの並びが不揃いなのが気になる。左を先に書くで統一しておきたかった)

イメージとしてはビー玉をざらざらと流し込んでから、抵抗の強弱を感じ取りつつ右に左に均す感じ。最大で900個程度の広がりしか考えなくていいからなんとかなっている。

Ruby の他の提出を見るとゴルフをしていなくても 300 バイト台の短い提出がいくつもあるし、内容も、候補を並べて最小値を選ぶ、二分探索で解(極小値)を探すなど、特に大層な道具は必要としていない。それは、頭の中で十分に理解して整理できているから書けるんだよなあ。

できないからソースコード上でメソッドと複数のインスタンスに分割して整理しています。結果としてひと味違った解法になったと思う。

 @2021-04-07

たぶん抗力の計算が間違ってるんだよね。

押した力を上限として0以上それ以下の力しか発生しないはずだけど、なんだか負の抗力によって隣の障害物に引っぱられていきそうになってる。それだと引っぱってる方はともかく引っぱられる方は、必ずしも安定した、低いエネルギー状態にあるとはいえなくなる。

これが問題にならない理由もわかるけど、それはクラスの外部、インスタンスの利用方法にあるのであって、クラスの、メソッドの定義としては間違っている。


2021年04月01日 (木)

最終更新: 2021-06-08T15:27+0900

[AtCoder] AtCoder Beginner Contest 155D 問題 Pairs

ABC の4問目で 400 点問題。しかし青diffではある。

 未提出 ABC155_d.rb27 (TLE必至)

時間制限を 10 秒にしてくれたらたぶん通る。しかし実際の制限は2秒であり、3秒ですらない。慈悲はないのか。

Ruby の提出一覧を見ると AC していても軒並み1秒越えであり、処理量がしんどい問題なのは間違いないのだけど、その中にあって1秒を切っている提出もある。ということは、己の考えが足りないのである。ぐぬぬ。

 方針

入力を正負ゼロに分けて、正負ゼロの積がそれぞれいくつ作られるかをまず求めた。

負の積が K 個かそれより多いならば、正の数と負の数のペアを考える。ゼロは特に考えることがない。K 番目が正の積の中に含まれているなら、負の数同士のペアと正の数同士のペアを考える。

これで考えるべき組み合わせが多少は減ったつもりになるが、入力次第では何の足しにもならない。本質的に計算量を削減する方法がわからなかった。

それでどうしているか。

K 番目の数を -10^{18} から 10^{18} の範囲で二分探索している。

ペアを、ある数とそれに掛け合わせるソート数列として持っている。K 番目の数の候補となる数が与えられたとき、その数以下の積がいくつ作られるかは、これまたソート数列を二分探索することでわかる。

ペアの数が馬鹿にならない。N (≦2×10^5) のオーダーで存在する。だから「ある数」と「ソート数列」に注目して、ペアをソートされた状態で持っている。そうすると K 番目の数の候補となる数が与えられたとき、かすりもしないペアを予め除外して考えることができる。かすらないとは2通りあって、すべての積がある数以下となるか、すべての積がある数より大きくなるか。全か無か。ここで累積和と、三度目になる二分探索を使っている。

とまあ、こんな感じ。(3つだが三重ではない)二重の二分探索のあいだに、範囲を絞っているとはいえちまちまと順番に数え上げる線形時間の処理が挟まっているのがいただけない。一番重たいケースで 10 秒はがんばった方だと思うよ。知的方面でのがんばりではないけども。


ソート列とソート列の組み合わせでペアを作っているのに、そのときに一方のソート列をばらばらにしてしまっているのが悪いのか? (短い方を選んでバラすようにはしている)


 AtCoder Beginner Contest 174E 問題 Logs

この回 は「C 問題が解けなくて大爆死した回の ABC」。その後 C 問題を解いて、F 問題も解いたけど、「F 問題が解けたら D と E も解けたつもりでいいんじゃないかな?」と書いたように、F の後でも D と E が解けていなかった。不思議なもので、D 問題は緑埋めをしていた先月に普通に解いていた(提出 #21267825)。緑がほぼ埋まってきて次なるターゲットは水色下位に移ってきている。E 問題 Logs である。解けない緑より解ける水色なのである。

 提出 #21466620 (AC / 226 Byte / 350 ms)

えー、解けました。解けなかったときは何を考えて行き詰まっていたか。

  1. 最優先で切断する丸太はその時点で最も長い丸太である。
  2. 2等分しますか? 3等分しますか? そもそも等分しますか?
  3. たとえば最終的な解が、2等分した長さより短く3等分したよりも長くなるなら、2等分したあとでその両方をさらにもう1回ずつ、合計で3回分割する手間をかけるのは間違いである。
  4. 解がわかっているなら、最初から2回の手間で3つに分けるのが最適だと判る。
  5. しかし解がわからない。

今日の日記のタイトルは「D 問題 Pairs」です。関連は?

これまで二分探索といえばソート済み配列から特定の閾値をまたぐ値を選び出すのに使用してきたのだけど、実はそれだけではなかった。何もない空中から特定の値(解)を見つけ出すのにも利用できるのだった。順序さえ与えられるなら、解が -10^{18} から 10^{18} の範囲に存在すると判っているなら、たったひとつの意味のある値(解)を二分探索してもいいのである。

という気付きが Pairs を解く過程で(まだ解けてないけど)得られていたので、今度はごく素直に、解を決め打ってから最適な切断をすると切断回数の合計が何回になるかという逆算的な解法を発想することができた。そういうことができるとわかっていた。

二分探索を使った解法でかつて最も衝撃を受けたのは Vacant Seat というインタラクティブ問題に対する提出 #2057817#2064531 だった。bsearch メソッドから呼び出されるブロックの中でクエリを行っている。いやね、自分も提出 #7970588 の中で二分探索を使って答えを出してるんだけど、そのことと、対象となる具体的なソート列がないまま空中で二分探索を行う、順序はクエリで動的に決定するということの間に、どれだけの隔たりがあることか。

脳みそが不自由だと存在しない制約で思考が枷をはめられてしまうのだなあ。最も基本的なツールといえる二分探索も、まだまだ使いこなせていないのだった。


ところで 350 ms は Ruby で2番目に速い提出なのだけど、どんぐりの背比べである2番目とそれ以降から頭ひとつ抜けて速いのがこの 提出 #15632506 (sushibon さん / 219 ms)。二分探索は行っていない(ソートはしている)。

二分探索というのは人間が考えることを放棄して機械に試行錯誤させる解法なのだけど、人間が頭を使えば無駄なく速く答えを求めることができるのですね。まあ、何をどう考えればいいのかわかりませんけども。

 AtCoder Beginner Contest 023D 問題 射撃王

これも空中二分探索。解を決め打ってから考える。もはやおなじみである。

 提出 #21974701 (AC / 245 Byte / 953 ms / 21392 KB)

Ruby では唯一3桁 ms に入った(他は4桁)。log1つ分の差だと思う。Nlog^2 と Nlog。単にソートする方のやり方を思いつかなかっただけなんだけど。

 AtCoder Beginner Contest 149E 問題 Handshake

同じ青diffでもこちらのほうが Pairs よりわずかに難しいことになっている。

 提出 #22314080 (AC / 283 Byte / 1489 ms / 22708 KB)

しかしこれは簡単な Pairs ということでいいんではないか? だって同じように二重の二分探索の真ん中で線形時間の足し合わせを行っていて、TLE にならないんだもん。

 Ruby によるすべての提出 (AC のみ / 実行時間昇順)

概ね 300 ms から 500 ms の間におさまっているから、自分の 1489 ms は最も遅い部類に入る。Pairs を解くヒントが(Pairs の提出一覧はもちろん)ここにもあるのでは?(だったら読むわけにはいかない)

 提出 #22329595 (AC / 422 Byte / 717 ms / 22940 KB)

ループの構成は変わらないまま脳筋的努力を重ねた結果、倍近く速くなった。しかし 300 ms にも 500 ms にも及ばない。やっぱり計算量のオーダーを減らす手がどこかにあるのだろう。それがわかれば Pairs が AC できるぞっ。

 提出 #22754190 (AC / 531 Byte / 246 ms / 24136 KB)

やったど。246 ms は Ruby では僅差で一番速い。

どこでオーダーが改善できるか。解法の根幹をなす大外の二分探索の log は欠かせない。入力をなめる N もなくせない。なら内部の二分探索を削るしかないのはわかってたんだけど、「log を削らなければいけません」「はい、削りました」ができるなら脳みそはいらないわけで……。

ヒントはこの問題の前に解いた射撃王にあった。log ひとつの差ってちょっとした違いなんですよ。ちょっと見る角度を変えるだけ……でなんとかなるなら脳みそは(略)

実際のところ、二分探索の代わりに shift/pop を繰り返すようにしただけ。


261 ms の提出を読んだ。A 数列の値から添字を得る逆引きインデックスを事前に作成するのがキモであるようだった。A の値の範囲は 10000 以下なので、それが配列のサイズとなったところで大した大きさではない。

言われてみれば、そうだね、という感じ(だけど思いつかなかった)。313 ms の提出も 328 ms の提出も 329 ms の提出も、同じ下拵えをしていた。

 提出 #22756111 (AC / 893 Byte / 977 ms / 30968 KB)

やったど! たまたまぶつかった別の問題ばっかり3問片付けてきたけど、とうとう本丸の Pairs をクリアしたぞ! (提出日時を見ればわかるけど、今日は5月の下旬なのだ。日記とは?)

これもやっぱり Handshake と同じように二分探索の代わりに shift/pop を繰り返すようにした。Pairs は Handshake と違って A 数列の値の上限が 10^9 なので、逆引きインデックスを用意しておく方法は使えなかったのではないかと思う。

ところで、ぎりぎり3桁 ms には入ったけど、759 ms には負けました。配列の操作でなく添字の操作をしているところが効いてるのかな?


2021年03月22日 (月) 「進入不可」と「進入禁止」はどちらが強い抑止効果を持つだろうか。人によるだろうか。■進入不可……本当に入れないかどうかは確かめてみなければわからないな!■進入禁止……なんで禁止されてるんだろう。誰が禁止してるんだろう。まあ、入って入れんこともなさそうだし、いっか。■だいたいこんな感じ。ありとあらゆる落とし穴に一度以上はまることを自認している。一度目は(なぜか人が避けて通る)ショートカットの疎通を確かめるために(穴に落ちるまで穴があるかどうかは不確かだ)。二度目以降は迂闊さのために。■再掲「シマノのハブの説明書にクイックリリースのハンドルの向きを規定する記述があって、それに続けて、茂みに突っ込んだりしたときに強制的に開放されないためだとかなんだとか、そうする理由が一緒に書かれていた。とてもとても素晴らしいと思います。納得できる理由がなければ動けない人間なので!」 禁止するにも作法があるのではないか。そこまでする義理はないって? いかにも。しかし実効性を求めるときには考えてもいい。


2021年03月21日 (日) [AtCoder] 今日の ARC115。いつものように 20 時までにお風呂に入って 21 時前にあがって PC 前でスタンバイしていたら、気付いたときにはもう残り時間が半分を切っていた。まあ、そういうこともある。帰宅が19時過ぎなのでもとから20時スタートは厳しい。時間が合わなくて1時間遅れで参加した ABC も過去にはあった>ds14050@ABC156。そのときのパフォはABC3完で177。プラス1時間で D 問題まで解けていたのがくやしいところ。ARC の A 問題1完最遅レベルのパフォは……知りたくない。■今日のパフォーマンスをどのように受け止めるか。ありうる理想世界の自分は ARC の A,B,C 問題くらいは1時間でささっと解けているはずなので、1時間で3問解いたパフォーマンスが2時間で3問解いたかのように評価されるのは不本意であるが、1時間で1問しか解けなかった、途中で0完も覚悟した、低パフォーマンスの第一の原因は自分の残念なおつむにある。残念なことであるなあ。


2021年03月20日 (土) [AtCoder] 今日の ABC196D 問題 Hanjo。Ruby でも(ほぼ)全探索を許してくれる慈悲深い制約に助けられた。終了1分前に ACE 問題 Filters。考え方は合っていたけど詰めが甘かった(RE, WA)。愚直解法とランダム入力で答えを突き合わせてデバッグをした(AC)。コンテスト中にこれをする余裕はない。


2021年03月17日 (水)

最終更新: 2021-03-24T16:47+0900

[AtCoder] AtCoder Beginner Contest 067D 問題 Fennec VS. Snuke

解いたあとで他の人の Ruby での解答を見たらバリエーションがいくつか見られた。

 解法1:キューを2本用意してフェネック、すぬけくん双方のスタート地点から各ノードまでの距離を幅優先探索などで確定し、それからノードの塗り分けをする。

これが一番多かったと思う。公式解説に書かれている通りの手順。

 解法2:1本のキューでフェネック、すぬけくんが交互に陣取りをしていく。

これは Ruby で最速の qib さんの提出 #20369253 (191 ms) の解法。

公式解説にはこう書かれている。

マス i と j の距離を d(i,j) として,マス i の色は d(1,i) ≦ d(N,i) ならば黒,そうでなければ白となる.結論としてマス 1 とマス N の 2 点から幅優先探索や深さ優先探索などを行うことで O(N) でこの問題を解くことが可能である.

解法1はたしかに解説通りの手順ではあるが、解答にあたり具体的な距離まで知りたいわけではなく、距離の大小関係だけ知れれば十分なのだ。

解法2の手順は(スタート地点からの距離を測定する)幅優先探索に則っているのだが、一見すると1手につき1マスしか塗れないゲームのルールに反しているように見えるのが難しい。同じことは解法1にも言えて、「マス i の色は d(1,i) ≦ d(N,i) ならば黒,そうでなければ白となる」が納得できるかどうかに尽きるのだけど、解法2の手順がなまじゲームに似ているせいで考えてしまう。

 解法3:自分の>提出 #20999230 (208 ms) やや遅く、メモリ消費も多い。

フェネックとすぬけくんの行動原理として想定したのは公式解説のものと同じ。見立てだけが異なる。どういう見立てだったか。

フェネック(すぬけくんでもいいが便宜上フェネックを選ぶ)のスタート地点を木の根と定めて、すぬけくんのスタート地点の深さを知る。すぬけくんは移動可能範囲を広げるために根に向かって移動する。フェネックはすぬけくんの移動可能範囲を狭めるためにすぬけくんに向かって移動する。出会うのは中間の深さ。すぬけくんは根に向かって移動できなくなった地点を根としてその子孫ノードだけを塗ることができる(だから一直線に根(フェネックのスタート地点)を目指していた)。

結局のところこの問題は一本の辺を見つけ出す問題だった。頂点集合をフェネック側、すぬけくん側に分ける辺がどれかを見つける問題だった。

その手順として幅優先探索(解法1)とその応用(解法2)と深さ優先探索(解法3)とダイクストラ法(未紹介)と、いろいろな方法があって、実行速度の差があった。同じ線形時間でも1回なめるだけで済ませられるのか、2回か、3回か。

 AtCoder Beginner Contest 148F 問題 Playing Tag on Tree

今日@2021-03-23 たまたま取り組んだこの問題が同じ方針で解けそうだった。

2地点から深さ優先探索で陣取りをしていって、中央付近でにらみ合って、それからどれだけ相手陣へ侵攻(自陣へ後退)できるかを数えれば答えになりそうだった。

 提出 #21207034 (WA×1 after_contest_01)

きっちりと隙を見せない after_contest に撃ち落とされましたとさ。

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

サーバル「ABC148F『Playing tag on tree』にafter_contestを追加したよ! 不等式に等号を入れるか入れないかを間違ってるコードが落ちるようになったはずだから確認してみてね」https://t.co/jcHP4lHFhg

 提出 #21208328 (AC)

不等号などなかった。先攻後攻を入れ替えたのと、自陣へ逃げ込もうとしてうっかり中立地帯へ迷い込まないように道を塞いだ。

当初方針のまま after_contest に対応したが、どうにも不自然に頑張ったようなコードになってしまった。この問題に関しては、想定解法通りに2通りの距離表を見比べて答えを選び出すのが良かっただろう。

ところで ABC148 はオンタイムで参加していた。A-D まで灰 diff で、E 問題に至ってもギリギリ緑という低難度回。F 問題でやっと水 diff 中位だったらしい。当時1時間を残していながら解けなかったのがこの F 問題。何を考えて解けなかったか。

木の上で追いかけっこをする2人がすれ違うことができない、ということが認識できていなかった。だから偶奇が適切な部分木を選んで逃げ込むことで追跡が躱せるような気がしていた。それじゃあこの但し書きが嘘になるのにね。「なお、ゲームは必ず終了することが証明できます。」 そんなん考えたら青 diff 上位の「DFS Game」より難しくなるってのにね。


2021年03月16日 (火) [AtCoder] 昨日から AtCoder Problems が真っ白で困っていた。Array.prototype.flatMap を補ってとりあえず大丈夫。どのブラウザも OS を選り好みするせいで代替になり得ない。■なんかそうしたら以前から真っ白だった AtCoder Pie Charts タブまで正常に表示されるようになった。棚ぼた。 ABC や ARC の問題一覧が見られる Table ページで自分の状態(AC/NotAC/NoSub)も見られるようになっている。あれってユーザースクリプトじゃなかったんか……。


2021年03月13日 (土)

最終更新: 2021-03-15T22:56+0900

[AtCoder] パナソニックプログラミングコンテスト(AtCoder Beginner Contest 195)F 問題 Coprime Present

本日の ABC。1時間かけて ABCD の4完で、残り40分考えて E 問題が解けずに終わった。ゲーム問題苦手。勝ち筋とか必勝法とか、さっぱり見えない。「自分はこの、先攻後攻が決まった瞬間に勝ち負けが見えるゲームを、きっと楽しくプレイできるんだろうなあ。

本番中に E 問題が行き詰まっている最中に F 問題をタイトルだけチラ見していた。Coprime の単語が見えた瞬間にあきらめた。別の問題だけど先々月に「Coprime はまた解けなかった。」 完全に苦手意識を持っている。素数とか見たくない。

 提出 #20911347 (TLE×19 / AC ×17)

割と大きめのサンプル3が通ったのでいけると思ったが TLE だった。

考えたことを順番に。

  1. 制約「B−A≤72」があからさまな弱点。
  2. A と B 自体は 10^{18} になりうる大きな数なので、互いに素をどのように確かめるか。
  3. 72 以下の素数で割ってみればいい。
  4. [A,B] の区間から作ってはいけないペアが列挙できたが、これを 2^{B-A+1} 通りの組み合わせからどう除外するか。
  5. (迷走) ペアの左側をマージしたビット列とペアの右側をマージしたビット列を用意して、全 2^{B-A+1} 通りを振り分けよう……実行が終わらない。
  6. (迷走) ペアを併合したグループを使って解けないか……解けない。
  7. 愚直にカードを1枚ずつ引いて、使う場合と使わない場合で深さ優先探索を……これがさっきの TLE 提出。

 提出 #20911691 (AC / 357 Byte / 221 ms / 14628 KB)

このとき(緑diff精進3問)解いた問題の1つが「ABC 115 D - Christmas」なんだけど、素直に問題の通りに書いた最初の版が明らかに TLE を免れなくて、ださいけど if を使って2回の再帰呼び出しを1回に節約するパスを追加することで AC になっていた。

倍倍ゲームになりうる再帰構造には特別な警戒が必要だということと、それが反転したときに改善効果が劇的だということを学んでいた。今回も最後の lambda F に2行追加して AC。

 「(迷走) ペアを併合したグループを使って解けないか……解けない。」

たぶんグループの作り方が間違っていた。二次ペア三次ペアと芋づる式に相互グループを作るのでなく、それぞれの数ごとに一次ペアのグループを作って、そのサイズでクラス分けをすれば、計算で答えが求まったのではないか。計算の材料にする数字が誤っていたから求まらなかったのではないか。いやでもそのクラスには公倍数の情報が抜けてるのか……。

 「72 以下の素数で割ってみればいい。」

組み合わせた結果をフィルタリングするよりも、フィルタリングした結果を組み合わせるべきだったのではないか。SQL がそうでしょう? JOIN する前に WHERE で絞るべきなんだ。WHERE に似ていても HAVING では遅いんだ。

全探索がダメでもある種の探索が許されていたあたり、今日の制約には優しさが感じられるなあ。


これに関連した @kyopro_friends さんのツイートを考えていた。

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

アライグマ「F問題は、COLOCON2018C『すぬけそだて――ごはん――』の難しい版なのだ! gcd(x,y)=gcd(x-y,y)≦|x-y|だから、72以下の素数の倍数が重複しないようにすればよくて、どの素数の倍数をもう使ったかでbitDPすればいいのだ!」

gcd(x,y)=gcd(x-y,y)≦|x-y|」ってつまり……

  • 10000 と 10010 のように近接した2数があるとき、その公約数が 10000 近辺にあることはないのだなあ。
  • 大小2つの数とその差(正の方)という3つの数があるとき、これらは GCD を共有しているのだなあ。
  • x-y を繰り返して行き着く先は x%y だけど、なんだかこれってユークリッドの互除法……

というような発見があった。ものがよく見えていないと「新発見」が多い。ユークリッドの互除法まで見つけてしまった。開拓者か研究者に向いているのではないか。