(A-1)/B+1 と書いたけど、だったら (A+B-1)/B と素直に書けばいいと思う。負数の整数除算は 0 に近づく言語と負の無限大に近づく言語があって、Ruby の場合はたとえば (-1)/2 が -1 になる。わざわざ括弧を付けたのは、たとえば 0-1/2 が 0 になるからで、負号がリテラルの一部(もしくは単項マイナス)であることを明確にするため。めんどくさ。■B 問題「Find snuke」。いまもって分からないこの条件文「A1,A2,A3,A4,A5 の中心はこの順に一直線上に等間隔で並んでいる」。中心ってどこ？ さておき、単にグリッドを全探索する問題なのだけどどこではまったのか。次の文字を探索するときに方向を固定するのを忘れていてジグザグに探索してしまっていた。それで答えがいくつも出てきて困っていた。さらには WA も出してしまって、そこから６分で別バージョンの解答を書き上げて AC を得た。つまり６分で解けたはずだよねってこと。コンテスト終了直後に WA 提出を眺めていてバグを見つけたので出し直して AC にしておいた。８方向の遷移先のうち１つがずれていたのが原因。'snuke' の各文字に対応したクロージャをチェインして出力に繋げる実装ってちょっとおもしろくないですか？ Array#inject メソッドがはまりすぎ(なので WA のままにしておけなかった)。■C 問題「Almost Equal」。制約がごく小さいので愚直に並べ替えて愚直に比較して答えを出した。■D 問題「Impartial Gift」。D は DP の D……ではない！ 差が一定以下で和が最大になるものだから、条件を満たす A の要素のうち最大のものと条件を満たす B の要素のうち最大のものを見つけて、いい方を答えにすれば良い。条件とは、現在見ている要素を a として、a-D から a の範囲の値が他方の数列に見つかること。■E 問題「Isolation」。UnionFind だと辺の削除はできないんだよね。注目するところは、辺の数はクエリの数を超えないということ。集合(Hash)で個々の辺を管理して許される。あとは辺の数が０と１のあいだで変化するのを掴まえて孤立頂点の数を管理する(変数名の o は orphan の o だよ。次数０の o でもあるかな)。サンプルの２が優しくて(「
2 番目の種類のクエリを行う直前の時点で、すでにその頂点と他の頂点を結ぶ辺が 1 本も存在しないこともあります」)、ペナルティを食う前にすぐ修正して提出したよね。いや、それでもペナルティは食らったんだった>WA。一度は書いた
E[a].clear がいつの間にか消えていたのが原因。■G 問題「Sort from 1 to 4」。もっと難しい類題を解いたことがある>ARC124-D「Yet Another Sorting Problem」(20211125)。あるいは UTPC2021-A「Make UTPC」(20220511)。今日の問題では、１から４の場所に納まるべき１から４の値の列が与えられる。ソートすればどの範囲が１の場所でどの範囲が２の場所か……ということがわかる。位置と値が一致しているなら交換は不要。１回のスワップでお互いの位置が正しくなるペアがあるならスワップして損はない。次は位置を交換している３つ組を見つけて２回のスワップで位置を正す。ここまで実装してあとはどうしようかと作業配列をインスペクトしながらサンプルを実行していたら、サンプルの２が神だった。残りは４つ組だけしかありえないので不一致の数を合計して÷４×３で OK。■F 問題「Merge Set」。名前からするとマージテクとかマージソートでうまくする問題かなと思うけど、うまい道筋をまだ見つけられていない。(ツイートを読んで書くんだけど) BFS も考えたけど隣接頂点リストが膨大になりそうで諦めた。ひょっとしてあなた(私です) M 個の値を頂点にしようとしていませんでしたか？■B 問題。今理解した。「5 つのマスの組 (A1,A2,A3,A4,A5)」という自己紹介がちゃんとあった。A よ、お前マスだったのか。■G 問題。「@kyopro_friends なるほど。書き方的に一般に成り立つように見えたので、例えば数が 6 種類あると上手く行きませんというのを伝えたかったです。」 うーん、わかりませんねえ。位置を正す方法(経路)に複数の選択肢があって、貪欲法では良くない経路を残してしまうのかなと思ったけど、そういうケースが作れないのと、そういうときにどういう方法がとれるのか。