x y、y x を検索すればいいと思う。横着して単一の文字列を対象にして検索するようにしたら 10 や 20 を 1 や 2 と見間違えるバグを仕込んで頭を悩ませていた。あほ。■C 問題「Dash」。書いてある通りに実装するだけなんだけど最初の提出は WA×1 だった。問題文の最後がこうなんだけど、「高橋君が一度も倒れることなく N 回の移動を行えるか判定してください」、N 回目(最後)の移動の１ステップ目を終えた時点で体力が尽きた場合の判定がそれほど明らかではない。「
最後の移動で体力が-1になった場合答えはYesとなりますか？」という質問と答えが全体公開されているくらいなので。自分はコーナーケースをうまく回避したつもりで N 回目の処理を特別扱いして WA×1 になっていた。ところで、WA×4 になる提出をいくつか見かけたけど、これは「
移動した点に置かれたアイテムを消費し」というのを読み落としていたものと思う。この点はちゃんと疑問を持って確かめていたので間違えなかった。■D 問題「Shift vs. CapsLock」。D は DP の D！ CapsLock が ON/OFF の状態それぞれの最小タイムを記録していく。たぶんないとは思ったけど制約上は許されていたので、Shift+A と CapsLock+A+CapsLock みたいな、結果が決まってそうなケースも一応比較した。■E 問題「A Gift From the Stars」。難しくはないと思う。迷って手が止まってえらく時間がかかったけど。まず次数１の葉っぱを見つける。その相手は星の中心に決まっている。星の中心の相手は葉っぱに決まっている。すでに見た葉っぱは無視して新しい葉っぱの相手を見る。それが自分(星の中心)なら無視して、そうでないものがあるならそれは別の星の葉っぱに決まっている。という感じで次々に判定していくだけのことに 40 分ちょっとかけてしまった。最終形は、星の中心をキューに入れるようにして星のレベルを記録していくものになった。■こちらの提出 #41744985 を見ると次数だけで答えが出せるみたい。次数１は葉っぱに決まってる。次数３以上は星の中心に決まってる。次数２は星の中心でも葉っぱでもありうるけど、全体を見ると星の中心と次数２の葉っぱの数の比率は n 対 2*(n-1) に決まってるので、って感じだろうか。ヒントなしでは気がつけないよ。■面白いことを書いている人がいる。「ABC303-D この問題の正解者は実は間違っていた」。形式だけ見て気が付いたことを。「別のとらえ方」として書かれている４ステップの処理について。１ステップ目は dp[0][j] と dp[1][j] に基づいて dp[0][j+1] に一時的な値を保存している。２ステップ目は同じようにして dp[1][j+1] に一時的な値を保存している。３ステップ目は dp[0][j+1] と dp[1][j+1] に保存した一時的な値に基づいて dp[0][j+1] に本式の値を記録している。４ステップ目は dp[0][j+1] に記録した本式の値と dp[1][j+1] に保存した一時的な値に基づいて dp[1][j+1] に、おそらく誤った値を記録している。これは自分が提出 #41747349 で５行目と７行目がどれだけ長くても１行の多重代入によって値の更新をしている理由だし、ときどきは見た目を整理したい邪悪な欲求に負けて代入を複数行に分けてバグらせてしまうのと同じことである。たぶんね。
問題３ あなたは現在の富に上乗せして一〇〇〇ドルもらったうえで、次のどちらかを選ぶように言われました。五〇％の確率で一〇〇〇ドルもらう、または確実に五〇〇ドルもらう。問題４ あなたは現在の富に上乗せして二〇〇〇ドルもらったうえで、次のどちらかを選ぶように言われました。五〇％の確率で一〇〇〇ドル失う。または確実に五〇〇ドル失う。」■２つの質問への答えを決めてから読み進めると書いてあったのは、「
たぶんあなたはたいていの人と同じように、次のような反応を示すだろう。問題３では大方の人が確実な方を選ぶ。問題４では大方の人がギャンブルを選ぶ。」「
あなたは選択を決める前に、問題３では一〇〇〇ドル、問題４では二〇〇〇ドルを「もらった」はずだが、そのことに十分注意を払っただろうか。たいていの人と同じなら、そんなことは気にも留めなかったはずだ。この「プレゼント」は参照点に含まれてしまい、参照点は無視されるのがふつうだからである。」「
またあなたは、損得に対する自分の態度が、富の状態の評価に必ずしも左右されないことも知っているだろう。一〇〇ドル得をするのが好きで一〇〇ドル損をするのが嫌いなのは、富の増減の問題ではなく、単に勝つのが好きで負けるのが嫌いだからである。そしてまずまちがいなくあなたは、勝つことを好む以上に負けることを嫌う。」■自分の答え。問題３ではダブルアップチャンス(ギャンブル)を選んだ。問題４では確実な損失を選んだ。どちらも想定の反対だ。どういう心理かというと、問題３ではすでに一〇〇〇ドルというあぶく銭を手に入れていて、ギャンブルを選んでもそれを取り上げられはしないので、追加でもらえなくてもその嬉しさは減らない。一方で確実に五〇〇ドルもらうよりも倍額の一〇〇〇ドルを確率でもらうギャンブルに勝つ方が喜びは大きい。問題４では、すでに二〇〇〇ドルという十分に大きなあぶく銭を手に入れているので、それが確実に五〇〇ドル減ることに痛みは感じない。感じない痛みを取り除くために失う額を倍にするかもしれないギャンブルに参加することは、痛みや悔しさを生み出すマイナスばかりが目立つ。■どうだろう。たぶん国民性みたいな傾向もあるんじゃないかな。自分の答えは日本人の標準だと信じている。だって完全に自分の利益と感情に従っていてこれ以外の答えは考えられないんだから。■とはいえ、得するチャンスを逃したことをあとから知って、本気で損をしたように感じたり、(そこに他者が関わっていたことで)損をさせられたと感じれば腹を立てたりする、自分と異なる考え方をする人が存在することも知っている。自分の感覚ではあると知ってすらいなかったプラスのチャンスを逃したことはただのゼロであり、そこに悔しさはない。事前に知って皮算用をしていたとしても、参加費がゼロならリターンがゼロでも惜しむ対象がない。でもそうは考えないやっかいな(説明ができない)人もいる。■いやまあ、説明だけならできる。本の同じ部分(97 ページ)に書いてある。「
金銭的結果の場合には、通常の参照点は現状すなわち手持ちの財産だが、期待する結果でもありうるし、自分に権利があると感じる結果でもありうる。たとえば、同僚が受け取ったボーナスの額が参照点になることは、大いにありうるだろう。」 参照点が異なっているだけなのだ。どうして参照点をそこに置いたの？ って疑問がやっぱり理解できずに残るわけだけど。
(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 種類あると上手く行きませんというのを伝えたかったです。」 うーん、わかりませんねえ。位置を正す方法(経路)に複数の選択肢があって、貪欲法では良くない経路を残してしまうのかなと思ったけど、そういうケースが作れないのと、そういうときにどういう方法がとれるのか。
この一連の操作のコストは（書き換えた要素の数によらず）2^k である。」「
kを使った場合のコストは、k-1以下のすべてを使ったコストより高い」)。自分は「わかる」のではなく「知っている」だけなのだ。最小値を求めるときに String#to_i を無引数で呼び出してしまって１ペナ。
調査してみると、経営者の決定がきちんと操車場に伝わっていなかった」)。それなのに最終的な解決方法が現実的ではあっても理想に届いていなかった(「
ささいな問題として……」)。数学者の興味をひくには、数学者の言であるとされる「
あなたの話は具体的でわかりにくい。もっとわかりやすく抽象的に説明してくれませんか？」がヒントになりそう。話が具体的すぎた。最後に、ペアを考えることで解けた競プロの問題を嬉しそうに挙げておきますよ。灘校文化祭コンテスト 2022 Day1-D「Double Permutations」(20220504)