/ 最近 .rdf 追記 編集 設定 本棚

脳log[20230415]



2023年04月15日 (土) トヨタ自動車プログラミングコンテスト2023#1(AtCoder Beginner Contest 298)があった。自分のすべての提出コンテスト成績証。C 問題に提出しようとして失敗したときにサーバーの異変に気が付いた。数分間リロードを繰り返しているうちに正常に戻ったのでそのまま続けた。C、D、E、F と AC を得て気楽な気分で G 問題を読んでいたのが終了 10 分前で、普段読まない質問ページを開いたのもこのとき。DDoS の影響で unrated だってさ! こんなに残念なことはない。俺が6完するのは珍しいんだぞ。今回は B 問題から重めの問題だったので振り返りも B から。■B 問題「Coloring Matrix」 問題文に書かれている回転の定義を読み解くのがまず難しい。2つの行列を照合する方法は2通りあって、Array#transpose と Array#reverse を組み合わせて行列自体を回転する方法と、添字を変換する方法。添字を変換する方法でやることにした。その方法だけど、90 度回転する変換と 180 度回転するものと 270 度回転するものをそれぞれ定義しようとして苦労して、(あまりに苦労したからどこかで間違えているに違いないと考えて)デバッグのために3行3列の変換結果を表示してみたけど、それが合っているかどうか読み解くのが自分には難しいということが明らかになった。問題文を読んで回転を脳内再構成することから難しいのだからそりゃそうだ。考えることをやめて「A_{i,j}​ を A_{N+1-j,i} で置き換える」という添字の変換をそのまま実装して2回3回と繰り返し適用することにした。AC まで 18 分。照合という語を使ったことについて補足。判定条件が論理パズルみたいでちょっと面白かったよね。A の要素が 1 のとき B の要素が 1 でなければいけない。ということは、A=0 のとき B は何でもいいし、逆に B=1 のとき A は何でもいい。A=1⇒B=1 (もしくは B=0⇒A=0) を確かめる式は A==0||B==1 になる。これって有名なパズルで、人間は未成年の飲酒を見つけるためならば確かめるべきを間違えないけど、ただの記号の組み合わせだとルール違反を見つけるのが途端に難しくなる。■C 問題「Cards Query Problem」 D 問題に出てもおかしくないような、下手を打つと TLE になりそうな制約と操作。あなたは std::set と std::multiset が使えますか、と問う問題かなと思うけど、Ruby にはない。カードごと箱ごとにソート済みの列と未ソートの列を1本ずつ持つことにした。答えを出力するタイミングで未ソートの列をソートしてマージする。出力する数の合計が 20 万以下に制約されているから、ソートする要素数も、マージ操作のコストも同じレベルに抑えられているはず。AC まで 28 分。方針を決めるまでにすこし考えたし、実装量もそこそこ多かった。実は実装に手間をかけなくても、1つの配列につっこんで出力の直前にソートするだけで十分だったっぽい。出力の総数が制約されているとはそういうことだよな。■D 問題「Writing a Numeral」 これは簡単。各桁の数字と全体の mod を記録していく。クエリ2で引き算をするために 10 の冪乗の余りも並行して記録していたけど、たぶん都度 pow メソッドを呼んでも大丈夫だった。■E 問題「Unfair Sugoroku」 確率の問題。確率とか期待値の問題って方針を決めるところに難しさがある。正解方針が引ければ答えが合うけど、答えにたどりつけない方針を引いてしまいがち。当てもんをやっている。「Boy or Girl paradox」とかモンティ・ホール問題とか、知らなければ避けられない、ヒトが傾向的に陥りやすい誤りがある。方針に迷って F 問題に手を付けるも一時退却してきたときにひらめいた正解方針がこう。高橋くんがサイコロを振って進んだ先のマスに場合の数を書き込みます。各回において高橋くんが初めてマス N に到達した場合の数と青木くんがマス N 以外のマスにいる場合の数から勝ちの確率を求めます。そうして各回で勝つ確率の総和が答え。制約が小さかったので愚直に配列をスキャンして数字を出したけど許された。助かる。■F 問題「Rook Score」 なんかやるだけに見えるけど、やや長めの制限時間3秒が気になる。たぶん想定される落とし穴は、0 以外の数字が書いてある N 個のマス (r,c) のどれかを答えの候補にして他を考えないことだと思う。しかし答えの候補は N 個の r と N 個の c の組み合わせから選ばなければいけない……ような気がする。しかし O(N^2) が許されない制約。どうする。貪欲にやって見込みがなくなったところで打ち切るようにしたら間に合った。それでいいのか?■「アライグマ「F問題は、行和+列和が大きい順にN+1個チェックすればいいのだ!」」 言われてみればそれはそう。そこまで見極められていなかったから、自分の提出(一応 AC)では貪欲さが足りなかったし、だから tinsep19 さんの提出 #40680322 のようにより厳しい打ち切り条件も採用できなかった。あと、セグメント木で解けるというツイートを2つ見たけどよくわからなかったので考えた。たとえば1行ずつ考えるとして、セグメント木には列ごとの合計値を記録する。行を移るときに同じ数字を二重に計上しないようにセグメント木上の数字を足し引き補正して、それから最大値を尋ねるのだと思う。ST でやったら WA×9 と微妙に間違えた。なぜ? ST クラスの内部配列のサイズを2べきに揃えるときに埋める値がよろしくなかった>AC。■ACL などまともなライブラリのセグメント木を使ったことがあれば単位元がパラメータ(の1つ)だということがわかったはずだ。この動画を見ていたら op と e の2つをテンプレートパラメータとして渡していて、「あっ、そうなんだ」とお勉強になりました。で、あらためて Wikipedia を読むと「定義……結合律…….単位元の存在……を満たすならば……モノイドという。」と書いてあるわけ。だけどね、痛い目を見るまではそういうお約束的な決まり事って無視しちゃうよね(イケナイ)。■これまでで 15 番目に良い順位だっただけに unrated の無念もひとしお。一入はありふれた漢字の組み合わせで難読。一目で覚えたい。