/ 最近 .rdf 追記 設定 本棚

脳log[AtCoder: 2021-04-12~]



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月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月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 だけど、なんだかこれってユークリッドの互除法……

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


2021年02月24日 (水)

最終更新: 2021-03-23T20:00+0900

[AtCoder] SOMPO HD プログラミングコンテスト2021(AtCoder Beginner Contest 192)F 問題 Potion

解説を読んで ABC をコンプリートしようシリーズの1回目。ABC192 で残っているのは F 問題。いわゆるポーションって portion とはスペルが違ったのね。

2回目があるかはわからない。1回目にして解説を読んでから2日間苦しんだ。DP だったんだけど、人類が扱うには次元が高すぎるのではないかな? 自分には無理。

 提出 #20468517 (AC / 614 Byte / 1451 ms / 18204 KB)

ソースコードの冒頭にも引用したけど、解説の要諦が次の一文。

dp[i][j][k] = i 番目までから j 個選んだときの和であって、mod C で k に等しいようなものの最大値

自分は最初これを次のように解釈した。

dp[i][j][k] = i 番目までから j 個選んだときの和であって、mod j で k に等しいようなものの最大値

微妙な違いがわかりますか? mod C と mod j の違い。うっかりミスではなく、理解できる範疇を超えていたから、これってこういう意味だよね、と一段次元が低い誤った理解しか生まれなかった。

引き回すデータ配列の構成を教えてもらってさえ遷移が書けるまで一日かかったんだけど、いざ完成したらこの微妙な勘違いのせいで時々答えが合わなかった。時々。答え合わせに使ったのは次のナイーブな解答スクリプト。N が 30 を超えると実行時間が現実的でないので生成する入力の N は小さめに。テストケースはまだ利用できない。

N,X,*A = $<.read.split.map(&:to_i)

p (1..N).filter_map{|c|
	k = X%c
	m = A.combination(c).map(&:sum).sort.reverse_each.find{|m| m%c == k }
	(X-m)/c if m
}.min

要するに、これを時間制限に収まるように書き直しましょう、という問題だった。それが難しい。

結局一度完成したと思ったスクリプトを囲うようにもうひとつループを重ねた。法が変わると余りは再利用できない。最初から目的地(C)を定めて j を変化させなければいけない。dp 配列の添字 k の上限は j でなく C である。無理だよ、明日にはもう自分でこの文が理解できないよ。


DP であることでナイーブな解答より有利になる点は次の2つ?

  1. j+1 個の組み合わせを生成するのに j 個の組み合わせ結果が利用できる。

    その際にキーとなるのが添字 i (「i 番目までから j 個選んだときの和であって」)。j 個の組み合わせ結果を i (1~N-j)によって分類しておくことで、j+1 個の組み合わせを作るのに利用できる。

    たぶんこれって DP のひとつの典型なんだと思うけど、配列の型を示されてさえこの種の遷移(何を残して何を再利用するか)を見つけるのに1日かかった。

    見つけた遷移は具体的には、「j を C まで増やしながら、ある j について i 番目の要素(A[i])を i の大きい順に考える。A[i] を採用しないときに dp[j][i] に対応する C 要素の配列は dp[j][i+1] のものと同じ。A[i] を採用するときは dp[j-1][i+1] に記録された C 個の値と組み合わせる」 i と j が解説とは入れ替わってら。

    dp[j][i] の値を作るのに dp[j][i+1] (最内ループの直前の値)と dp[j-1][i+1] (中間ループの直前の値の1要素)を再利用している。

    勘違いして見えていなかったのは、j=C であり j を 1..N の範囲で変化させる過程で各 j(C) に対応した答えが見つかる……のではなく、C=1..N について j を 1..C の範囲で変化させなければいけないということ。

  2. 組み合わせた結果の和を mod C で分類して最大の値だけを採用することで、無駄な組み合わせが省ける。
  3. あとはまあ、組み合わせる数は多い方が初期値の点でも経時増加量の点でも有利なので、ループを降順にして、途中で打ち切り条件を設定したりした。だけど special_xx.txt に類するケースがスペシャルな理由は、こうした打ち切りが無効なところにありそう。

  • 提出 #20486969 (TLE×11)

    主にイテレータを使って書き直したので遅くなるのはわかる。

    Array#min の代わりに Array#[] でダイレクトに最小値を取得するようにしたので、special_xx.txt 以外のケースでは改善している。

  • 提出 #20486969 (TLE×11)

    同じように Array#min を使うのをやめたのと、イテレータを使わず全て while で書いた。special_xx.txt 以外のケースで上よりさらに少し改善しているが、TLE は TLE。

    Ruby って整数演算が足す引く剰余大小比較まで、どれも同じくらい遅い雰囲気。演算コストに差がないなら演算子の数を減らす方がいい?

    でもどこに 800 ms も遅くなる要因があった? もう予測できない。

 提出 #20581154 (AC / 615 Byte / 1437 ms / 15868 KB)

