脳log[AtCoder: 2021-09-19～]

最終更新: 2021-09-23T19:26+0900

♪ [AtCoder] AtCoder Regular Contest 126

昨日の ABC に続いて今日は ARC があった。

昨日と同じく ABC の３完(+2WA)。24 時終了でもう 27 時になりそうだけどまだ結果が出ない……(水色に戻れたの？どうなの？)

 A 問題 Make 10

脳内で組み合わせを全探索して優先順位を付けて貪欲法で>提出 #25984785。

 B 問題 Cross-free Matching

LIS が見えていなかったせいで配列に対して insert/delete_at を繰り返す効率の悪い実装になったけど、通るは通った>提出 #25988002 (911 ms)。

LIS ではないこの解答の形は「Shortest Path on a Line」と「蛍光灯」で書いていた>20200826p02。

LIS にすると倍以上速くなってこう>提出 #26015260 (440 ms)。

 C 問題 Maximize GCD

最初にサンプルの３にだけ答えを返すように if で処理を分けた。そうすると残りのケースで K の高すぎる上限を気にかける必要がない。

次に GCD について。砂で隙間を埋めるように１ずつの操作ができるとなると、GCD が取り得る値について A 数列の素因数から推測できることは何もないような気がしてくる。じゃあ探索しますか？

1. 考えてる途中でなぜか +1 の他に -1 の操作もできるつもりになっていて WA>提出 #25992664。
2. -1 の操作に対応した部分を削除して AC>提出 #25993948 (1248 ms)。
3. C 問題も B 問題同様、制約と入力がガチガチに厳しくないのに助けられている。余分な log を削って 943 ms>提出 #26017330。

どうもね、N 回のループの中身を対数時間の処理にするということが、N^2 のループに対する高速化だという意識が強すぎて、N 回のループで前処理をして N 回の本番ループを定数時間で済ませる方が速いという感覚が持てない。N が２×N になってもオーダーは変わらないけど、ループを２本に増やすことに無意識の抵抗があるらしい。

 D 問題 Pure Straight

残っていた 20 分で愚直解だけ>提出 #25995534。

RE と TLE の背後に WA が隠れている可能性がないではないが、「Shift and Inversions」でやったようにうまい遷移と、それと省略を見つけて高速化すればいいのかなと。

最終更新: 2022-02-17T12:53+0900

♪ [AtCoder] 第七回 アルゴリズム実技検定 過去問

第四回までの日記>20201111p01。

課金ユーザーじゃなくてごめんね。@atgolfer1 に流れてきたツイートを見てはじめて問題が公開されていること、第七回が行われていたこと、終了していたことを知ったよ。

 A - チェックディジット

やるだけ。提出 #24382962

 B - 蒸気圧

小さい方を選ぶだけなんだけど、10 分以上切り捨てたり余りを取ったりして悩んでいたのは内緒。提出 #24383193

 C - 入力チェック

Ruby なので 10 進 100 桁はなんの障害でもなかった。提出 #24383281

 D - 書き換え

５つのパターンをじっと見れば最終結果に影響するような文字の取り合いがないことがわかる。提出 #24383341

 E - 青木君のいたずら

探索が許されていることと操作が１回に限られていること、それと遷移が足し算ではなく掛け算だという点が違うけど、問題の形としては ARC122 の C 問題 Calculator を思い出した>20210612p01.03。これが解ければ ARC122-C も解ける！

提出 #24383572

 F - ダブルブッキング

スケジューリングの問題だけど、求められているのが最適化ではなく判定だという点で、最も簡単な部類。提出 #24383711

 G - べき表現

20 分考えた。

どんな正の整数でも、テキトーに選んだ正の整数を基数としてその冪乗の和で表せるのは当然だけど(N 進数ってそういうもの)、使える数字が 0 と 1 と -1 に限定された 3 進数ではどのように事情が異なってくるか、という問題。

2×3^x = 1×3^{x+1} - 1×3^x

という感じで、2 を -1 に置き換えてから次の桁にツケをまわしていくのがいいでしょう。提出 #24384055

 H - 折れ線グラフ

解けてないよ。制約が小さいから探索していいのだろうけど、それでも 100 の 100 乗になるようなバカな探索は許されない。私はバカです。

 @2021-11-15 TLE→AC

上限の揃った制約が DP だと告げている。それも３乗の。まだ８問目だからって雑な探索で解けるとなめてかかっていたのではないか？

1. 提出 #27281059 (TLE×4) 腰を据えてもこれである
2. 提出 #27281255 (AC / 476 ms)

なだらかな折れ線グラフを書きたいのだから、遷移先の幅は自ずと限られる。(W = A.sum/[N-2,1].max+1 -2, +1 はテキトー)

 I - ほくろ

「ABC-D 虐殺三銃士」のひとつ「Congruence Points」を思わせる問題だけど、両目の位置を手がかりに確定した情報が得られるところが優しい。

図形問題は行列や複素数に計算を丸投げしがちなので、これは自分で式を書いた。25 分かかった。提出 #24392172

 J - 終わりなき旅

「強連結成分分解をしよう」がキーワードだった競プロ典型 90 問の 021 - Come Back in One Piece（★5）がすぐに思い浮かんだんだけど、深さ優先探索を２回するんだというアルゴリズム解説は何か所かで読んでたんだけど、これは 17 問ある★５問題のうちで解いてない３問の１つなのだった。

雰囲気は掴んでいたので雰囲気で書いた。提出 #24393748。細部が詰められてなくて無駄があるかも。競プロ典型 90 問のおかげでアルゴリズムの顔見せだけは済んでいたので、今度は実装するところまでこぎつけた。

 K - 急ぎ旅

理解が甘くて 1 TLE。実装ミス(< にすべきところを <= にしていた)で 1 WA。AC はこれ>提出 #24424698。

最短経路問題ならダイクストラ法なんだけど、満足度と所要時間の２つを考えなければいけないのをどう考えるか。所要時間が最短であることが第一で、満足度の高さはその次に考慮すればいいだけなんだけど、だけど、「満足度について、同じ都市を 2 回以上経由してもその都市の景観は 1 回しかカウントしません」という文言がちょっとひっかかるよね。経路を記録して重複を排除しないといけないの？(それには無視できないコストが……)

もちろん負の移動時間はないから、同じ都市を２度訪れる経路が最短になることはない。だけど次の２つのようなパスで所要時間の合計が同じになる場合をどのように扱うか迷った。

都市 M に着いたときの満足度の総和は明らかに２、３、４を経由してきた経路の方が大きくなるんだけど、もう一方の経路は M のあとで７、８、９を経由することで取り返すことができるかもしれない。M に着いたときの満足度の低さを理由にして一方のパスを捨てていいのかどうか。

実は上の図には嘘があって、上の図のような状況の実際は下のようになっている。

