読者です 読者をやめる 読者になる 読者になる

ゆらのふなびと

競プロ, Python, C++

ABC041 D - 徒競走

問題 N匹のうさぎ(1..N)が徒競走をした。 M人の観客から、x_iはy_iより先にゴールしたという情報がわかっている。 同着はいないとするとき、着順は何通り考えられるか? 制約 2 <= N <= 16 1 <= M <= N(N - 1) / 2 解法 着順は最大で N! 通りある。いくら制…

ABC040 D - 道路の老朽化対策について

問題 N個の都市がM本の道路でつながれている。i本目の道路は都市a_iとb_iを結び、y_i年に造られたものである。 Q人の国民がいる。国民jは都市v_jに住んでおり、作られた都市がw_jより大きな道路しか使わない。 各国民について、自身が住んでいる都市から条件…

ABC038 D - プレゼント

問題 i 個の数の組 (w_i, h_i) が与えられる。これらから自由に選んで並べてw, hともに狭義単調増加な列を作るとき、その最大の長さは? 制約 1 <= N <= 105 1 <= w_i <= 105 1 <= h_i <= 105 解法1: LIS まず、入力をwの昇順にソートします。すると、以下の…

ABC009 D - 漸化式

行列累乗は半環なら普通の演算以外でも使えるよ!という問題。 問題 数列 A はすべての要素が 32 ビットの符号なし整数で表現でき、その値は次のようにして決まる。 はじめの K 項 A1, A2, …, AK は入力で与えられる。 A とは別に K 項の数列 C1, C2, …, CK …