平均すると最初の提出より1割弱タイムが改善しているけど、意味のある差ではない。

ベースはイテレータメインの提出 #20486969 (TLE×11)。

AC と TLE の分かれ目は4重ループの最深部にあった。

  1. 初期値を正の無限大ではなく nil にした。

    正の無限大は正常値として扱えるので記述が統一できるのだけど、むしろ異常値として nil や -1 や無限大を設定・検知して、ループをスキップするのが良かった。

    ところで、想定上限を整数で表現しようとすると 67 か 68 ビットが必要になる気がして採用できなかった。Float::INFINITY と Bignum の、どちらがいいともいえない。打ち切り条件が ×C ではなく ÷C である理由でもある。

  2. 余り(k)の計算は、k = m%ck-=c if c<=k よりも、「実行されないコードが最速」なのだった。負の添字を使った配列参照は組み込まれた機能でありコストは支払い済みなので、使い倒さなければ損になる。

いくつかの C について最小公倍数で余りをとれば、より外側のループで DP 配列が再利用できるのではないか。数列 A の偏りと C の組み合わせを調べれば、k が取り得る値が C 種類より少なくなるのを見抜けるのではないか。結局のところ、TLE の原因はおそらく X%C と A%C(の和) がまったくマッチしないせいで4重ループを最初から最後までフル回転させられるせいだと思うから。

 提出 #20639856 (AC / 870 Byte / 1167 ms / 24016 KB)

「いくつかの C について最小公倍数で余りをとれば、より外側のループで DP 配列が再利用できるのではないか」を実装してみた。話を単純にするために C が偶数の時に j=C/2; i=0 の DP 配列を C=C/2 の DP 配列として再利用した。

たとえば N が上限の 100 のとき、51..100 は普通に DP をする。1..50 は再利用配列を使用して DP をしない。限界は次の2点。

  • C が大きいときの方が DP の処理量が多いので、全長の下半分の節約は、処理時間にすると4分の1以下の短縮効果にしかつながっていない。
  • special_xx.txt 以外のテストケースでは打ち切り条件が有効に働くので、DP の節約効果が日の目を見ないどころかただオーバーヘッドを増やしただけになる。

 @2021-03-05 テストケース

ケースXX (素因数)A に含まれる 9999999 の数答えが見つかる C
special_01.txt52142908377193267103×4703×10764231956301
special_02.txt48620189947792921131×2719×18713×729445312
special_03.txt70227681074731923770227681074731923723
special_04.txt651020109319638361162011×231599×1735054934
special_05.txt61168850281850484182936769××737535968945
special_06.txt857415171960730822×11257×32587×11686759956
special_07.txt794433313787770441101×74910361×10500118167
special_08.txt515779426304609041101×510672699311494178
special_09.txt8962979337589569513×22769×1312161174929389
special_10.txt908429522499966622×24335153×1866496427910

N はすべて 100。数列 A の要素はほとんどが 10000000 で、0から9個が 9999999 という構成。

special_xx.txt が入力する数列 A の中に値の種類は1から2個しかなかった。C 個選んだ和の余りがとる値は、限られた 9999999 がいくつ含まれるかでしか違いが出なかった。つまり1から10種類。それでも C が 1..N の範囲で変化するうちに余りの数字(k)自体は変化していくし、X%C も変化するんだけど、どうやったらぎりぎり最後までマッチングしないような X が選べるんですか?


2021年02月21日 (日) ARC の方。A だけ。B 問題は通せへんとあかんかったな(最終的に WA が2ケース)。C 問題は読んでないよ。なお、AtCoder Problems によると C 問題でもギリギリ緑色という難易度のよう。C 問題までさっくり通せるべきだったね。C完B完。これをコンテスト時間中にだね……。

最終更新: 2021-04-06T17:58+0900

[AtCoder] SOMPO HD プログラミングコンテスト2021(AtCoder Beginner Contest 192)/B,C,D,E

