JOI難易度8を2日で全クリする
これはなんですか？
基本に立ち返るべく、難易度8をもう一周する事にしました
解説記事ではないので、感想とかを書きます
ネタバレ注意
Shuffle
1回のシャッフルにつき列が分かれて増える数は高々2なので、愚直にシミュレーションしても間に合う事が分かります
シャッフル後のカードは増加列をいくつか持っている形になっているので、それを持ちます
実装辛い...
植木算消えろ！！！
散歩
これad-hocで面白い
ある時点で各頂点の向きがどちらかは、最初の向きとその頂点を通った回数によって決まります
各頂点を N 回通る時、その頂点から右と下の頂点へはそれぞれ大体半分ずつ通ります（奇数の場合、最初に向いている方向が1回多い）
よって、N 回目に散歩する時に各頂点がどちらを向いているかが分かるので後は適当にシミュレーションするだけです
認証レベル
これ簡単枠じゃないかな
cost1[i]= 事務所1で i 室入るために必要な最小コスト
cost2[i]= 事務所2で以下同文
として、事務所1で入る室数を全探索すれば良さそうな事が分かります
コストは、エレベータの所からスタートしてstd::priority_queueを使うと簡単に実装できます
事務所1,2で同じ実装をするのは面倒なので、関数でやると楽ですね
Sequence
要は奇数か偶数かを考えれば良い事が分かります
鳩の巣原理より、周期の長さは高々 (2n-1) × n で、実際はもっと短いので間に合うっぽい？という事が分かります
というわけで周期の長さがいくつかをシミュレーションして、後はバケット法の下位互換（伝わって）をすれば良いです
↓こういうやつ
while(p%n&&p<q){ ans+=v[p++]; } while(q%n&&p<q){ ans+=v[--q]; } ans+=(q-p)/n*sum;
周期が確定した後に最後のを消し忘れてN回WA出した...
Pyramid
これも簡単枠。
std::priority_queueを使って、ピラミッドの高さが高い方から周りに伝播させて行けばいいです
define int long longをしているとMLEします（懲りない人）
Abduction
X座標とY座標は独立なので、それぞれimosの要領でDPすれば良いです
配列の再利用をしないとMLE
dpx[H][j]とする所をdpx[W][j]にして、気づくのに1時間かかった...
カス
Advertisement
トポソみたいな感じで、上からドバーッと流していけば良い事が分かります
これ、強連結成分分解とは言わない気がする...
Distribution
子の中で最も得点の高いパスを親に繋げて、他はそこで打ち切りみたいな実装をすると、O(NlogN)になって嬉しいです
以前やった時はLCA使って実行時間ギリギリで通した記憶...
方向音痴のトナカイ
これ難易度9だと思うんですが...
前からやるとTLEするので、後ろからやります
後ろからだと、次にできるやつが高々4通りなので間に合います
やっぱり難しいなぁ...
------------------ここまで4/29------------------
Sengoku
以前やった時は面倒な方法をしたのですが、今は45°回転する一般的なテクを知っているのでさほど難しくはないです
重複した線に気をつければ、そこまで難しくはないはず...?
a plus b
見た目は簡単なのに...ってやつですね
以前やった時、実装に苦しんだ覚えがあって二度とやるかくらいに思っていたんですが、大して難しく感じませんでした（嬉しい）
ただ、長さが0のものをvectorに入れていたせいでバグって30分溶かしました...（ァ）
DNA Synthesizer
ただのやるだけDPに見えますが、実行時間制限が短いです
std::setを使うとTLEしますが、std::unordered_setを使うと余裕で間に合います
set::findだけを使う時はunordered_setを使った方が速いです
Trieでやるともうちょい速いです
歩くサンタクロース
全点からの距離の和の最小は中央値という有名なやつを利用します
どれか1つだけ取り除く場合、中央値はどう変化するかを考えれば良いです
そんなに難易度8の中ではまぁまぁ難しい方？
Deciphering
部分文字列の数え上げ、典型中の典型ですね
define int long longを付けてることでTLEやMLE、難易度8はめちゃくちゃ多いなぁ...
Nails
正三角形は嫌なので、傾けて直角三角形にします
あらかじめ加算のスタートとゴールをimosで加算してから斜め方向にimosすればOK！
面白い問題だと思います
JOI Flag
ほとんど塗られてないので、適当な枝刈りをすれば良いです
愚直に実装すると大変ですが、工夫すれば楽に実装できます
現代的な屋敷
向きが同じ状態の周りのスイッチと、向きの違う同じ場所に対して辺を張れば良いです
1-2-3-4-5のように連なっている場合は、1-3のような辺は必要ありません
あとは適当にダイクストラすればOKです
マスコットの片付け
かなりAtCoder寄りの問題ですね...
縦長の長方形を追加する時、大事なのは高さであり、上下にいくつずつあるかはどうでも良いです
なので、DP[i][j] = 既に上下に i マス 左右に j マス追加した場合の数 としてDPをして、後は適当に最初の長方形を作るまでの通り数と上下左右にそれぞれ割り当てる通り数を掛ければOKです
面白い問題だと思います
Spy
Nの方の制約がゆるいので、そっちから考えます
ans[i][j] = JOIの i , IOI の j が参加するプロジェクトの個数として、JOIとIOIでそれぞれ下に降りていけばO(N2)です
難易度7でも良いんじゃないかな...
Mountain Rescue
難易度8としては珍しいインタラクティブです
割と天才解法だし、難しいと思うんだけどなぁ...
Presents
全ての出次数が1という事は、各連結成分が1つの閉路と、閉路に向かって生えている辺のみという事です
閉路に向かって生えているのは全て嬉しさが多い方にできます
閉路の中で、自分と違うのを好む人が偶数の場合、全員を嬉しさが多い方に分配する事ができます（偶数回反転したらもとに戻る）
しかし、奇数の場合は閉路の中の誰かを犠牲にする必要があります
あとはDFSやるだけ
フクロモモンガ
最大の懸念は、時間が短いかつ高さが高いという事はあり得るかということです
登る以外は全て時間と同じだけ下がるので一度も登っていないものは関係ありません
また、一度登ったらギリギリの高さまで登ってギリギリ到着を繰り返す事になるので、必ず高さ0になり関係ありません
よって、時間だけを見れば良いことが分かりました
後はダイクストラするだけです
財宝
半分全列挙からRange Minimum Queryです
mutliset ... TLEする
Segtree ... ギリギリ間に合う
スライド最小値 ... 余裕で間に合う
コピー&ペースト2
元の位置を逆算する一般的なテク
Bulding3
Building N を見る度に頭痛くなるんですけど...
Building 4がトラウマ過ぎる
必ず使わなきゃいけない数がある場合とない場合があるぞい！
重複に注意
遺産相続
クラスカル法を思い出すと、小さい方から貪欲に追加していくだけで最小全域木になる、つまりなるべく番号が小さい人に割り当てるのが最適です
より、連結であるかは単調になり、二分探索が使えます
難易度8の中では割と難しい方なのでは...?
屋台
まわりのを既に買ったかどうかを5bitで持つDP
実装鬼畜すぎる...
多分難易度8最難関
鉄道運賃
BFSで最短経路で頂点に入ってくる辺の本数を持っておき、それが0になったら消して子に伝播...みたいな事をすると良いです（語彙力）
既に消した辺を二度消すみたいな事をして1WA
準急電車
増える量は単調減少なので、単純にpriority_queueに入れて貪欲法でOKです
めちゃくちゃバグらせた...
本番だったらマジでパニックになってそう
JOIOI王国
普通にやると実装が面倒になるのですが、Sayaka姉貴の言ってた90°回転を4回やるテクを使うと簡単れふ
おわりに
疲れました...
4/29 9問
4/30 21問
一日で終わらせるのはほとんど不可能に近いです
是非挑戦してみて下さい！
