CODE FESTIVAL 2018 に参加しました。 昨年は予選 C のギリギリで引っかかって通過したのですが、今度は予選 A で決められてよかった。 本選前 会場近くをうろうろしてました。 ちょうど同時期に開催されたきらら展の様子。#code_festival pic.twitter.com/J…

問題 https://www.ioi-jp.org/joi/2017/2018-ho/2018-ho.pdf 考察 重要な性質として、ある定期券のもとでの から への最短経路は、 [定期券に含まれない区間] [定期券に含まれる区間] [定期券に含まれない区間] のような構成になると言えます（各区間は も認…

問題 https://www.ioi-jp.org/joi/2017/2018-ho/2018-ho.pdf 考察 一つの串団子と、それに含まれる緑色の団子は一対一に対応します。 よって各緑色の団子について、「それを使って串団子を作るか？ 作るなら縦と横どちらの向きに作るか？」を考えることにし…

問題 https://www.ioi-jp.org/joi/2017/2018-ho/2018-ho.pdf 考察 展示する最大の美術品と最小の美術品がどちらも不定だと考えづらいので、片方を固定してみます。ここでは最大を固定するとします。 まず、同じ大きさの美術品がない場合を考えます。 あらか…

問題 https://www.ioi-jp.org/joi/2017/2018-ho/2018-ho.pdf 考察 まず分かることとして、K 個あるマッチは使い切ってしまったほうがお得です。 また、マッチを付けるのは来客の直前、そして消すのは客が帰った直後にしたほうがいいのも明らかです。 これら…

【問題】 agc004.contest.atcoder.jp【考察】 最初、魔法で色を変えられるスライムは 1 匹だけと勘違いしてて、各色のスライムごとに元になるスライムをどの色にすればコストが最小になるかを計算するコードを書いたんですが、サンプルの 2 で落ちて誤読に気…

【問題】 arc058.contest.atcoder.jp【考察】 典型数え上げ問題の変形タイプ。この問題では少し特殊な制約がついていて、二項係数ライブラリで一発 AC というわけにはいきません。まず数え上げ問題の常套手段として、いくつかの排反な事象への場合分けをしま…

【問題】 arc024.contest.atcoder.jp【考察】 そこまで難しくないんですが、結構一般的な知見を得た問題。 以下簡単のため、互いに共通部分をもっていてもアナグラムダジャレになれる、と考えます。まず、2 つの部分文字列がアナグラムの関係にあるとき、そ…

【問題】 arc014.contest.atcoder.jp【考察】 N がそれなりに小さいのですが、ギリギリ半分全列挙はできないくらいの大きさ (そもそも効率的にマージする方法もなさそうですが)。そこで O(N^4) くらいの DP かなと思ってあれこれ考えてみるものの、箱に入っ…

【問題】 arc038.contest.atcoder.jp【考察】 Grundy 数を使いそうなのはすぐに分かるのですが、普通に山ごとに Grundy 数を設定しようとすると、ある山の遷移が他の山に影響を与える設定のせいでうまくいきません。そこで視点を変えて、茶碗に入っている豆…

【問題】 arc037.contest.atcoder.jp 【方針】 K 番目に小さい値を求める問題 (CodeForces 191E) を最近やっていて、それと同じく二分探索でやるのかなと最初に思う。ちょっと考えたら、ある値 S より小さいようなマス目の値は std::set で簡単に求まりそう…