昨日あった ABC。今晩には ARC があるので復習が忙しい。

 B 問題 uNrEaDaBlE sTrInG

正規表現を乱用する問題だと決めつけて考えた。使える限り最善でなくてもかえって難しくなっても正規表現を使う。

 提出 #20290278 (AC / 50 Byte / 62 ms / 14440 KB)

パターンには改良の余地がある。たぶん /^([a-z][A-Z\n])+$/ で良かった。

$ は改行の前でも文字列の末尾でもマッチしたと思ったけど、フラグの影響がどう出るかが不確かだ。そして Ruby のフラグは JavaScript のフラグと比べてあべこべな雰囲気がしてわかりにくい。

入力が英大文字小文字だけだから大小の判別は1ビットを見るだけでいいんだけど、正規表現だから関係ない。

 C 問題 Kaprekar Number

C 問題にしては……と疑いをもったが、テキトーに大きい桁を与えてもいけるみたいだったので問題の通りに関数 f を定義してシミュレーションした。本当はテキトーに大きいだけだとすぐに桁数の少ない値に収束してしまいかねなくて、そうではない嫌らしい値が与えられるかもという疑いがまだあったのだけど、とりあえず投げてみるスタイル。

 提出 #20296774 (AC / 157 Byte / 560 ms / 14324 KB)

最近誰かがツイートで Integer#digits メソッドに言及していたので初めて使ってみた。適所では? そういえば D 問題でも使っていた。適時(タイムリー)だ。

 D 問題 Base n

やってきました因縁の D 問題。前回の虐殺劇が記憶に新しい>20210206p01.02。今回も E 問題が緑色なのに対して D 問題が水色だったりして、正答数に逆転があったもよう。

あれ? やるだけ? という感想はあまりに素直。たしかに優秀な人は目をつぶっていても答えにたどり着けるのかもしれないが、凡人は周到に落とし穴を探し出さなければいけない。

 落とし穴1:基数が変われば必ず得られる数が変わる?

それは1の位についてだけ当てはまらない。基数が3でも4でも5でも、数1は0より大きい1番目の数で変わらない。

そしてこれが、基数の種類を答える問題でないことの傍証になる(そういう誤読が多かったらしい)。無限大の答え方が問題文中にないからだ。

 落とし穴2:その式、d+1 と M(+1) に暗黙の大小関係を仮定していませんか?

二分探索の下限に d+1 を、上限に M+1 を設定していたのだけど、M+1 の方が d+1 より小さいことがあるから、答えを導く引き算の結果が負の数になるケースがあった。

手で計算しているときは自然と自然数の範囲でものごとを考えてしまって例外ケースを無視してしまいがち。

早期に AC を得ていた複数の人が上限を定めない二分探索を行っていたようだ。kotatsugame さんがこの奇妙な二分探索の振る舞いについてツイートしていたので存在は知っていたが、自分で使えるほどには知らないし思い出さない。

 提出 #20335649 (AC / 212 Byte / 64 ms / 14580 KB)

7 WA のあとの AC。どちらの落とし穴もテキトーな入力を与えて出力を見るデバッグで発見した。1桁のケースはタイプするのも簡単だし、それでいて境界に近くてバグが潜みがち。嗅覚を働かせよ。

えびま @evima0

(D 実はもともと「9 1」っていうサンプルがあったんですが、出題の意義が 1/3 くらい消滅する (「1 9」だと 2/3 消滅) ので消してもらいました) https://t.co/NNcbAu6GjF

このツイートはもっともで、そうでなければ D 問題としては易しすぎて出題されなかったと思う。といってもこれだけいくつも罠があって目配りが要求されるなら、AGC の A 問題といった風情もある。

自分より上位の人は仮に D 問題の罠にはまったとしても、さくっと E 問題を片付けてから帰ってきて、結局 E も D も通してしまうというムーブができてしまう。(そもそも罠にはまらないか)それができるからこそそのレイティングなのだ。自分がそれをやろうとすると虻蜂取らずになるのが目に見えているので、1時間かけて D 問題を通しました。今回の成績はABCDの4完最遅レベルでレートは横ばい。

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

フェネック「もともとD問題でXが1文字のケースを、アライさんは2個か3個しか用意してなくて、それだとWAのケース数でコーナーケースがバレそうだからたくさん増やすようにアドバイスしてみたんだけど、どうだったかな?」https://t.co/FxcvbhUJNL

