問題 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 個あるマッチは使い切ってしまったほうがお得です。 また、マッチを付けるのは来客の直前、そして消すのは客が帰った直後にしたほうがいいのも明らかです。 これら…