はじめに
JOI本選で178点、Bランクだった。春合宿には落ちてしまった。
オープンコンテストがあるのでネタバレを見ずにそれを解いて、気分だけでも春合宿参加者に負けないようにしていく。できれば点数で春合宿erに勝っていきたい。
オープンコンテスト
1日目
試験(Examination)
を満たす
の個数を各クエリ毎に
を変えながら数え上げる問題。
問題文を読んで、まずは小課題1を解く。これはで二重ループを回すだけで解ける。2点。 高速化をすればこれで100点を取れてしまうらしい(後で試してみたら2.5msで通すことができた)けど、流石に本番にそれをやる余裕はなかった。
小課題2はが必ず0になる。成績とクエリを数学の点数の順に昇順ソートすると1つ目の式が消える。2つ目の式は座標圧縮+BITでよくあるやつをすれば解ける。ここまでで40分
満点解法ではその上で3つ目の式に対応できるようにどうにかしなければいけない。しかしこれは割と簡単で、BITの上に個数を載せていたのをやめて、代わりにBITの各要素をsetにしてを追加、取得クエリではsetの要素内で
以上のものの個数を数え上げればよい。setでは最後の部分ができないので平衡二分探索木を使うなりさらに座圧+BITをするなり、をすれば解ける。ここまでで1時間。
かなり上手く考察が進んだと思っていたのだが、春合宿会場ではこの問題の満点解法を13人が通していたらしい。恐ろしい。 自分が解けていること、正答者数が多い事から難易度11はなさそうで、BITの上にさらに何かを載せるという部分が難しいので難易度9でもなさそうだと感じた。
ナン(Naan)
有理数の上でケーキ分割問題を解くもの、らしい。本番ではケーキ分割問題の存在自体を知らなかった。
とりあえず小課題1を解く。の場合、右から1人目、2人目の順番に取るか、2人目、1人目の順番に取るしかないので、両方のケースを調べる。
各人物毎に公平な分配だと感じる最大の幸福度が決まっていて、それより大きな幸福度が与えられるような大きさのナンを貰っても意味がない事に気づくと、切られたナンを取る人の順番を決めた時の最適な切り方と公平な分配が可能かどうかがわかる。これを実装して5点。
これが分かると小課題2も階乗でのパターン全列挙で解ける事がわかり、やると合計29点が貰える。bitDPをすればもう少し人数が多くても対応できそうな気がするが、残念ながらそのような制約を持つ小課題はなかった。
少し休憩を挟んでいた事もあるが、これだけで実装に2時間以上を費やしてしまった。とても悲しい。 本番で100点を取れた人はいなかったようなので、どうやらこの問題の配点は29点らしい事が分かった。
難易度12だと思うのだけれど、典型といえば典型のようなので難しい。難易度12のマージテク問題が今となっては(難易度12の中では)かなり楽な方に分類されるように、15年後のJOI勢はこのような問題も典型問題として簡単に解けるようになっているのかもしれない。
ビーバーの会合(Meetings)
3点を指定するとその3点からの移動距離が最小になるような頂点の番号が返ってくるため、クエリ回数を一定以下に抑えながら木の構造を復元する問題。
この時点で残り時間が30分を切っている。何もわからないため、とりあえず小課題1だけを解く事にする。
頂点数が極端に少ないため、回クエリを実行して頂点番号を保存、ありえる木を全列挙して、それぞれシミュレーションする事にする。
流石に個程度の辺それぞれに対して張るか張らないかを決めたらTLEを起こしてしまうため、木である事を使っていい感じにすると間に合う。実装は間に合わなかった。
0点だった。もし時間が十分に残っていたとしてもほんの少しの部分点しか取れなかったと思う。反省。
春合宿参加者の中でも0点の人は1人しかいなかったらしい。大失敗をしてしまった。何も分からなかったので難易度12だと思う。
まとめ
100+29+0=129点。1問目が解けたため良い点数にはなったと思うのだが、上手くやればあと数点は稼げたのではないかという気分になってしまう。
もし春合宿に参加していればおそらく得点で8位〜12位辺りに位置していると思うのだが、残念ながら春合宿には参加できていない。
2日目
ふたつのアンテナ(Two Antennas)
もう片方との距離が一定以上かつ一定以下なら通信できるアンテナが一定間隔に並んでいて、区間クエリが与えられるので区間内の双方向に通信できるアンテナの中で高さの差が最大なものを答える問題。
小課題1を見る。で解いてもいい事がわかり、これは前計算を何もしなくてもクエリ毎にその区間内のアンテナの組を全探索すればよい事がわかり、解ける。
小課題2を見る。全てのアンテナの組に対して、その2つが双方向に通信できるかどうか、通信できるならその高さの差(ここではスコアと呼ぶ事にする)をあらかじめメモする事ができる事がわかる。
求めたい物は にあるアンテナの組の持つスコアの最大値 なので、よくある区間DPをする事でこれを解く事ができる。
小課題3を見る。クエリが1つで、区間が全範囲を指している。
地点を左から順番に見ていく事を考える。ある地点が(片方向に)通信する事ができる区間のは右と左に2つあるが、右側のものだけを考える事にする。
そうするとSegtreeの区間取得クエリが丁度適用できるようになる。絶対値の最大値を計算するので難しいように見えるが、区間minを持つSegtreeと区間maxを持つSegtreeを両方用意してしまえばよい。
このままでは右側片方向の通信にしか適用できないが、地点の区間になるので、Segtreeに対して
の取得が始まる前タイミングで要素追加、
の取得が終わった後のタイミングで要素削除をするようにすれば双方向に通信する事ができ、これで解ける。
初日の1問目と似た雰囲気を感じる、よい問題だった気がする。取れる部分点は全て取って、満点解法を諦めて他の問題に移るタイミングも適切でよかったと思う。春合宿の会場で同じ得点を取った参加者がかなり多かったはずで、おそらく難易度は12な気がする。
ふたつの料理(Two Dishes)
問題概要の説明をする必要がわからなくなってきたので、読んで。
小課題1はボーナスの値が正である事が保証されていて、ボーナスを得る事ができる境界の時間が全て一定になっている。
まずはかかる時間と得ることができる得点を累積和で保存しておく。
Naanの小課題1と同じように、カレーを先に作るか丼を先に作るかを決めたり、決め打ちをしながら累積和と二分探索を組み合わせたりする事で解ける。適当だが、これで5点を取る事ができた。
小課題3を考える。でDPをするような見た目をしていて、また、達成したカレーの工程の個数と達成した丼の工程の個数からかかる時間がすぐに求まる事を考えると、累積和と組み合わせてよくあるDPをする事で解く事ができる。小課題2もこれが解ければ自動的に通るため、追加で10点。
実装を手早く済ませた上で自明な部分点を取る事ができたのはかなりよい動きだったと思う。満点が出ておらず、この問題もすぐ諦める事ができたのはかなり良かった。難易度はほぼ間違いなく12。
ふたつの交通機関(Two Transportations)
グラフが2つ与えられるので、2つを合体させたグラフの都市間の最短距離を求めよ。
独立なソースファイルを2つ用意し、その2つ間のやりとりはbool、なおかつやりとりの回数を一定回数以内に抑えなければいけない、間違ってもAtCoderには出せないとても面白い形式の問題。
小課題1を考える。これは与えられるグラフが1つなので、ダイクストラをするだけで解ける。答えの出力をできる関数がA側、グラフが与えられるのがB側なため、求めた最短距離を2進数に変換して送る必要がある。最悪ケースで距離を30bit管理すると落ちるので注意する。6点。
小課題2を考える。B側にある全ての辺の情報をA側に送信すればよいので、それをする。B側の辺の数が、辺の情報は頂点
つとコストがあるが、頂点情報には
bit、コストには
bit、合計すると
で、クエリ制限は
回なので、これで8点を取る事ができる。
小課題3を考える。合体させたグラフが連結である事が保証されているので、これは木になる。
B側の辺のみを考えるとこれは自明に森になるので、あらかじめDFSをしておいてのようにすれば、A側に伝える時に必要な頂点情報の数は
個に抑える事ができ、小課題3が解けた。
小課題4以降を考える。まず、辺情報そのものを送るのではなくAとBのそれぞれでダイクストラをして、その結果をマージする事を考える。
そのままダイクストラをすると当然正しい結果が得られないので、「まだ確定していない頂点の中で、都市0との距離が距離が最も短い頂点」を考える。AとBからこの情報を取得し、そのうちの短い方を取り出す操作を回繰り返す事で、通常のダイクストラと同様に解く事ができる。
回の操作1回につき、距離情報に
bit、頂点番号情報に
bit、それをABそれぞれに対して行うので合計で
回のクエリが必要となる。
ならこれで解く事ができ、ここまでで38点を得られた。
ダイクストラの最短距離の更新に着目すると、前回の更新地点と今回の更新地点の距離の差はたかだか500以下になる事がわかる。そのため、その分の値を減らすことでbitかかっていたものを
bitに減らす事ができ、小課題6までを解く事ができる(本来
bitでよい部分を
bit取ると小課題6が通らなくなってしまうため、注意する)
ここまでをコンテスト中に考察して84点を得る事ができた。満点解法では、距離情報を送信した後に距離を比較し、距離が長い方からは頂点番号を送信しないという方法を取る。距離が短い頂点の情報だけ更新してしまえば、確定しなかった方の頂点の情報は更新をしなくていいというのが理由になる。
これをする事で、各クエリ毎にbit減らす事ができ、満点を得る事ができる。
あまり得意なタイプの問題ではない印象だったが、無事84点を取る事ができてよかった。残りの16点についても本当にもう少しという所だったので、このような所を詰める事ができたらよいと思った。
難易度はだいたい10ぐらいだと思っているのだけれど、正答者数がかなり少ない気がする。
まとめ
35 + 15 + 84 = 134点。かなりの成功だったと思う。コンテスト終了直後は成功したのか失敗したのか分からない程度の印象だったが、他の参加者の点数分布を見た限りだと、どの問題も通すべき課題は全て通し、問題3については100点こそ得られなかったものの、なかなかの高得点を得る事ができたと感じた。
春合宿参加者全体の順位で見ても、これだけ取れていれば1桁順位はほぼ確実なのではないかと思った。今後もこのようなパフォーマンスを取っていきたい。
3日目
指定都市(Designated Cities)
問題概要は省略。
小課題1について考える。これは頂点の部分集合全てに対してその集合内の頂点全てを特別都市に指定した場合の答えを保存し、popcount毎に分類しておく事で解く事ができる。ほぼ自明枠。
小課題2について考える。まず与えられた木を適当な頂点を根とした根付き木とする。根の頂点のみを指定した場合、根から子の方に向かう辺のコストの総和が答えになる。
根の頂点以外を指定した場合について、選んだ頂点と根を結ぶパス上の頂点について、コストの値が根を選んだ場合と逆になる。そのため、根から選んだ頂点とのパスに含まれるコストの値を使って適当に計算して、木DPをすると解ける。
小課題3について考える。小課題2の時と同様に木DPをして片方の頂点を選び、もう片方の頂点とのパスに含まれる重みの総和の分だけさらにコストを減らす事ができ、それを実装すると点数が貰えるような気がしたが実装をする事ができなかった。
小課題4以降は全く分からなかった。小課題3すら実装できずに13点のみで、かなり酷い結果になってしまった。
ランプ(Lamps)
区間を選んで0に変更、1に変更、区間flipの3種類の操作をして、文字列AをBと一致させるための最小操作回数を求める問題。
小課題1について考える。全てのbitを0にするか1にするかをそれぞれ決めても状態数が十分少なく済むため、頂点でBFSをすると解ける。6点。
小課題2以降が全く分からなかった。ある程度の人数がこの問題を解いていて、6点しか取ることができなかったのはかなり悲しい。
時をかけるビ太郎(Bitaro, who Leaps through Time)
問題設定が面白かった。
小課題1について考える。これはで愚直にやってよいので、解く。制約がかなり大きいのでこれを高速化しても満点は取れそうになかった。残念。
区間取得、区間変更クエリが与えられる問題なため、Segtreeに載せる事を考える。の時点で関数と対応する区間の始点に突入した場合の、区間の終点に出てくる時の最小スコアと時間の組 のような関数を考えると、Segtreeにはこの関数を載せて、関数同士のマージ動作を実装すればいい事がわかる。
想定解はこれで合っていたようだが、ここからの実装で大きな失敗をしてしまった。Segtreeに載せる要素が6つ(始点の最小時刻、始点の最大時刻、終点の最小時刻、終点の最大時刻、区間の長さ、区間のスコア)で、それらのマージ動作で6つの場合分けを実装しなければいけない事になり、他の問題が解けずに集中力が切れていた事もあり、実装ができずに破滅してしまった。
とても難しかった。厳しい。
まとめ
13 + 6 + 4 = 23点。本当に悲しい。通すべきだった部分点すら通せない、実装ができない、集中力が途中で切れてしまう、様々な所で失敗してしまった。
現時点で合計286点、初日と2日目のペースが続いていれば4日で500点を目指せたのに、大失敗をしてしまった。参加者全体の中ではおそらく15〜18位ぐらいだと思う。
4日目
24 + 0 + 6 = 30 かなしい
まとめ
4日合わせて129 + 134 + 23 + 30で316点だった。3日目と4日目が酷すぎる。残念ながら今年の進級はほぼ確定しているため来年のJOIには参加できない可能性が高いが、もし留年する事になったら来年の春合宿を目指して頑張りたい。