AC が出るまでは WA の数を見て方針を疑ったり挫けそうになったりしたけど、1アイディアで 7 WA が 1 WA にまで減ったりしたから、まあこういうことなんだろうと予想はしていた。まんまと手のひらころころ。

 E 問題 Train

プライオリティキューを書くだけの問題。まあその「書くだけ」ができなくて 2 WA するのが自分なのだけど。

 提出 #20371092 (AC / 998 Byte / 594 ms / 48260 KB)

……だと思ったら、Ruby で最も速い複数の提出が Hash を待ち行列に使っていた。keys.min で最小値を都度取り出す使い方で、それでいて速い。えええ?

あと、久しぶりにプライオリティキューを書いたから速度改善テクニックを1つ忘れていた。ヒープを整理するときに都度都度要素を交換しながら上昇(下降)するのでなくて、ローテーションする感じで、いくつかの要素を順番にスライドさせてできた空きに追加要素を置くのがいい。


2021年02月16日 (火)

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

[AtCoder] AtCoder Regular Contest 112/A,B,C

先週末の ARC。ABの2完でレートは横ばい。ちょっと背伸びして C 問題が今やっと解けたので日記にする(べつに考え続けていたわけではなくて、オラクルが降ってくるのを待っていたのです)。

 A - B = C

 提出 #20145565 (TLE×8 / AC×4)
 提出 #20146816 (AC / 96 Byte / 93 ms / 14500 KB)

一応制約は掛け算していたんだけど、まずは素直に数えて確実に答えを……TLE。見れば一次 の k のΣなので機械的に変形して……AC。

間違った式の変形に5分以上の時間をかけてもしゃーないので、TLE は避けられない。今は(ARC の1問目に対しても)ステップを刻まなければ、答えにたどりつくことさえ覚束ない。

 B - -- - B

どれだけ1円を払っても数の種類は1しか増えないので、基本となる操作は何回2円を払って絶対値を変化させられるか。±B が境界として存在していて、|B| から 0 へ向かう変化と -|B| から負の無限大へ向かう変化が考えられる。反対側の値は1円余らせておくだけでいい。0 を挟んで -B から B の範囲を数えるのが面倒か。親切にも B=0 となるコーナーケースがサンプルのひとつになっている。もうひとつのコーナーケースが C=1

 提出 #20157041 (AC / 204 Byte / 63 ms / 14300 KB)

2 WA のあとの AC。±B と 0 と、それらで区切られた4つの区間を愚直に数えた。

 提出 #20182663 (AC / 145 Byte / 65 ms / 14268 KB)

翌日になって機械的に式を整理したもの。できれば if による分岐を消したかったのだが。

 C - DFS Game

問題の見通しは難しくない。表のスコアと裏のスコアと、手番を渡すか否かのフラグ(子孫ノード数(=スコア計)の偶奇)があって、それらを葉からボトムアップで積み上げていけば先手、後手のスコアが即座に解る。

制約の 1≤p_v<v の解釈に一瞬詰まったけど、p_v の上限が v であることで、逆向きにスキャンするだけで子から親へ順序よく処理できる親切設計だとわかった。

最後まで解らなかったのは青木君高橋君が採用する最適な行動がいかなるものであるか。二人が何を指標にしてどの子を選ぶのか、それが解らないでどうしてコーディングができる? 何をコードにする? 自分はこの、先攻後攻が決まった瞬間に勝ち負けが見えるゲームを、きっと楽しくプレイできるんだろうなあ。

 提出 #20211491 (AC / 568 Byte / 352 ms / 49992 KB)

odd.sort_by!{ _2-_1 }even.each(...) がキモ。これが二人の戦術。


最後まで見えなかった even.each についてもう少し。

even は潜って戻ってきたときに手番が入れ替わらない子ノードを集めた配列。表のスコアが裏のスコアより高いものは手番(※広辞苑にはテツガイの見出ししかない。テバンは業界用語か?)を持っている方がさっさと潜って表のスコアを得てしまえばいい(裏のスコアは相手に渡る)。では裏のスコアの方が高いものは?

裏のスコアの方が高いものは、できることなら相手の手番で相手に選ばせたい。そうすれば表のスコア(低い)が相手のものに、裏のスコア(高い)が自分のものになる。それが可能になるのは、潜って戻ってきたときに相手に手番が渡る子ノード(odd 配列)が奇数個ある場合。手番というババの押し付け合いに勝てる。

 提出 #20212523 (AC / 432 Byte / 255 ms / 54588 KB)

