最終更新: 2021-03-15T22:56+0900
本日の ABC。１時間かけて ABCD の４完で、残り40分考えて E 問題が解けずに終わった。ゲーム問題苦手。勝ち筋とか必勝法とか、さっぱり見えない。「自分はこの、先攻後攻が決まった瞬間に勝ち負けが見えるゲームを、きっと楽しくプレイできるんだろうなあ。」
本番中に E 問題が行き詰まっている最中に F 問題をタイトルだけチラ見していた。Coprime の単語が見えた瞬間にあきらめた。別の問題だけど先々月に「Coprime はまた解けなかった。」 完全に苦手意識を持っている。素数とか見たくない。
割と大きめのサンプル３が通ったのでいけると思ったが TLE だった。
考えたことを順番に。
このとき(緑diff精進３問)解いた問題の１つが「ABC 115 D - Christmas」なんだけど、素直に問題の通りに書いた最初の版が明らかに TLE を免れなくて、ださいけど if を使って２回の再帰呼び出しを１回に節約するパスを追加することで AC になっていた。
倍倍ゲームになりうる再帰構造には特別な警戒が必要だということと、それが反転したときに改善効果が劇的だということを学んでいた。今回も最後の lambda F に２行追加して AC。
たぶんグループの作り方が間違っていた。二次ペア三次ペアと芋づる式に相互グループを作るのでなく、それぞれの数ごとに一次ペアのグループを作って、そのサイズでクラス分けをすれば、計算で答えが求まったのではないか。計算の材料にする数字が誤っていたから求まらなかったのではないか。いやでもそのクラスには公倍数の情報が抜けてるのか……。
組み合わせた結果をフィルタリングするよりも、フィルタリングした結果を組み合わせるべきだったのではないか。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|
というような発見があった。ものがよく見えていないと「新発見」が多い。ユークリッドの互除法まで見つけてしまった。開拓者か研究者に向いているのではないか。
最終更新: 2021-03-24T16:47+0900
解いたあとで他の人の Ruby での解答を見たらバリエーションがいくつか見られた。
これが一番多かったと思う。公式解説に書かれている通りの手順。
これは Ruby で最速の qib さんの提出 #20369253 (191 ms) の解法。
公式解説にはこう書かれている。
マス i と j の距離を d(i,j) として，マス i の色は d(1,i) ≦ d(N,i) ならば黒，そうでなければ白となる．結論としてマス 1 とマス N の 2 点から幅優先探索や深さ優先探索などを行うことで O(N) でこの問題を解くことが可能である．
解法１はたしかに解説通りの手順ではあるが、解答にあたり具体的な距離まで知りたいわけではなく、距離の大小関係だけ知れれば十分なのだ。
解法２の手順は(スタート地点からの距離を測定する)幅優先探索に則っているのだが、一見すると１手につき１マスしか塗れないゲームのルールに反しているように見えるのが難しい。同じことは解法１にも言えて、「マス i の色は d(1,i) ≦ d(N,i) ならば黒，そうでなければ白となる
」が納得できるかどうかに尽きるのだけど、解法２の手順がなまじゲームに似ているせいで考えてしまう。
フェネックとすぬけくんの行動原理として想定したのは公式解説のものと同じ。見立てだけが異なる。どういう見立てだったか。
フェネック(すぬけくんでもいいが便宜上フェネックを選ぶ)のスタート地点を木の根と定めて、すぬけくんのスタート地点の深さを知る。すぬけくんは移動可能範囲を広げるために根に向かって移動する。フェネックはすぬけくんの移動可能範囲を狭めるためにすぬけくんに向かって移動する。出会うのは中間の深さ。すぬけくんは根に向かって移動できなくなった地点を根としてその子孫ノードだけを塗ることができる(だから一直線に根(フェネックのスタート地点)を目指していた)。
結局のところこの問題は一本の辺を見つけ出す問題だった。頂点集合をフェネック側、すぬけくん側に分ける辺がどれかを見つける問題だった。
その手順として幅優先探索(解法１)とその応用(解法２)と深さ優先探索(解法３)とダイクストラ法(未紹介)と、いろいろな方法があって、実行速度の差があった。同じ線形時間でも１回なめるだけで済ませられるのか、２回か、３回か。
今日@2021-03-23 たまたま取り組んだこの問題が同じ方針で解けそうだった。
２地点から深さ優先探索で陣取りをしていって、中央付近でにらみ合って、それからどれだけ相手陣へ侵攻(自陣へ後退)できるかを数えれば答えになりそうだった。
きっちりと隙を見せない after_contest に撃ち落とされましたとさ。
競技プログラミングをするフレンズ @kyopro_friends
サーバル「ABC148F『Playing tag on tree』にafter_contestを追加したよ！ 不等式に等号を入れるか入れないかを間違ってるコードが落ちるようになったはずだから確認してみてね」https://t.co/jcHP4lHFhg
不等号などなかった。先攻後攻を入れ替えたのと、自陣へ逃げ込もうとしてうっかり中立地帯へ迷い込まないように道を塞いだ。
当初方針のまま after_contest に対応したが、どうにも不自然に頑張ったようなコードになってしまった。この問題に関しては、想定解法通りに２通りの距離表を見比べて答えを選び出すのが良かっただろう。
ところで ABC148 はオンタイムで参加していた。A-D まで灰 diff で、E 問題に至ってもギリギリ緑という低難度回。F 問題でやっと水 diff 中位だったらしい。当時１時間を残していながら解けなかったのがこの F 問題。何を考えて解けなかったか。
木の上で追いかけっこをする２人がすれ違うことができない、ということが認識できていなかった。だから偶奇が適切な部分木を選んで逃げ込むことで追跡が躱せるような気がしていた。それじゃあこの但し書きが嘘になるのにね。「なお、ゲームは必ず終了することが証明できます。
」 そんなん考えたら青 diff 上位の「DFS Game」より難しくなるってのにね。