この一連の操作のコストは（書き換えた要素の数によらず）2^k である。」「
kを使った場合のコストは、k-1以下のすべてを使ったコストより高い」)。自分は「わかる」のではなく「知っている」だけなのだ。最小値を求めるときに String#to_i を無引数で呼び出してしまって１ペナ。
調査してみると、経営者の決定がきちんと操車場に伝わっていなかった」)。それなのに最終的な解決方法が現実的ではあっても理想に届いていなかった(「
ささいな問題として……」)。数学者の興味をひくには、数学者の言であるとされる「
あなたの話は具体的でわかりにくい。もっとわかりやすく抽象的に説明してくれませんか？」がヒントになりそう。話が具体的すぎた。最後に、ペアを考えることで解けた競プロの問題を嬉しそうに挙げておきますよ。灘校文化祭コンテスト 2022 Day1-D「Double Permutations」(20220504)
C:\Program Files\Ruby27 にインストールして、コマンドプロンプトで ABC300.rb27 とか ruby27 ABC300.rb27 で実行できるようにしている。■方法は？ ruby.exe の名前を ruby27.exe に変えるのはあまりうまくなさそうだし、ruby27.exe という名前のシンボリックリンクを他所に作っても x64-msvcrt-ruby270.dll みたいなライブラリにパスが通ってないと実行できないしで、~\Documents\PATH という名前のフォルダをパスの通ったフォルダとして用意して、ruby27.bat という名前のバッチファイルを置くようにしている。中身は次の２行だけ。@set PATH=C:\Program Files\Ruby27\bin;%PATH% @ruby %* 他にも ruby18.bat、ruby19.bat、ruby25.bat、ruby31.bat、irb27.bat、ruby27-prof.bat とかのファイルがある。Ruby-1.9 のあと AtCoder に触れるまで Ruby から離れていたことがわかりますね。原始的だけど面倒がない。■デスクトップに空の ABCxxx.rb27 ファイルを作成してサクラエディタで開いて、コマンドプロンプトも開いて準備完了。ブラウザとエディタとプロンプトを行ったり来たりしてる。あとアニメとかの動画をデスクトップいっぱいに最大化して再生してる。静かすぎるのも集中できないものらしいですよ。オートインデントだとか補完だとか整形だとか構文エラーの指摘だとか、機械に不随意に横から茶々を入れられるのが耐えられないのでエディタには多くを求めていない。■BIT とプライオリティキューとセグメント木と組み合わせの事前計算をイチから書くことはもうないので、そのときはエディタの GREP 機能(Ctrl+G)で過去ファイルを漁っている。プライオリティキューとセグメント木にはバグったものが混じっているのがわかっていて、うっかりしていると過去のバグを再現してしまう。■コードテスト勢(実在をやや疑っている)よりはよく準備してると思う。言語リファレンスはここ☞。できることは全部リファレンスに書いてある。専ら Array#insert の第一引数と第二引数のどっちがどっちだったかと、ビット演算子の優先順位を確認するのに使っている。他に競プロで使うようなものはだいたい覚えてるかな。Ruby だけだからね。C++ で書こうとすると cpprefjp が手放せない。■こういうお役立ち記事があるのは知っている。「RubyプログラマがAtCoderの環境をatcoder-cliとonline-judge-toolsで快適にしてみた - Qiita」。使われているのはどれも有名どころのコマンドで、AtCoder に限らず使う機会が多くあると思う。参考にしてまったく損はない。だからそうでない原始人スタイルもあることを書いた。. である」という内容だった。理由はわかる。さもなければそれはより大きいばってんとして数えられるべきだからだ。でも本文中に「バツ印を構成するマス以外に # は書かれていません」「異なるバツ印を構成するマス同士は頂点を共有しません」という条件が書かれている。そうすると結局判定条件としては「少なくとも１つは .」だけど、実際に入力されるものは「４つとも . になっている」ということだ。別にそれで問題はない。ないんだけど、全体として過不足なく丁度になっていないことで考え漏らしがあるかと疑念が生じて考えてしまった。あとは「頂点」ってなんだ？とか。具体例を読めばグリッドの十字部分らしいとはわかるけど、推測ですよ。解答は X 字の右上がりでも右下がりでもいいので端点を見つけて長さを計る。ちなみに最初に考えた解法は UnionFind を使うもので、問題文を読むときも UnionFind が使えるかどうかを確かめながら読んでいた。でも判定が簡単そうだったので UnionFind は書かないで済ませた。■D 問題「AABCC」。来たよ、苦手な苦手な D 問題、数学(素数)、緑 diff(予想)。数字と友達になれないと TLE になるやつ。解けなかった ABC296-D「M<=ab」の反省から N の平方根の範囲で何かする制約だとはすぐに読み取った(この前はそれすらできなかった)。あとはやや長めの３秒制限を信じて打ち切りながら全列挙した。自分の提出は Ruby の中でも一番遅い部類。苦手なんだよ。■E 問題「Dice Product 3」。確率の問題。Ruby による他の提出を見ると一番早い提出がたぶんメモ化再帰で自分のと全然違っていた。自分の解法。まず、N が２と３と５の積に分解できなければいけないので因数を数える。４と６の目はひとまず無視して２と３を数える。１の目は最初からないものとして５面ダイスで問題を解く。その場足踏みはサイコロを振らなかったのと同じことなので。N が２と３と５に分解できたら６の目と４の目の数を決め打つ総当たりで、ダイスの目の並べ方を組み合わせで求めて確率を出す。解答の C 関数の定義がやや不自然だった。引数を n と rs から rs だけにして n は rs.sum で求めることにすると無駄がなかった。■F 問題「More Holidays」。解けなかったのでこれは精進。方針は、１つの x で区切られた長さ 0 以上の o の連続を、K 回連結することを考える。K はべらぼうに大きな数になりうるけど、仮に入力 S に含まれる x の個数が X 個だとしたら K/X と K%X を使ってうまく数える。罠がいくつかある。どの o の連続から数え始めるかを全探索するのだけど、後ろの方から数え始めて K 回連結したときにうっかり T の長さ NM を超えてしまわないこと。まだある。入力の先頭と末尾が o の文字で、操作回数 K が x の個数の倍数で、繰り返し回数 M が十分に大きいとき、末尾と先頭にある o の連続を一体で扱わなければいけない。」という添字の変換をそのまま実装して２回３回と繰り返し適用することにした。AC まで 18 分。照合という語を使ったことについて補足。判定条件が論理パズルみたいでちょっと面白かったよね。A の要素が 1 のとき B の要素が 1 でなければいけない。ということは、A=0 のとき B は何でもいいし、逆に B=1 のとき A は何でもいい。A=1⇒B=1 (もしくは B=0⇒A=0) を確かめる式はA_{i,j} をA_{N+1-j,i}で置き換える
A==0||B==1 になる。これって有名なパズルで、人間は未成年の飲酒を見つけるためならば確かめるべきを間違えないけど、ただの記号の組み合わせだとルール違反を見つけるのが途端に難しくなる。■C 問題「Cards Query Problem」 D 問題に出てもおかしくないような、下手を打つと TLE になりそうな制約と操作。あなたは std::set と std::multiset が使えますか、と問う問題かなと思うけど、Ruby にはない。カードごと箱ごとにソート済みの列と未ソートの列を１本ずつ持つことにした。答えを出力するタイミングで未ソートの列をソートしてマージする。出力する数の合計が 20 万以下に制約されているから、ソートする要素数も、マージ操作のコストも同じレベルに抑えられているはず。AC まで 28 分。方針を決めるまでにすこし考えたし、実装量もそこそこ多かった。実は実装に手間をかけなくても、１つの配列につっこんで出力の直前にソートするだけで十分だったっぽい。出力の総数が制約されているとはそういうことだよな。■D 問題「Writing a Numeral」 これは簡単。各桁の数字と全体の mod を記録していく。クエリ２で引き算をするために 10 の冪乗の余りも並行して記録していたけど、たぶん都度 pow メソッドを呼んでも大丈夫だった。■E 問題「Unfair Sugoroku」 確率の問題。確率とか期待値の問題って方針を決めるところに難しさがある。正解方針が引ければ答えが合うけど、答えにたどりつけない方針を引いてしまいがち。当てもんをやっている。「Boy or Girl paradox」とかモンティ・ホール問題とか、知らなければ避けられない、ヒトが傾向的に陥りやすい誤りがある。方針に迷って F 問題に手を付けるも一時退却してきたときにひらめいた正解方針がこう。高橋くんがサイコロを振って進んだ先のマスに場合の数を書き込みます。各回において高橋くんが初めてマス N に到達した場合の数と青木くんがマス N 以外のマスにいる場合の数から勝ちの確率を求めます。そうして各回で勝つ確率の総和が答え。制約が小さかったので愚直に配列をスキャンして数字を出したけど許された。助かる。■F 問題「Rook Score」 なんかやるだけに見えるけど、やや長めの制限時間３秒が気になる。たぶん想定される落とし穴は、0 以外の数字が書いてある N 個のマス (r,c) のどれかを答えの候補にして他を考えないことだと思う。しかし答えの候補は N 個の r と N 個の c の組み合わせから選ばなければいけない……ような気がする。しかし O(N^2) が許されない制約。どうする。貪欲にやって見込みがなくなったところで打ち切るようにしたら間に合った。それでいいのか？■「アライグマ「F問題は、行和＋列和が大きい順にN+1個チェックすればいいのだ！」」 言われてみればそれはそう。そこまで見極められていなかったから、自分の提出(一応 AC)では貪欲さが足りなかったし、だから tinsep19 さんの提出 #40680322 のようにより厳しい打ち切り条件も採用できなかった。あと、セグメント木で解けるというツイートを２つ見たけどよくわからなかったので考えた。たとえば１行ずつ考えるとして、セグメント木には列ごとの合計値を記録する。行を移るときに同じ数字を二重に計上しないようにセグメント木上の数字を足し引き補正して、それから最大値を尋ねるのだと思う。ST でやったら WA×9 と微妙に間違えた。なぜ？ ST クラスの内部配列のサイズを２べきに揃えるときに埋める値がよろしくなかった>AC。■ACL などまともなライブラリのセグメント木を使ったことがあれば単位元がパラメータ(の１つ)だということがわかったはずだ。この動画を見ていたら op と e の２つをテンプレートパラメータとして渡していて、「あっ、そうなんだ」とお勉強になりました。で、あらためて Wikipedia を読むと「定義……結合律…….単位元の存在……を満たすならば……モノイドという。」と書いてあるわけ。だけどね、痛い目を見るまではそういうお約束的な決まり事って無視しちゃうよね(イケナイ)。■これまでで 15 番目に良い順位だっただけに unrated の無念もひとしお。一入はありふれた漢字の組み合わせで難読。一目で覚えたい。