JOI難易度8 感想
埋める
E - シャッフル
実装やるだけ
D - 散歩
回目の状態が簡単にわかるので、後はシュミレーション
E - 認証レベル
やるだけ
sequence - 数列 (Sequence)
問題そのものはまともでおもしろいが、MLEが厳しいためにちょっと定数倍むだにとるけどねみたいな方針を取った
pyramid - 貫きピラミッド (Pyramid)
ぱっと見えなかった。イメージは多始点Dijkstraみたいな感じかな?(Dijkstraではないけど)
abduction - 誘拐 (Abduction)
今まで見た中では断トツでむずかしい。
こんなの縦横独立じゃないと解けないと信じるとちゃんと独立になってることに気づく
advertisement - 宣伝 (Advertisement)
SCC貼るだけやるだけ
distribution - 冊子の配布 (Distribution)
頭がついてなかったので、木の2乗DPの応用で解いたがどう考えてもいらなくて笑ってしまった
F - 方向音痴のトナカイ
かなりカス。逆からみると確かに小さくなるが、こんなもん前からみても本質は変わらんだろ
手元実行ならいいが、そうじゃないならメモリorTLが大変
sengoku - 戦国時代 (Sengoku)
絶対値を外して、算数する
aplusb - 足し算 (a + b problem)
やるだけ
dna - DNAの合成 (DNA Synthesizer)
基本的なDP
D - 歩くサンタクロース (Walking Santa)
縦横独立に考える。ぐっと睨むと1つを取り除いたところで、中央値となるx, y座標はともに候補は高々2つしかない
deciphering - 解読 (Deciphering)
部分列DPの基本問題
D - 釘 (Nails)
2次元imosの理解を問ういい問題な気もする(難易度は?といわれるとあれだけど)
joi_flag - 日本情報オリンピック旗
枝をかりましょうという問題。実装も易しい
3 - 現代的な屋敷 (Modern Mansion)
基本的な拡張dijkstra
2 - マスコットの片付け (Mascots)
基本的なDP
3 - スパイ (Spy)
こんなもんはbitsetで殴ればおしまいです
3 - 山岳救助隊 (Mountain Rescue Team)
問題そのものはおもしろい
2 - プレゼント (Presents)
functionalグラフになれていれば簡単
D - フクロモモンガ (Sugar Glider)
実は高さの状態は高々1つしかみなくていいのになかなかきづかなかった。おもしろい。
F - 財宝 (Treasures)
TLは別に厳しくなて、半分全列挙はでできます。
A - コピー&ペースト 2
逆からみる典型
E - ビルの飾りつけ 3
for文でiとjのミスでだいぶぺナ吐いちゃった。
問題自体は単純で挿入しないといけない場合としなくていい場合で場合分け
K - 遺産相続
単調性になかなか気づかなかった。いい問題
F - 屋台 (Food stalls)
やることは簡単だが、実装が添え字で頭壊れる~~~~
C - 鉄道運賃 (Train Fare)
最短経路木に着目する問題。ウニみたいなのに注意だね
B - 準急電車 (Semiexpress)
貪欲法。旧ABCにちょっと似た発想のがある
C - JOIOI 王国 (Kingdom of JOIOI)
90度回転させながらやると楽。実装問題と思ってたけど、最終的にはかなり簡潔になった