Ruby の他の AC 提出(今のところ2つ)と比べて遅かったので出し直し。100 ms 縮んで遜色がなくなった。省メモリを目論んだが結果的に増えている。配列の配列の配列がよくない。

ところで、再帰呼び出しを行っている解答を手元で実行してみたらいくつかのケースで stack level too deep (SystemStackError) が出て速度比較ができなかった。PC が貧弱なんだな(環境変数か? その解決法はドーピングぽい)。


2021年02月06日 (土)

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

[AtCoder] AtCoder Beginner Contest 191/C,D,B(空白とスペース)

今日の ABC の C と D はちょっと傾向が違ったよね(E と F は時間切れで読んでいない)。C はむしろ復古的かもしれないけど。

 C 問題 Digital Graffiti

どこに着目すれば数えられるのか、わかりますか? わかりません。

 提出 #19978760 (AC / 969 Byte / 62 ms / 14484 KB)

テキトーに注目して数えて、(÷2では)ダメだとわかって(÷3で)やり直して、31 分かけて鬼の羅列である。

(構造の)理解に頭が必要ないという意味で、これも可読性に優れた読みやすいソースコードの例なんですよ。似たような例にすべての繰り返しを for ループで書くなんてありますね。for さえ解れば鬼に金棒、馬鹿の手にハンマー。目に入るすべては釘。打つべし打つべし。

だけどプログラムは構造化と抽象化を(必要である限り)繰り返して、人間はよりハイレベルな意味を読み取らなければいけないんです。あれをどーしたこーしたなんて作業手順を(人間に向けて)仰々しく並べ立てることに意味はありません。それはソースコードの役割であって、人間に向けたコメントには意味のあることを書いてください。

 「黒に塗られた部分は一つの自己交叉のない多角形となることが保証されます。すなわち、」

これって、黒のマスが1つの塊(ドーナツではない)であって、黒の内部に白のマスが島になっていることがない(逆に黒のマスはたった1つの島になっている)ってことだと読んだ。そのあとで補足的に「白に塗られた任意の 2 マスは、辺を共有するマスへの移動を繰り返し、白に塗られたマスのみを通って互いに到達可能である(マス目の一番外側のマスは全て白に塗られていることに注意してください)」ともあるし、問題文は慎重に 書かれていたと思う。

多角形の解釈についても、色が塗られたグリッドであって座標空間上の点列ではないのだから、書かれていないものを見ようとして見るべき角が見えていなかっただけでしょう。

数学の言葉で書かれた制約の読解に普段苦労するので(20201122p01)、今回の問題文に文句はない。

 「AtCoderの何角形問題についてです https://t.co/kVNwsq8xSC」 / Twitter

すごくいい。そうか、ドット絵師と 3DCGモデラーがいただけなのか。

 D 問題 Circle Lattice Points

図形です。

制約が 10^5 だからどうかなーと思ったけど、普通に数えられる範囲だったみたい。手元ではサンプルに2秒以上かかってたんだけど、ジャッジサーバーは速かった。

 提出 #20002500 (AC / 606 Byte / 833 ms / 14420 KB)

1時間かけて、コンテスト終了1分前の提出。よかった……よかった……。

格子点を数える問題で、入力を小数で受け取るのはやっぱり怖い。小数点以下第4位までって書いてあるので、(文字列のまま) 10000 の下駄をはかせて、ついでに諸々の座標が正の範囲に収まるように平行移動した。負の数が混じると整数除算の丸め方向が期待と異なっていて面倒くさい。

# 0 を足すと答えが変わります。難しすぎるでしょ?

 -1/2 #=> -1
0-1/2 #=> 0

# 1 (イチ)が変数 l (エル)で、中身が正の数だったり負の数だったりすると、もう予測できないでしょ?

