(Div2)CodeforcesABC100が終わって3時間後に行われたCodeforces。いい子はとっくに寝てる時間ですが、大学生の特権と言わんばかりの夜更かしで参戦しました。教訓としては、「眠気がある状態でコンテストは参加するもんじゃない」1。個人的に初めて大きくレートを落としたコンテストになってしまいましたが、Dまでの解説はします。(例によって幾分見やすいHackMD版のリンクも貼って置きます。今回は数式も少ないので大差ないかも。(指紋)問題リンク概要あなたの目の前にはテンキー式のロックが掛かったドアがあり、手元にはその暗証番号を部分列(連続でなくてよい)として含む数列が書かれた紙がある。テンキーの一部には指紋がついている。指紋がついた数字は必ず暗証番号に使われており、暗証番号はそのようなものの中で最長のものであることが分かっている。このとき、暗証番号を正しい順番に出力せよ。紙の数列を順番に見ていって、暗証番号とマッチしたら出力するだけ。制約が非常に小さいので毎回全探索で十分間に合う。騎士たちの強さがpi、所持金がciで与えられる。騎士たちは他の騎士を殺すことで相手の所持金を手にすることができるが、自分より真に弱い(pが真に小さい)騎士しか殺せない。良心の呵責から、各騎士は高々k人しか他の騎士を殺すことはできない。このとき、各騎士について他の騎士を殺した後に所持しうる最大金額を出力せよ。解説ずいぶんと物騒な問題文だが、お察しの通り「円卓の騎士」がモチーフになっている。私は円卓の騎士の元ネタを知らないのでなんとも言えないが。それはさておき、やるべきことを簡潔にまとめると以下の通り。騎士のデータを強さについて昇順になるようソートする。弱い騎士から順に以下の操作を行う。自分の1つ前の騎士の所持金を配列(coinとする)に挿れて降順ソート。coinの長さがkになるまでpop_back()する。coinの総和を答えとして記録。10)ので、毎回ソートしても十分間に合う。上はあくまでも「強さが互いに固有(distinct)である」場合の方法であり、実際は「同じ強さの騎士が来たら一旦配列(stockとする)に記録して、真に強い騎士がきたらstockを全部coinに突っ込む」みたいな処理が必要になる。0;}下手な実装をすると絶対バグる、Codeforces恒例の実装系問題。私は苦手なタイプの問題だが、今回は幸いにもバグらなかった。慣れてきた感じがある。座標軸に平行な辺を持つ正方形Aと、座標軸と45度に交わる辺を持つ正方形Bが与えられる。正方形の辺上も内部として扱うとき、AとBが共有部分を持つか判定せよ。解説(未完)問題自体は至って簡潔なのだが、考えてみると結構難しい。1つでも頂点が一方の正方形内部にある場合は明らかにYES。Bの頂点がAの内部にあるかはgridの探索でもよくやる境界判定で簡単に出来るのだが、問題はもう一方。これは幾何問題ではたまに出てくるテクニック「座標回転」(造語)を行えば上手くいく。Y)は元のグラフを45度時計回りに回転させて原点中心に拡大したものになる」というテクニック。回転行列を使えば簡単に証明できる。これを適用することで、Bが座標軸に直交するようになって先の境界判定をそのまま使えるようになる。解説(完全)しかし、未完とあったように先の方針では漏れがある。それが以下のようなケース2。これを網羅する方針で間違えたために、私はサーバージャッジで落とされた。すればこのようなケースを網羅できるかというと、答えは意外と簡単で「一方の中心が他方に含まれているか」を調べるだけ。解説見て「たったそんだけでいいのか......」と嘆くなどした。0;}残念ながら不正解だったが、経験は得られた。今度AtCoderにでも類題出ないかな。あと上のコードが汚いのはなんとかならないのか。(公開通信)問題リンク概要2人が1~9の数からなるペアを1つずつ持っており、2つのペアには1つだけ共通の数が含まれている。2人は自分のペアは知っているが相手のペアは知らない。この状況下で以下のような通信を交互に1回ずつ行い、共通の数を当てることが目標となる。一方がもう一方へ1~9の数からなるペアをいくつか伝える。ペアは異なる数字から成り、かつ同じものを含んではならない。伝えるペアの中には自分が持つペアが必ず含まれていなければならない。第三者であるあなたもこの通信だけを見て、2人と同様に共通の数を当てることが目標となる。共通の数は分からないが、どんなケースでも2人とも共通の数が分かっているなら0共通の数は分からず、1人でも共通の数が分かっていないケースがあれば-1を出力せよ。一目すると「何言ってんだこいつ」って感じの問題。要は論理パズルみたいなもので、眠気で支配された頭には堪えた。私の方針を説明すると、どちらか一方の視点に立ち、「もし自分がこのペアを持っているなら」と仮定する。相手についても「もし相手がこのペアを持っているなら」と全パターン仮定し、以下のように可能性を模索する。ペアの要素が2つとも違うor同じなら、相手がそのペアを持つ可能性はないのでスルーもしペアの要素が1つだけ一致するなら、その一致する数が「共通の数」となる可能性があるのでset(posとする)に突っ込む相手について全パターン模索し終わった時点で、posの要素数が0なら、自分がこのペアを持つことはないのでスルー。1なら、その要素が共通の数としてあり得るのでset(ansとする)に突っ込む。2なら、自分がそのペアを持っているケースについて自分は共通の数が分からないので、-1を出力して終わり以上を自分の伝えた全ペアに対して行った後、ansの要素数が0になることは条件から絶対にない。1ならそれが唯一「共通の数」になりうる数なので、それを出力。2以上なら、どのケースでも本人は「共通の数」を1つに絞れているはずなのに自分は分からないということで0を出力。これをそのまま実装してなんとかpretestまでは通ったのだが、案の定サーバーテストで落とされる始末。ちなみに一方からの視点だけから見ていたのがまずかった模様。両者の視点に立って考えてれば合ってたと思うと悲しいね。0;}コメントを書いてて「私がやっているのはプログラミングではなく論理学なのでは?」と思い始めた。説明がとても難しい......。感想A,Bは順調だったんだが、C,Dの全ケースに対応しきれず死亡。コーナーケースを考える練習が足りてないなぁと実感した。こどふぉは最後までコーナーケースがあるかどうかも分からないコンテスト形式なので、その能力は今後の大きな課題になりそう。紫から一歩遠ざかってしまった。今月は上の通りなんかいっぱいコンテストがあるっぽいので、巻き返すチャンスはある。次回からは十分に仮眠をとることを心がけよう。眠気がなかったら解けていたかというと、そうでもない気はする。↩この図はCSAのAppで簡単に作れます。046の解説(A~Dまで)。