脳log[20220918]

2022年09月18日 (日) [AtCoder] 昨日あった UNICORNプログラミングコンテスト2022(AtCoder Beginner Contest 269) のふりかえり(精進でも復習でもなく)。コンテスト成績証 - AtCoder。自分のすべての提出。AC までの所要時間は A=１分半、B=４分、C=４分、D=16分、E=19分、F=40分。30分６完なら黄パフォもあったみたいだけど、自分は１時間半かかりました。E は取りかかるまでに数分考えたし、F は考えながら実装して詰まって考えて実装再開してまた詰まって飛ばした E 問題をチラ見してひらめいて完成させるまでに思いのほか時間がかかっていた。■A 問題「Anyway Takahashi」。自分の提出言語で入出力と四則演算ができますかという問題。参加賞。謎の Takahashi 推しだと思ったら(今日になって見た)問題名が自覚的だった。■B 問題「Rectangle Detection」。配列やループが使えますかという問題。どうとでも書くことができてかえって方向性を定めにくいかもね。B 問題を解くのに短く書くとか効率良く解くとかは邪念と変わらない。■C 問題「Submask」。ビット列の部分集合を列挙する問題。昇順で答えるところを見逃してはいけない。何桁目のビットが立っているかを列挙して、０個選ぶ組み合わせ、１個選ぶ組み合わせ、２個選ぶ組み合わせ……を考えるのが正攻法。いや違う。入力に１のビットが k 個あったとして 0 から (2^k)-1 まで繰り返すのが一番しっくりくる。昇順に答えが見つかるので順番に出力していける。この方法はつまり、入力から０のビットを取り除いて１のビットだけで 0/1 の２択を k 個組み合わせ(2^k 通り)、答えるときに取り除いた０のビットを再度補っていると考えられる。ちなみに知っていれば０のビットを取り除いたり補ったりする手間をかけずにそのままビット演算で列挙できる。この場合は降順に答えが得られるので逆順で答える。蟻本と典型90問で取り上げられているので知っている人は知っている。■D 問題「Do use hexagon grid」(茶 diff)。ハニカムグリッド上で UnionFind をやる問題。６個の隣接ノードが問題文に書いてあるので、文字通りにやるだけ。……なんだけど、考える前に手が動く性分なのでノードや辺がうまく見えなくて UnionFind が書けなかった。座標平面を１列に延ばしておよそ４メガの点列を探索した。←の提出は他の提出に比べて桁違いに遅かったので、方針は同じながら効率に配慮したものを再提出した(314 ms → 67 ms)。■F 問題「Numbered Checker」(ぎりぎり青 diff)。だいたいいつも E 問題と F 問題は同時に開いて、F 問題を先に読んでパッとは解けないことを確認してから E 問題に取りかかるんだけど、昨日の F 問題はあからさまに簡単だったのでそのまま取りかかった。チェス盤に連番が書かれていてクエリで指定された矩形領域の白マスに書かれた数字の和をおおよそ定数時間で求める問題。連番でも１つ飛ばしでも式は等差級数の式で変わらない。Wikipedia で「等差数列」を開いて２種類の式の使いやすい方を写すだけ。……だと思ったんだけど１行目の和を求めたあとで３行目５行目を含めた和を一括で求めるのに詰まってしまった。自分はこんなあからさまに単純な法則で増加する数字をまとめて数えることもできないのかと不甲斐ない思いをしたよね。各行先頭の白マスを見比べて 2M ずつ増えているなと数列の和の式を２階建てで適用したら、サンプル１に含まれる６つのクエリのうち最後の１つ以外は正解した。え、なんで１つだけ合わないとかそんな中途半端がありえるの？ E 問題を読んだのはこのタイミング。「インタラクティブ」の文字が目に入るやそっ閉じした。インタラクティブ問題は、問題形式そのものの難しさゆえか解くべき問題は易しめに手加減されていると感じることが多いんだけど(実際 E 問題だけど緑 diff だった)、やっぱり問題形式に難しさがある。初めての人が標準ライブラリの入出力がバッファされていることフラッシュの必要があることを理解できなくて TLE になるのは通過儀礼。そこを抜けてもデバッグに手間がかかる。昨日の E 問題は返すべき答えを人間が用意するのに難しさはないからまだましだけど、デバッグのためにサーバープログラムを書くとなると時間がかかる。F 問題の方が早く解けそうだった。結局３行目５行目は 2M×列数 の割合で増えていたのだった。■E 問題「Last Rook」(緑 diff)。N×N のチェス盤に N 個目のルークを置く問題。ルークは飛車。どちらがわかりやすいかどっちもわからないか。矩形を指定してクエリできるので、領域を４つに分けながら絞っていくのかと最初は考えた。行と列が入り乱れて死ぬ未来しか見えない。最小２×２の盤面でクエリをシミュレートしてみたら、結局縦と横で２回のクエリが必要になるのであって、１つのクエリで盤面を４分の１に限定できるわけではないことがわかった。縦と横で独立して調べるとして、２の10乗はいくつか(クエリ総数が20だから縦と横にそれぞれ10回しか使えない)。1024。２の10乗と10の３乗の対応は覚えておいて損はない。10ビット20ビット30ビットがキロメガギガに(ほぼ)対応する。サウザンドミリオンビリオンでもいいけどね。制約は１辺 1000 以下。制約からも方針の正しさが示唆されるのであとは実装するだけ。以前の日記に「二分探索を使った解法でかつて最も衝撃を受けたのは Vacant Seat というインタラクティブ問題に対する提出 #2057817 と #2064531 だった。bsearch メソッドから呼び出されるブロックの中でクエリを行っている。いやね、自分も提出 #7970588 の中で二分探索を使って答えを出してるんだけど、そのことと、対象となる具体的なソート列がないまま空中で二分探索を行う、順序はクエリで動的に決定するということの間に、どれだけの隔たりがあることか」と書いたくらいなので、今回は自分が bsearch メソッドの中でクエリを行うターンだと当然考えたのだけど、制約が１回のクエリの無駄も許さないと言っているので、ブラックボックスの Range#bsearch メソッドを信頼することができなかった。今回も二分探索を手書きした。提出前に気がついたけど、手書きした二分探索は複数バグっていた。■結果は 85 分でノーミス６完の青パフォ。まだかつての Highest に届かない。