問題 n頂点m本の辺からなる無向グラフが与えられる。 このグラフの辺に適当な向き付けを与え、有向グラフにして、 全体を強連結（任意の2頂点u,vについてuからvへのパスが存在する）にすることができるか答えよ。できる場合は具体的な向き付けを一つ出力せよ…

問題 n人の人が以下のようなルールで列に並ぶ。 i番目の人が来て、列の最後尾に加わる。i番目の人は重要度a[i]と、常識度c[i]を持っている。 一つ前の人の重要度a[i-1]が、自分の重要度より低かったら、その人前へ割り込む。 割り込みはc[i]回だけできる。 n…

問題 n個のハンガーが一列に並んでいて、左から順に1からnの番号がついている。 以下のようなクエリがq個来るので処理せよ。 0 l r l以上r以下の番号のハンガーのうち、上着がかけられているハンガーの数を出力する。 (0以外の数字) 数字のidをもつ人が、次…

問題 m個の塩基配列が与えられる。 n文字の塩基配列で、全ての文字が塩基配列にカバーされている （すべてのiに対して、ある整数l≦i≦rが存在して、塩基配列のl文字目からr文字目までがいずれかの塩基配列に等しい） ようなものの数をmod 10^9+9で求めよ。 制…

問題 n桁のb進数の数のうち、leading zeroがないものを全てノートに書く。 1ページあたりc個の数字を書くものとするとき、最後のページに書かれる文字の数はいくつか求めよ。 制約条件 b≦10^(10^6) n≦10^(10^6) c≦10^9