上記は Ruby の挙動。仲間はずれらしい>「整数同士の除算演算子の挙動 (C言語、C++、Scala、Java、Rust、Go言語、PHP、JavaScript、Perl、Python、Ruby、Elixir) - Qiita」 Python の整数除算(//)も同じく負の無限大方向に丸められるとか。

他の人の Ruby での提出を見ると、入力を to_r するものが多かった。r は Rational の r. 使ったことがないと使えないし、思いつきもしないのだ。

二分探索の探索範囲をちまちま限定したところで、倍の違いが試行1回の違いにしかならないのだから、2つのループは1つで十分でしたね。これは円を4分割して数えられないか考えていたのが尾を引いている。


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

アライグマ「D問題は、円の中の格子点のx座標としてありえる値の範囲がX-R~X+Rだから、x座標を決めたときの格子点の個数が求められればいいのだ! 誤差が大変だから整数で計算して、負の数の切り上げや切り捨ての計算に気をつけて……、罠がいっぱいあって大変なのだ」https://t.co/6z8erFU3Ym

実は二分探索がいらなかった>画像。三平方の定理! 中学生!

 提出 #20013918 (AC / 265 Byte / 125 ms / 14404 KB)

三平方の定理。速い! 短い!

Integer#sqrt なんてニッチなメソッドを使ってみた。

ところで、やっぱり **2 は遅いみたい。引き算を2回評価することになっても覆らないくらいに。


Ruby での提出を早い順に見てるんだけど、どの人もどの人も平方根をとって計算で格子点の数を求めていた。10行以下のスクリプトで。それが間違いなくすごいんだけど(だって開始後30分ぐらいでの無駄なく短い提出だ)、それらをことごとく撃墜した3つの入力(handmade_marginal_{01|03|05}.txt)が、今回はいい仕事をしていたなと。単に to_f を to_r にしたところで、三羽烏のひとつしか超えられないみたいですよ。

Rational だけでなく BigDecimal の存在も忘れていた。これは「任意の精度で 10 進表現された浮動小数点数を扱えます。」 to_d の d は (big)decimal の d. to_f を to_d にしてもやっぱり3つのうち2つが WA になるようなのは、BigDecimal#sqrt を使わないで Math.sqrt を使っているのが良くないんでしょうか。Math モジュールは、標準とはいえ require が必要な添付ライブラリである BigDecimal を知らないのが普通だと思う。

提出して確かめようとしてわかった。BigDecimal#sqrt を使うとサンプル3で既に TLE が避けられない。

 Ruby で一番最初に AC をとった提出 #19982442 (vmi さん)

入力は Rational で受け取っている。Math.sqrt の結果を検算して条件を満たす限り±1の微調整を施し続けている。そして大事なことは、±1した結果の正当性も確かめている。

単純に±1するだけ、しっぱなし、では、handmade_marginal_{00|04}.txt に捕まってしまうようだ。

書き方を洗練させた結果がたぶんこの提出 #20009989 (kyoshida さん)。find メソッドと count に加算する前の nil チェック。

 二分探索解法だが探索がループごとに1回の提出 #19993857 (n4o847 さん)

左右の点のうち1点が二分探索で見つかりました。左右の点の中間座標は円の中心に由来して明らかです。ではもう1点は? a1 = x*2 - a0

 Integer#sqrt が AC と WA を分けた例

違いは1行だけ。Math.sqrt の結果を(floor ではなく)小数点以下第5位あたりで丸めていたらどちらも AC だったんだろうかダメです

これが Integer.sqrt の実装らしい。

def isqrt(n):
    x, y = n, (n + 1) // 2
    while y < x:
        x, y = y, (y + n // y) // 2
    return x

Math.sqrt とは別に用意する価値があるからこそ存在しているのかな。ニッチとか言ってしまったが、こちらが使い所を知らないだけなのか。

 ABC191 - D - Circle Lattice Points - Senの競技プログラミング備忘録

自分は今回も Sqrt Inequqlity のとき(20200316p01)も、浮動小数点数を単純に嫌ったり怖がったりして難を逃れたけど、こういう風に限界を見極めて対応できるの、かっこいいよなあ。

 空白とスペースについて

B 問題の出力例はスペース区切りだけど、問題文は「A′ の要素を空白区切りで順に出力せよ。」という表現になっている。

ここを参照すれば間違いないという定義があるわけではないけど、空白が white spaces の意味なら、ここに改行もタブも含まれると考えるのが普通(※要注意ワード)。自分は「スペース」(ASCII 0x20)と「空白文字」を使い分けているし、AtCoder にもそのように期待している。

というわけで、わざわざ .join(' ') はしない>提出 #19962733

ダメです handmade_marginal_{00|04}.txt に捕まってしまう。Math.sqrt のアルゴリズムに起因して誤差が蓄積するらしい?


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 はたぶん軸に平行な傾きをうまく扱えなかったんだろう。今回は読めていた。