お題箱より。 No.1460 Max of Min - yukicoder 解法 この問題の解法はいくつかのステップで構成されていて、その1つ1つが覚えておくと有用なテクニックだと思います。順に追っていきましょう。 ステップ1 求めたい値 は、与えられた数列の要素に対して と を…

お題箱より。 No.1067 #いろいろな色 / Red and Blue and more various colors (Middle) - yukicoder 解法 箱を並び替えても答えが変わることはないので、 の昇順に並べておきます。 各箱から玉を1個ずつ取り出し、ある1つの色 の玉がちょうど 個選ばれる場…

No.1100 Boxes - yukicoder 解法 まずボールが1つも入っていない箱の数を固定します。これを とすると、その選び方は 通りです。 その上で、残りの 個の箱全てにボールが入るような場合の数を求めます。これは包除原理を用いて と求めることができます。 先…

No.1051 PQ Permutation - yukicoder ※当初の公開時点での解説およびリンク先コードが誤っていたため、修正しました。 解法 ※以下の解説中で「辞書順で1つ進める」と書いた時には、「もし進められない（既に辞書順最大である）ときには -1 を出力して終了す…

お題箱より。 No.1029 JJOOII 3 - yukicoder 解法 計算量などの表記のため、 と置きます。この問題の制約では です。 作りたいレベル のJOI文字列を と表記します。文字列のインデックスは0-indexedで表記します。 を前から順に作っていく、以下のようなDPを…

No.980 Fibonacci Convolution Hard - yukicoder 変な解き方をしました…。後述するように厳密に正しい解法ではないので、あまりオススメはしません。 解法 0-indexedのほうが楽なので、数列 を あとは同様の漸化式で定義される数列、としておきます。クエリ…

お題箱より。 No.778 クリスマスツリー - yukicoder 解法 飾りを頂点0を根とする根付き木とみなします。言葉を言い換えると、求めるものは以下の2条件を満たすペア の個数です。 頂点 が頂点 の先祖である。 頂点番号について、 である。 ここでの「先祖」は…

No.819 Enjapma game - yukicoder writerさんの解法が天才なので、地道に実験して解いた私の解法もまとめてみたいと思います。 解法 「その盤面状態で自分のターンが回ってきた時に勝つ/負ける」という状態をそれぞれ勝ち状態/負け状態と呼ぶことにします。 …

No.803 Very Limited Xor Subset - yukicoder 解法 AtCoderに「Limited Xor Subset」という問題があります。この問題の想定解法は今回のyukicoderの問題とは全く違うものですが、この問題に対するこちらの別解がとても参考になります。私もコンテスト本番は…