これは１と M とのあいだの最短所要時間と、M と N とのあいだの最短所要時間がどちらも１つの値に決まることからわかる。最短経路であるどの２つのパスを取り上げても、分岐と合流を繰り返す第３のグラフのような関係になることが納得できたら、ある都市に最短で到着する経路のなかから最大の満足度を記録するのでいい。

 L - たくさんの最小値

セグメントツリーなんだけど、最小値を持っているインデックスをどうやって列挙するかという問題。

最小値の記録と添字の記録をセグメント木と配列で分担しようとして TLE を出したり(提出 #24408482)、セグメント木の実装ミスで大量の WA を出したりしつつ(提出 #24412768)、三度目の正直で AC>提出 #24413254。

セグメント木を上から下に下るのって苦手。(根っこが上です。逆にすると頭が働かない)

 M - 分割

全部を分割した状態から始めて、損をしない範囲で統合していくのかなと思ったけど、並べ替えができなくて境界が入り乱れるのを、どう整理して扱えるのかわからない。

とある赤亀コーダーさんによると全体でこの M が一番難しかったらしい。

 N - モノクロデザイン

昨日これの簡単なバージョンを解いたよ>「B - すぬけ君の塗り絵 2 イージー」(提出 #24414821)。

二次元累積和かなと思うんだけど、ABC203-D Pond も競プロ典型 90 問の 081 Friendly Group（★5）もまだ解いていない。二次元累積和って累積和の累積和とは違うんだなー、という感想を持ったのは覚えてるけど、よく思い出せない。

 O - コンピュータ

O 問題が解けたのは初めて。

入力を圧縮したり累積を記録したりして計算量を削減するのは、競プロ典型 90 問の 089 - Partitions and Inversions（★7）ぽいなーと思った。

以下は考えたこと。

1. ある B より後ろにあって、前にある B と同じかそれより小さい B は無視できる。
2. だから N 個の入力は、B の増加列といくつかの A を足してまとめたもののペアとして圧縮できる。
3. 最終日までに得られる報酬の総額は決まっている。コンピュータに支払う金額をどれだけ減らせるかという問題。
4. 十分な資金があるなら明らかに B の最大値と同じ値段のコンピュータ１つだけを買うのが最適。
5. しかし資金が足りない場合は目の前の障害(B)を超えられるだけのコンピュータを買って、目先の報酬を得るようにしなければいけない。
6. なんですかね、貧しさ故に最適な選択ができないって、現実ですか。保険とか追証とか宝くじとか。
7. 複数の買い方。障害(B)が１、２、５、６、９と並んでいるときに、１を買って５を買って９を買うのがいいか、２を買って６を買って９を買うのがいいか。局所的な判断では決まらないので貪欲法は使えない。
8. 迷うたびにキューを伸ばすと爆発するので DP っぽいなー。
9. N^2 のループは許されていないので、すべての i についてそれより後ろにあるすべての要素を処理対象にすることはできない。
10. i<j<k とする。コンピュータはできるだけ買わないのが正解だから、ある i と j がともに k にある障害を越えるというとき、j から k への遷移が i から k への遷移より得するということはない。
11. i を通過する時点ですでに k を超えられるだけのコンピュータを買う資金があるのだから、到達地点が同じ k なら j で足踏みする価値がない。
12. j で足踏みする価値は k より遠くへ(k を超えて一足飛びに)到達できる可能性にある。
13. という感じであとはがんばってコーディングする。提出 #24429839
14. .each_with_index.each とか謎なことしてる……。幸いにしてこれは無駄なだけで害はないけど、部分的な修正を繰り返すとこういう風に、(通して書き下したときにはありえない)謎なバグを仕込みがち。

最終更新: 2021-07-19T22:56+0900

♪ [AtCoder]AtCoder Regular Contest 123／C 問題 1, 2, 3 - Decomposition (+ B + A)

悔しいなあ。手も足も出ない方がまだあきらめがつく。

 提出 #24373137 (WA×20 / RE×12 / AC×2)

１時間かけてコンテスト終了直前に投げた。サンプルすら通っていないけど、５つあるケースの最後の１つの答えが違っているのに気がついていなかった。ダメダメである。

RuntimeError の原因は Array#compact が false を取り除いてくれていないのに気付かずそのまま min メソッドを呼んだこと。

Wrong Answer の原因は比較して小さい方を選ぶべきところで、勝手に優先順位を付けて先に値が得られた方を選んでいたこと。それともう１か所(b+(d-1)%10 の %10 が完全に余計)。

プログラムの型は Send More Money と同じ>20210412p01。桁を見て、キャリー(ボロー)を伝えて、最後まで矛盾なく桁が確定できるかどうか。それを k を増やして条件を緩和しながら最小値を探った。

答えの上限が５だと見抜いていたところは偉いと思うんだ。なぜ５かといえば、項数が１ならある桁に関して作れる数字が 1..3。２なら 2..6、３なら 3..9、４なら 4..12、５なら 5..15 ということで、最初に 10 種類の数字が作れるのが５項の和。0..4 の数字を作ろうとすると繰り上がりが不可避なのが制限だけど、それは隣の桁で吸収できる。６以上に項数を増やしてもできることは増えない。

 提出 #24375535 (AC)

ほとんど違いませんよ。でも A から F まで６問ある中の３問しか相手にしていないのに、時間内に完成させられないんだなあ。

実行時間から判断するにだいぶ無駄が多いみたいだけど、制約に苦しめられてたったひとつの解法、たったひとつの記述を探らないでいいってすばらしい。

 B 問題 Increasing Triples

ただの貪欲。提出まで 15 分>提出 #24363550

 A 問題 Arithmetic Sequence

AC まで 2 WA、33 分。どういうこと？ 10 分時点で９割５分は完成していた>提出 #24355415。デバッグ出力を消し忘れてるのと、入力を勝手にソートしてるのがいけない。列(Sequence)は順序付き！(知らないわけではない。括弧と波括弧に使い分けがありそう？ それは知らない)

AC>提出 #24361099。ほとんど違いませんよ(２回目)。

最終更新: 2022-01-25T19:28+0900

♪ [AtCoder]AtCoder Beginner Contest 210／E 問題 Ring MST (+D 問題)

A 問題から WA を出して、D 問題も 4 WA のち AC だったけど、D 問題が水 diff だったおかげで４完最遅に近かったはずでもそこそこのパフォーマンスがもらえた。棚ぼた。E 問題が解けなかった。

 提出 #24322478 (RE×11 / AC×19)

30 分考えて出したコンテスト中唯一の提出。ソースを見ればわかるけど、３分岐のうち２つしか埋まっていない未完成の状態。未実装部分に 1/0 (ZeroDivisionError) を埋めておくことでジャッジ結果を AC/WA の２択ではなく AC/WA/RE の３択にするテクニック。WA がなかったということで、中身のある２分岐にミスはなさそう。

 提出 #24337207 (AC / 273 ms)

複数の A 要素の関係について、中国剰余定理が関係してくる気がしてお手上げだと思っていたのだけど、GCD で良かったらしい。まだ理解していない。

 D 問題 National Railway

DP です。１行目から行ごとに考える。

1. ある行について。処理済みの地点に建てた駅からこの行この列に至る最小のコストを記録することにする。
2. その次の行にて。各列 Aij の費用を払って駅を建てたとする。前の行の j 列に記録されたコスト(の先にある地点)をもうひとつの駅として、建設費用を計算する。
3. 建設費用の最小値が答え。

罠があるとすれば、同じ行から２つの駅を選ぶ場合を見落とさないこと。見落とさないこと。慌てて対応をミスって WA を重ねないこと。

 提出 #24314328 (AC / 559 ms)

m1 が同じ行内からもう１駅を選んだ場合の建設費用。m2 が前の行の同じ列から下に線路を引いてきたときの建設費用。

その他の処理は「この行この列に至る最小のコスト」を記録するためのもの。上の行から引っぱってきた線路を延長するのがいいか、Aij を払ってその場に駅を建てるのがいいか、同じ行の左右から線路を引いてくるのがいいか、最小費用を記録する。

ところでこの問題、「鉄道建設にかかる費用として考えられる最小値を出力してください。」で問題文が締められているのだけど、２、３回読み直したよね。え？ どのような鉄道を敷けばいいのか示されてましたか。まさか「高橋君は国民の利便性を上げることよりも、鉄道建設にかかる費用を少なく抑えることを優先したいと考えています」が真実その通りで、1000000 マスのうち最低でたったの 2 マスをカバーする鉄道を敷設するだけでお茶を濁すつもりだなんて、一読しただけでは飲み込めなかった。高橋王国民甘すぎ。

最終更新: 2021-07-14T01:38+0900

♪ [AtCoder] 競プロ典型 90 問／083 - Colorful Graph（★6）

たいへん厳しい。解説１、解説２、解説３、解説４。

解説を読めば半分全列挙と同じように、汎用的な手法であるが故に問題から解法を見出そうとしても出てこないタイプの問題と解法だったと言えるのではないか。

以下は解説を読む前の提出。

 提出 #23928493 (TLE×9 / 同じ内容) ※TLE×4 に改善できる

クエリを先読みして頂点ごとに関連するクエリ番号をためておき、メインループは辺について繰り返すことにした。メインループの中ですることは辺が結ぶ２頂点が持つクエリ番号列のマージ。色の伝播を担うのが辺だということと、現在の色を決めるのは直近のクエリだということに着目した解法。

解説１にも書かれているように、これは特定の頂点に辺とクエリが集中したときに処理時間をオーバーする。とはいえこの提出のマージ部分は不必要に時間をかけている。２つのクエリ番号列の長さの和に比例した時間ではなく、二分探索を繰り返してもう少し(＜コレ)ましな時間にできる。その場合の TLE は(おそらく)４つ(random_challenge のうち２つと random_clique ２つ)>typical90_83_TLE4？.rb27。

 提出 #23932276 (TLE×8 / 同じ内容)

この問題の悩みの種は、クエリに応じた色の変化を隣接ノードに「通知する」ことも、逆に隣接ノードに現在の色を「問い合わせる」ことも、制約から許されていないということ。

ここで、親にだけ通知してみるのはどうだろうと考えた。隣接ノードの数は N のオーダーになりかねないとしても、親であれば１つに決めていい。問題は親の決め方で、この問題のグラフは木ではない。

この提出ではノード番号が小さいものを親の側にあるとした。いきなり「親は１つ」ではなくなっているがしかたがない。だからこその TLE×8 なのだ。

 提出 #23933074 (TLE×5 / 同じ内容)

所与のノード番号を利用するアイディアはお手軽に過ぎたので、今度はちょっと手間をかけて深さ優先探索で親子関係を決め、閉路が見つかったときに限り余分な親を追加することにした。残る TLE は５つ。

テストケースをダウンロードしたら、TLE になっているのは random_clique と名付けられた全２ケースと random_kill と名付けられた全３ケースの合計５ケースだった。自分の解法に弱点があり、そこを見事に狙い撃ちされたといったところか。定数倍の改善では全然間に合わない。

 提出 #23996165 (TLE×2 / 同じ内容)

閉路が見つかったときにどちらをどちらの親にするかは好きに決めていい。親の数を比べて親の数が少ない方に他方を親として追加することにしたら、random_kill と名付けられた３ケースの TLE が解消した。

残るは random_clique が２ケース。random_kill が特定の１、２ノードに辺が集中していたのに対して、この２つのケースはまんべんなく多くの辺が伸びている。クエリに応答する負荷が全体的に底上げされていて逃げ場がない。

 提出 #24004617 (TLE×2 / 同じ内容)

クエリの先読みをしたらメインループの前準備で探索のためのスタックがいらなくなった。クエリに関与しない頂点は無視していいし、入力された辺も片方向だけ記憶しておくのでいい。どちらをどちらの親にするかを決める

# P[v].size は親の数。Qn[v] はクエリで参照される回数
if P[a].size*Qn[a] < P[b].size*Qn[b]

という判定はメインループの負荷をよく反映していて気が利いてると思う。すべてクエリ先読みの効果。でもダメ(TLE)です。さっきの TLE×2 からはローカルで 12 秒が 7 秒になったけど、ならジャッジサーバーでは良くて 5 秒だろう。制限は 3 秒。

最終更新: 2021-06-17T19:54+0900

♪ [AtCoder]競プロ典型 90 問／035 - Preserve Connectivity（★7）

解説はこちら>解説１、解説２、解説３

 LCA とダブリング

「実装したことはないけどダブリング(要は繰り返し二乗法でしょ？)で効率的に親を辿る？」と書いたのがつい先月のことだけど、とうとうダブリングを実装する機会が訪れた。

この問題がどうして、選ばれた複数の頂点を決まった順番で環状に並べて隣接する頂点ペアの LCA が辺の本数になって割る２が答え、になるのかは解説３を読む。今は LCA にだけ注目する。

LCA の取り扱いは「巨大企業」や「筆塗り」で経験があるけど、線形より効率的な LCA の検索が案外面倒くさい。「最小共通祖先 [いかたこのたこつぼ]」にいくつか手法がリストアップされているけど、自分が知っている手段はセグメント木だけであり、セグメント木は書くのが面倒くさい。

そこでダブリングです。

 提出 #23482710 (TLE×26 / 810 Byte / 2207 ms / 42608 KB) ※まだコンテスト期間中であり見られないはず。

間違えた(TLE)。

A = [ps=P.dup]
(D.max-1).bit_length.times{ # １世代上はすでに P としてあるので、１回分繰り返しが無駄かも。
	A << ps = N1.times.map{|a| ps[ps[a]] }
}

Ans = lambda{|a,dd|
	i = 0
	while 0<dd
		a = A[i][a] if 0<dd&1
		dd >>= 1
		i += 1
	end
	next a
}

A 配列に事前に親、親の親(２世代上)、４世代上、８世代上、とメモしておいて、Ans 関数(Ancestors の略ったら略)で「a の dd 世代上は？」という質問に対数時間で答えられるようにした。Ans 関数がこのようなインタフェースになっているのは、LCA を経由した２頂点間の辺の数を求めたい呼び出しもとで「同じ深さにある２頂点 a,b が初めて祖先を共有する深さは？」という問いを立てて、二分探索でその深さを確定させようとしたから。次のように。

Dst = lambda{|(a,b)|
	da,db = D[a],D[b]
	dc = (1..[da,db].min).bsearch{|dc|
		Ans[a,da-dc] != Ans[b,db-dc]
	}
	next dc ? da-dc+db-dc+2 : (da-db).abs
}

競プロにおいては対数は定数と言われるけれど、かなり大きな定数ではあり、必要がないところで log をくっつけると TLE に苦しめられたりする>「Pairs」。同じ日記に書いてあるけど、「射撃王」や「Handshake」のように余分な log があっても TLE にならないこともある。

 提出 #23482781 (AC / 873 Byte / 1082 ms / 42672 KB) ※まだコンテスト期間中であり見られないはず。

A 配列は正しくはこう使う。共有されている yuruhiya さんの解答 を見ても LCA#lca メソッドが同じ感じだったので、大嘘はついてないと思う。(Dst は Distance の略。D は Depth の略)

Dst = lambda{|(a,b)|
	da,db = D[a],D[b]
	a = Ans[a,da-db] if db<da
	b = Ans[b,db-da] if da<db
	A.reverse_each{|ans|
		a,b = ans[a],ans[b] if ans[a]!=ans[b]
	} if a!=b
	next a==b ? (da-db).abs : da+db-2*D[P[a]]
}

実は解説２にはこれを説明する具体的手順が書いてある(あとで詳しく読んだ)。だけどありとあらゆる落とし穴にはまりたがる自分にとって、「こうすればいいんですよ」とか「こうしてはいけませんよ」いうアドバイスは役に立たないんですな。「要は繰り返し二乗法でしょ」というだけの理解で実装してみて、「あれは良かったここはダメだった」と納得するまでは身にならない。仮にアドバイスのおかげで最初からうまくやれたとしても、それは今回だけのことであり、将来必ず自分の性向に導かれて穴にはまる。早いうちに地図を作っておくべきだ。そうすれば多少は、ね。

最終更新: 2021-06-21T21:06+0900

♪ [AtCoder]競プロ典型 90 問／068 - Paired Information（★5）

すごく難しいです。答えの出し方に確証が持てないまま、とりあえずグラフとして解答を書いた。クエリ０に応じて辺を追加する。クエリ１に応じてノードの値を確定しながら X から Y までグラフをたどる。しかし TLE。

 提出 #23506723 (TLE×10 / AC×3) ※まだコンテスト期間中でありアクセスできないのでこっち>提出 #23506723.rb27

次にクエリ０では Y=X+1 だという制約を思い出して、グラフを配列上に配置した。しかしこれでは多少効率が良くなれど TLE は解消しない。制約はノード数(N)、クエリ数(Q)ともに上限が 10 万であり、１つのクエリに答えるのに線形時間をかけることができない。

局所の変更を全体に(対数時間で)波及させるのに BIT がまず浮かぶ。何を記録しようか。階差の累積値かなと思った。つまり、連続する３要素 A,B,C があり、２度のクエリ０によって A+B=S, B+C=T であるとわかっているなら、C-A=T-S から１つおきの２要素の差が直接にわかる。これの累積を記録しておけば、クエリ１で X と Y が 2×k はなれていても直接計算できる。

 提出 #23510943 (AC / 669 Byte / 413 ms / 31888 KB) ※まだアクセスできないのでこっち>提出 #23510943.rb27

結局 BIT は使わなかった。クエリへの答え方は階差の累積という点で同じだけど、クエリの先読みをすれば事前に累積値が記録しておける。更新がないなら値の取得に対数時間がかかる BIT よりただの配列の方が良い。Ambiguous と答えるタイミングは Union-Find で管理した。

 「《上級者向け（★7）》 X[i] + 1 = Y[i] の制約を外した場合（ワナにとても引っ掛かりやすいです）」

階差を使う解法は完全に「Y=X+1 (T=0 の場合)」という制約に依存しているので、とっかかりを失って困ってしまった。グラフなら困らないが TLE。階差を封じられてどうすればよいか。

 「A_1 と A_2、……、A_{N-1} と A_N の関係性がすべて分かっていた場合、A_1 の値を +1 すると、下図の通り +1 される要素と -1 される要素があります」

解説が公開された。プラスかマイナスか、そんな単純な関係やったんか。それにしてもそこからさらに(厳しくない方の)制約をクリアさせられることがもうつらい。

Y=X+1 (T=0 のとき) という条件が外れた厳しい方の制約だけど、X から Y へ至る異なるパスがクエリ０によって与えられたときにどうすればいいかわからないでいる。定数時間で答えるためにどのような情報の持ち方をしておけばいいのか(グラフは TLE)。でもプラスかマイナスかという単純な関係なのならば、すべてのパスに関わるノードをまとめて詰め込んでおいて、つじつまが合うのだろうか。

連結なノード間であるノードを基準(たとえばゼロ)にして相対的な値を割り振っておく。ノード間の距離(の偶奇)も記録しておく。迂回路があっても分岐点・合流点のノードが持つ相対値はパスによらず共通だし、パスによって異なる非共通ノードも、ノード数の偶奇はたぶん同じになる。まだよくわからないのは、連結成分ごとに基準となるノードが必要だけど、連結成分同士が連結するたびに基準と相対値のふり直しをして許されるのかというところ。小さい方の連結成分を選ぶようにすればいいのだろうけど。

全部 Union-Find に乗せたいけどうまくいかない。Unite は当然として、Find で集合の代表を書き換えるタイミングでもごにょごにょすると、集合の合体があったとしても偶奇と相対値を適切に(新しい代表を基準にして)更新できると思うんだけど、符号で死ぬほどバグらせる。一見正しい答えに見えても、バグ×バグ=正常だったりする。

 https://github.com/monnu123/atcoder_files/blob/master/kyopro90-68.cpp (monnu さん / C++ / 166 ms)

自分がやりたいのはたぶんこういうの。やっぱりできるんだね。不可能をやろうとしてるのでないとわかったのは朗報。

ところで、Ruby のようなスクリプト言語と C++ の実行時間が接近しているときは、入出力がネックになって C++ の実行時間が遅くなっている印象がある。C ランタイムとの連携を切ったり、std::endl が引き起こす flush を "\n" で回避したり、いろいろ対処法がある模様。

 https://github.com/NachiaVivias/kyopro-tenkei-90-submit-nachia/blob/main/shared-solutions/068-Paired-Information/068-01.cpp (Nachia さん / C++ / 51 ms)

こっちの見た目すっきりな方はすっきりしすぎてて自分がやりたいことと同じなのかどうかもわからない。

ノード数が 2N あるなあ。前半 N 個と後半 N 個の位置づけとは。

偶数世界と奇数世界？ これはノード番号 X が偶数か奇数かという話ではなく二部グラフの話なのであって、あるノード X を赤色で塗った場合と白色で塗った場合を同時並行で扱っているのではないか、という……あてずっぽうです。

 提出 #23560415 (AC / 778 Byte / 334 ms / 16544 KB) ※まだアクセスできないのでこっち>提出 #23560415.rb27

やった！ うんざりするほどバグらせてついに完成した(UnionFind 全乗せ版)。頭が整理されたところでバグまみれを捨ててイチから書き直したのが良かったと思う(それからもバグらせたんだけど)。

	D[a] *= D[g]
	V[a] += D[a]*D[g]*V[g]

↑ここは無駄なことをしてる。修正版はこう↓

	V[a] += D[a]*V[g]
	D[a] *= D[g]

Union-Find でグループの代表とサイズを管理するのはこれまでのおなじみだけど、同時に代表からの相対値を記録するのは考えたこともやったこともなかった。「重み付き UnionFind」というものがあるらしいが、いったい何に使うものなのか。

ノード数が 2N のすっきり解法は遠くから拝むだけにしておきます。

 https://gist.github.com/masa-aa/4be96f053457dc60625a3552288fb1e4 (masa_aa さん / PyPy3 / 304 ms)

これも重み付き UnionFind。ノード番号の偶奇を利用すれば別途偶奇の管理をする必要がないらしい。クエリへの応答部分でだけ偶奇を気にすればいいというのがよくわからないが、たぶんこれを考えた先に Nachia さんのサイズ 2N のグラフがあると思う。

偶奇を一体でぐちゃぐちゃ扱う(自分)→偶奇に前提をもうけて整理されたグラフを作る(masa_aa さん)→偶奇と奇偶を並行させて偶奇の別を気にしない(Nachia さん)、という違いなのではないか、という印象を持っている。

あ find メソッドで再帰呼び出しをしていない。スタックオーバーフローのおそれがないのはいい。

これだけの学びがあるのは企画の趣旨に照らして(そうでなくても)、すばらしい良問だったのでは？

最終更新: 2021-07-12T20:54+0900

♪ [AtCoder]東京海上日動 プログラミングコンテスト2021（AtCoder Regular Contest 122)／A,B,C

 A 問題 Many Formulae

A 数列を後ろから見ていく方針は早くに決まったのだけど、初項を [1,0] ではなく [1,1] にしていたミスでいつまでも答えが合わなかった。あと余りを取り忘れて 1 TLE。

 提出 #23369338 (AC / 147 Byte / 106 ms / 24936 KB)

もう 54 分経っている。

 B 問題 Insurance

A 数列をソートすれば賢く答えが求められそうだけど、何も考えずに探索しても良さそう。この前の ABC204-E Rush Hour 2 と違って最初から実数解が求められているあたり、罠もなく素直なのでは？

デバッグ出力を消し忘れて 1 WA。bsearch メソッドで極小値を求めようとして 1 WA。三分探索(名前だけは知っていたが初めて書いた。「三分探索を救いたい - Qiita」)を 100 回試行しようとして 1 TLE。ざっくり半分の 50 回にして AC。本当は探索範囲の幅が許容誤差以下になったかどうかを終了条件にすべきだったそれもダメ？。

AC までおおよそ 30 分だから B 問題は A 問題より簡単。

 C 問題 Calculator

盲滅法な探索では時間が足りない。考えても時間の無駄なので興味本位で解説を読んだ>「C - Calculator 解説 by maroonrk_admin」

フィボナッチ数？ 「競プロ典型 90 問」でも見かけたが、この数列がどうして頻繁にあちこちに登場するのかわからない。限りなくありふれたジェネレータなのか(知らなかったけど A 問題にもフィボナッチ数が現れていたらしい)。あと、計算途中で１を足すという行為が、新しい系列のフィボナッチ数列を開始すること、それらずれたフィボナッチ数列を串刺しにした和が数列として現れるということもあまりピンとこない。そうなの？ そんなこと漸化式を見てわかる？ 足し算とはそういうものだ、と言われたら言葉がない。私は足し算がわかりません。

とりあえず実験をした。x,y=1,1 を初項として操作３と４を繰り返すとどのように値が増加するか。大体 80 数回で N の上限を超える。今度は x,y=0,0 でスタートして 80 数回の１か所でだけ +1 をすると、80 数回の操作３、４の結果がどういう値になるのかを調べた。これは並べるとフィボナッチ数列になった。

つまり、次の提出における A 数列というのは、フィボナッチ数列を貼り付けたものではなく、+1 するタイミングによって操作３と４を繰り返したのちのちにどれだけの影響を及ぼすかというのを予め調べた実験結果なのである。

 提出 #23379308 (半分くらい WA)

「貪欲をすればよい」と解説に書いてあったので貪欲をした。フィボナッチ数列の増加のしかたを見れば組み合わせでどんな数字でも作れそうな雰囲気はある(基数の冪乗を大きい方から取っていくのと同じように)。

「この時，i と i+1 両方で操作することはありません． なぜなら，」は読み飛ばした。解説の細かい部分にこだわってもわかりません。

WA の原因は問題を読み誤っていたこと。x か y のどちらかが N になればいいと思っていたが、そうではない。

 提出 #23379741 (AC)

x と y を取り替えればいいのだから、仮の操作列を作ってから必要に応じて操作１と２、操作３と４を交換するようにした。最初からきれいな解答を作ろうという努力はあきらめている。

ARC-C が自分のいるところからどれだけ高くにあるかは垣間見られたのでは？ 時間内に B 問題まで解けただけで上出来なのに、レイティングは下がるんですよ。緑に対してあまりにひどい仕打ち。A、B がどちらも茶 diff だといっても、ARC に参加する層にとっての茶 diff だという意味で、ABC の茶 diff 問題とはくらべられないと思うんだ。へなちょこながら ARC に参加する意気にレイティングで報いてほしい(嘘です)。

最終更新: 2021-09-14T17:27+0900

♪ [AtCoder]競プロ典型 90 問／059 - Many Graph Queries（★7）

AtCoder タグを付けてるけど非公式コンテストです。

この問題はとっかかりがなくて最初から解説を読んだ>解説１、解説２、解説３。

 キーワード「DAG を使いこなそう」

この問題で扱われるグラフは DAG (有向非巡回グラフ) といわれるもので、サイクル(閉路) を含まない有向グラフです。

えっっっ？ どこに閉路を含まないって書いてあった？ 問題文を３回読み直して気がついた。

辺 i は頂点 Xi から Yi に向かいます。

制約 1≤Xi<Yi≤N

制約が持つ情報量が多すぎて見逃していた。難しい。そして閉路が含まれてるなら含まれてるで、解説３に書かれている強連結成分(SCC)分解を手段として持っておくべきであると。

 提出１ (TLE×6 / 3325 ms / 461844 KB) 得点 2/7

まだコンテスト期間中だけどソースコード共有の動きがあるくらいなので隠す必要はないかなと>「解説が公開されたら、ソースコードを共有していきましょう」。

N,M,Q = gets.split.map(&:to_i)
B = 60 # Bignum に切り替わらないビット数を。
Z = (N-1)/B+2
V = Array.new(N+1){|a| [0]*(Z-a/B) }
E = Array.new(N+1){[]}; M.times{
	x,y = gets.split
	E[x.to_i]<<y.to_i
}

N.downto(1){|a|
	va = V[a]
	va[-1] |= 1<<a%B
	E[a].each{|b|
		V[b].each_with_index{|v,i|
			va[i] |= v
		} if va[a/B-b/B-1][b%B]<1
	}
}

puts$<.map{|ln|
	a,b = ln.split.map(&:to_i)
	next %w[No Yes][V[a][a/B-b/B-1][b%B]]
}

２枚目の解説画像で満点解答のために「ビット演算で 64 倍高速化」と書かれていることから、Ruby で満点解答が望めないのは明らか。Ruby を使うことによる定数倍のハンデが最初から 100 より大きいので……。手元では V = の初期化部分だけで２、３秒かかってるもんね。部分点２で満足している。

AtCoder はスクリプト言語に優しいので、定数倍高速化がキーになるのは非公式コンテストならではかな。解説が大いに参考になる。

昨日の ABC204-D - Cooking の解法はどこか(解説１)で見たような形だなあと思いながら書いていた(この日記を書いてるのは月曜だけど、典型90-059の出題は土曜日だったので、日曜の ABC の前に取りかかっていた)。

 解説と違う点

キーワードからこうだろうと最初に思いついた方法で実装したら解説とちょっと違う。違って良くない。

最初にすべての頂点について到達可能な点を(テキトーにビット演算を使って)調べてからクエリに定数時間で答える、というのがさっき貼り付けたスクリプトだけど、解説ではクエリを 64 並列で調べるようにしていた。クエリが起点にある。

調べたら、重いケースでは頂点数(N=100000)、クエリ数(Q=100000)に対して、実際に到達可能性が参照される頂点の種類が 84000 ちょっとになるものがほとんどだった(例外が 99999)。約 16000 の頂点に関しては到達可能地点を調べたのが無駄だった。まあ、無駄を省こうとするとスタックオーバーフローを避けてごてごてと記述と条件判断が増えるわりに、２割も違わない(それも入力依存)という見かたはできる。

必ずしも良くないばかりでもなくて、頂点数 N に比して辺数 M が大きい場合、想定解法の方が遅くなる。

 提出２ (MLE×1 / 1154 ms / 1244032 KB)

基本は提出１と同じ。30 ビット 60 ビットでテキトーに区切っていた最大で 10 万ビットになりうるビットフラグを、１つの Bignum にまとめた。

多倍長が許されるのは数百桁までかなと思ってたんだけど、(最大で)10万桁でもすっごく速かった。しかしメモリ制限 1024 MB を超えて 1.24 GB 使ったところで MLE。

N,M,Q = gets.split.map(&:to_i)
E = Array.new(N){[]}; M.times{
	x,y = gets.split
	E[N-x.to_i]<<N-y.to_i
}
V = [nil]*N
N.times{|a|
	va,bs,b = 1<<a,E[a]
	va |= V[b] if va[b]<1 while b = bs.pop
	V[a] = va
}

$<.each{|ln|
	a,b = ln.split.map(&:to_i)
	puts %w[No Yes][V[N-a][N-b]]
}

頂点番号とビット位置の対応を逆向きにしたのが工夫(提出１でも Z-a/B という形でやっていた)。たとえば N-1 番目の頂点が N 番目に移動するというのを 0b11 で表現すれば Bignum はいらない。これを素直に 1<<N-1|1<<N で表していたら、ほぼ全ての頂点で N 桁の Bignum が必要になってもおかしくない(頂点１以下全ての頂点が頂点 N に遷移する場合)。しかしあえなく MLE。工夫なしだと 1.29 GB だったから 50 MB だけ減りましたよ。

たぶん Bignum のネックは桁数に比例する部分ではなく、100 桁であれ１万桁であれ必ず必要になる基礎的な部分でのコストなのだろう。その面では 64 ビット版が不利だ。Bignum か非 Bignum かで見れば、上の段落で改善するのは 10 万頂点のうちの 62 頂点程度に過ぎない。桁数部分での寄与は小さい。

 提出３ (AC / 2009 ms / 500612 KB) 得点 7/7

これは提出１、２と違って想定解法と同じ方針。ただしクエリ 64 並列ではなく 10 万並列でやっている。

DP がしたいのに Bignum を頂点の数だけ保持すると MLE になるのをどうすれば良いか。TLE を避けたいなら Bignum を使うしかないがどうすれば良いか。頂点番号の小さい順にどんどん処理を進めて、使用済みの情報は辺もクエリも遷移してきたという DP 要素もどんどん捨てていった。一時的には C 配列に処理待ちの Bignum が蓄えられるけど、どこかから遷移して来るまではそれも 0 (Fixnum) だ。

N,M,Q = gets.split.map(&:to_i)
E = M.times.map{ gets.split.map(&:to_i) }.sort_by(&:first)
A = Array.new(N){[]}
B = Array.new(N){[]}
Q.times{|q|
	a,b = gets.split
	A[-a.to_i]<<q
	B[-b.to_i]<<q
}

r = 0
C = [0]*N
N.times{
	as,bs,c,q = A.pop,B.pop,C.pop
	c |= 1<<q while q = as.pop
	r |= c[q]<<q while q = bs.pop
	C[N-E.shift[1]] |= c while e = E[0] and e[0]+A.size==N
}

Q.times{|q|
	puts %w[No Yes][r[q]]
}

Ruby で満点がありだったのだなあ。道具のせいにしてあきらめなくて良かった。

 提出４ (AC / 1376 ms / 383080 KB)

メモリもタイムもさらに良くなった。提出３がベースだけど、クエリごとに１ビットを使うのではなく、スタート地点 A が共通するクエリが同じビットを共有する。

こちらを参考にして。

昨日はうしさんのライブラリを参考にして解いたため、(A_i,B_i)というクエリを処理するときにはdp[A_i]|=1<<iとしていた。そうではなくdp[u]|=1<<uとし、すべてのペアについて問題を解くことにすれば、頂点番号uに対しては1..uに対応するbitしか保存しなくてよいため、必要なメモリが\frac{N^2}2くらいになるらしい。

頂点番号が小さい順に処理をするという提出３の流れと、頂点番号が小さいものから０に近いビットを割り当てるというのがマッチして、ビットの同時使用量が節約できる。

整理したからそのまま同じではないけど、だいたいこんな雰囲気>typical90_59_nosub5.rb27

@2021-09-14 結局最後のも提出した>提出 #25841973 (1149 ms)

最終更新: 2021-06-05T05:03+0900

♪ [AtCoder] 競プロ典型 90 問／057 - Flip Flap（★6）

解説画像はこちら>https://github.com/E869120/kyopro_educational_90/blob/main/editorial/057.jpg

この問題はとても良かった。確実に力になった。問題を解く選択肢が増えた。キーワードは「行列の掃き出し法を知ろう」だって。

最初は独力でパネルを順番に見ていく DFS を書いた。それしか知らない。だけどどうしても入力に左右されるし、あるパネルに影響する複数のスイッチの組み合わせを総当たりするので遅くなる。

入力を前処理して扱いやすくするとは考えてもみなかった。

でまあ今後は、こういうことができると知ったはいいけど、これが適用できる対象の性質を見抜けるかどうか、というところに課題が移ったとみていいのではないかな。簡単ではないね。

具体的な実装にも迷いがある。スイッチ数(N)、パネル数(M)の上限が 300 なのに対して 550 ms の時間をかけている。メインループだけど、

1. スイッチ群から最も左のビットが立っているスイッチを選んで取り出す
2. 残されたスイッチ群を処理して最も左のビットが取り出したスイッチのものより右にくるようにする
3. 取り出したスイッチを押したり押さなかったりする(最も左のビットが立っているスイッチはこれ１つだけなので確実にどちらかを選べる)
4. 繰り返し

ステップ１の処理が N で、ステップ２の処理が N×M。もっとシュッと片付くうまい書き方があっても良さそうでは？

hai!@magrofly「典型057 Ruby https://t.co/Dri1yBSvuK」 / Twitter

「基底を求める」のはよくわからないけど、「解く」過程では順番に適用していくだけでいいようだ。さっきの手順に当てはめると、基底を求めるのがステップ２に相当して、解く部分がステップ３。ステップ１の検索が不要であると。

 549 ms

最初の提出。無駄にソート、検索している(９行目)。

N,M = gets.split.map(&:to_i)
A = N.times.map{
	gets
	next gets.split.map{_1.to_i-1}
}
S = gets.split.map(&:to_i)

n,T = 0,[0]*M
while as = A.sort_by!(&:first).shift
	i = as[0]
	A.map!{|bs|
		i < bs[0] ? bs : ((as|bs)-(as&bs)).sort
	}.reject!{|bs|
		bs.empty? && n+=1
	}
	as.each{|i| T[i] = 1-T[i] } if S[i]!=T[i]
end

p(S==T ? 2.pow(n,998244353) : 0)

 524 ms

ツイートを参考に改良したが、あまり良くはならない。N,M<=300 だから？ 対称差を求める部分(15行目)が富豪的過ぎるから？ 前処理の部分でまだちょっと変なやり方をしてる？

N,M = gets.split.map(&:to_i)
A = N.times.map{
	gets
	next gets.split.map{_1.to_i-1}
}
S = gets.split.map(&:to_i)

N.times{|i|
	next if A[i].empty?
	(i+1...N).each{|j|
		next if A[j].empty?
		if A[j][0] < A[i][0]
			A[i],A[j] = A[j],A[i]
		elsif A[j][0] == A[i][0]
			A[j] = ((A[i]|A[j])-(A[i]&A[j])).sort
		end
	}
}
A.reject!(&:empty?)
O = N-A.size

T,as = [0]*M,nil
as.each{|i| T[i] = 1-T[i] } if S[as[0]]!=T[as[0]] while as = A.shift

p(S==T ? 2.pow(O,998244353) : 0)

最終更新: 2021-06-24T16:08+0900

♪ [AtCoder] 競プロ典型 90 問／055 - Select 5（★2）

★２つだからってこういう素直なスクリプトを投げた。

N,P,Q,*A = $<.read.split.map(&:to_i)
p A.combination(5).count{|a5| Q == a5.inject{_1*_2%P} }

結果は TLE×21/AC×4。なんだよ全然ダメじゃんかよ。解説画像はこちら>https://github.com/E869120/kyopro_educational_90/blob/main/editorial/055.jpg。Ruby では解説が役に立たない。★６～７相当のより高速な解法があるというから、そちらを解説してもらわねば。

ABC192-F Potion (20210224p01) を思い出しながら悪あがきをした。

N,P,Q,*A = $<.read.split.map(&:to_i)
q = Hash.new 0
S = A.map{|a| q[a%P]+=1; q.dup }
(N-1).downto(N-4){|k|
	S.pop # S.size==k
	q = Hash.new 0
	S.map!.with_index(N-k){|q0,i|
		a = A[i]
		q0.each{ q[_1*a%P]+=_2 }
		next q.dup
	}
}
p q[Q]

これで TLE×6/AC×19。0≤Q<P≤10^9 という制約がえぐすぎるんよな。大きすぎるし、素数じゃないし。いったいどういう手が打てるのか。

N が 100 以下というところで何かできないかと考えた。3..100 のある i より左から A×A のペアを作って記録し、また 1..98 のある i より右から A×A のペアを作って記録し、3..98 の 96 通りのある A_i に関して i の左右から条件を満たすペアを引っぱって来られないかと考えた。P で割った余りは 10^9 通りになりうるけど、A×A%P が取り得る値は 10000 通りより少ないから、左側のペア×A_i を総当たりしても高々 1000000 通りであり、これは許される。あとは右側のペアが定数時間で選べれば良い。ここでモジュラ逆数が使えるような、使いたいような気がするんだけど、法が素数でないから「a が m と互いに素でなければならず、さもなくば逆元 x は存在しない。」と Wikipedia に書かれていて困っている。A×A×A%P の値が決まっているとき、A×A%P の値が何であれば A×A×A×A×A%P==Q となるか。たぶん１つに定まらないのではないかと思う。ここで詰まった。

Ruby を使う良さってこういうところだよね。ぬるい解法が許されないところ(許されるとそれ以上考えないので)。「Ruby ならではのお楽しみポイント」「この前の日記(20200907p01)で散々 TLE に苦しめられた問題も、C++ なら変数 r を map に、変数 nmin を multiset にすることで、ある範囲のキーを二分探索で検索することも、小さい方からキーを取り出すことも、STL 任せで妥当な時間で行える。適当に速くて短い提出を選んだけどこんな感じ>「提出 #16578878」。トリックは必要ない。」 そこは問題の本質ではないからかかずらいたくないという考えもあるだろうけど、自分が一番楽しめるのはここ。

Ruby で 365 ms の解答が共有されているなあ。見たい、見たくない、見たくない。

典型 90-005 の解説から>「mod の値が 998244353 のような特殊な値ではないので一工夫必要ですが、それでもたとえば 3 種類くらいmod を用意して中国剰余定理で復元する方法などで上手くいきます」。中国剰余定理は Wikipedia やブログを読む機会が何度かあったけど、まだ早い、と理解をあきらめている状態。

「線形篩を用いた合成数を法とする逆元の列挙」

最終更新: 2021-06-08T14:11+0900

♪ [AtCoder]AtCoder Beginner Contest 170／F 問題 Pond Skater

競プロ典型 90 問の 043 - Maze Challenge with Lack of Sleep（★4）が普通に解けたので、Pond Skater (青diff1968)も解けるような気がした(既視感>20200826p01。根拠は必要ない)。

 提出 #23175112 (AC / 777 Byte / 492 ms / 46772 KB)

All AC になるまで死ぬほどバグらせた。これが時間内に解ける未来が見えない。訪問済みフラグが二値ではない。ループの継続条件とキューへの追加条件が同じではない。ループのあいだ無条件にキューに追加していると rand_20_01.txt と rand_20_03.txt の２つのケースでキューが複製要素で膨れ上がってしまう。それ以外のケースでは AC なのに。

無駄に難しくしてる？ そうであってほしい。

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

比較すると短いし速いし省メモリだと思う。テストケースハック(※テストケースは公開されている)らしき提出を除けば。

訪問済みフラグを水平方向と垂直方向に分けたのが間違いだったろうか。途中からフラグ(二値)ではなくなったし、紆余曲折を経て扱いが同列だし、単にコストとして再定義して書き直せるのでは？

 提出 #23175271 (AC / 590 Byte / 374 ms / 39016 KB)

Vh と Vv だったものを C に統合した。さらに短くさらに速くさらに省メモリになった。最初にコストでなく２つのフラグを使って書き始めたのが間違いの始まりだったのだなあ(Maze Challenge with Lack of Sleep（★4）の解き方がそうだったからなんだけど)。

最終更新: 2021-06-08T14:41+0900

♪ [AtCoder] エイシングプログラミングコンテスト2021（AtCoder Beginner Contest 202）／E 問題 Count Descendants

解けてしまった問題とまるで歯が立たなかった問題は、日記にならなくて困るという点で共通する。E 問題で Ruby の AC 提出をざっと見たら他の人の解法が異なっていたのでそれを。

ちなみに F 問題の提出(Ruby)はなかった。ゼロだった。まずね、凸包がよくない。それは自分の人生とは一切関わることのない専門用語(だということにしてこれまで無視してきたもの)なので。

話は E 問題。こちらはやること自体は明白で、読めばわかる。木が与えられて、深さを調べるのも、親を辿るのも、基本操作だ。この問題の問題は制約にあって、ノード数もクエリの数も、上限が20万だというところ。定数時間でクエリに答えたい。

 クエリ(U,D)に答える方法１

1. ある深さ D にあるノードのうち祖先に U を持つものを選ぼうか。
2. 実装したことはないけどダブリング(要は繰り返し二乗法でしょ？)で効率的に親を辿る？
3. (ほぼ)全ノードがフラットに並んでたらダブリング関係なくクエリ(N)×ある深さのノード数(N)で死ぬ。

 クエリ(U,D)に答える方法２

1. あるノード U の子孫ノードを深さごとに数えておこうか。
2. 深さを調べる深さ優先探索のついでにそれはできるけど、子ノードが記録した配列をマージするのが大変。ほぼノードの数だけマージ操作が必要。マージテク？

3. 実装しなかったのでこれがアリなのかわからない。子ノードのうち底が深くないものから深い方へ、順番に足し合わせていくとどうなるか。

   一直線の木で Σk 個の要素を処理するような実装でなければアリなのか。

 提出 #22827097 (TLE×27 / AC×3)

これはマージしないでいいように１つの深さ記録配列を共有する実装。ただしノードごとに Array#dup した配列をスナップショットとして持っている。配列の要素数の合計がギガ単位になるけどどうかな、と期待して出したけど全然ダメだった。AtCoder の入力マジえげつない。上限は飾りじゃないのよ。

 提出 #22832306 (AC / 708 ms / 285,364 KB)

基本形はさっきのと同じ。クエリを先読みして必要なものだけ記録するようにした。TLE から 22 分経過していてコンテスト終了まで残り 10 分。あぶなかった。

 クエリ(U,D)に答える方法３

これは他の人の AC 提出を読んで知った方法。二分探索を使うらしい。オイラーツアー？

1. 深さ優先探索で深さを調べると同時に、あるノードに降りてきたタイミングと上っていくタイミングを記録しておく。
2. クエリがきたらノード U の両タイミングの間に処理をしたノード(=子孫ノード)のうち、ある深さ D にあるノードの数を答える。
3. タイミング配列をなめて深さを確かめる線形時間の処理は許されない。どうする？
4. (３つの提出を読んだのに思い出せない) どうする？
5. タイミング配列を深さごとに分けておくのかな。
6. クエリが指定する深さのタイミング配列を取り出して、そこからクエリが指定するノードの子孫にあたる範囲を二分探索で切り出すと、答えがわかる……かな？ 実装して AC をもらってないので不確か。

確かなことはこのあたりの提出を読めばわかる。(提出の早い順)

• 提出 #22837949 (tinsep19 さん / AC / 1016 ms / 94,688 KB)
• 提出 #22839832 (konayuki さん / AC / 910 ms / 296,740 KB)
• 提出 #22841409 (qib さん / AC / 806 ms / 58,764 KB)

メモリ消費にけっこう差があって、自分の提出は最も多い部類。正直どこが原因なのかわからない。

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

♪ [AtCoder] AtCoder Beginner Contest 199（Sponsored by Panasonic）／D 問題 RGB Coloring 2

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

 提出 #22101036 (AC / 343 ms)

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

chokudai(高橋 直大)ナス@chokudai

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

chokudai(高橋 直大)ナス@chokudai

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

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

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

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

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

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

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

• widetree_all2one.txt

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

• widetree_one2all.txt

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

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

 提出 #22109995 (AC / 238 ms)

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

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

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

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

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

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

 提出 #21721083 (AC / 3703 ms)

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

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

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

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

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

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

 Ruby によるすべての提出

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

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

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

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

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

 提出 #21741214 (AC / 921 ms)

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

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

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

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

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

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

 提出 #21743445 (AC / 66 ms)

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

 「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] }]}