てすと
Awkward Response
1000.. とか 999... が強そう
10^k に対してyesになるのは N = 1, 10, ..., 10^k と 10^k <= N のときかつそのときに限る
まずNが10^kの場合を弾きたくなる
10^k と 2 * 10^k をいい感じにやればできる
10^kを弾いたので、10^k に対してyesになるのは10^k <= N のときかつそのときに限る
これで桁数が特定できる
桁数がわかったら、末尾に0をつけてクエリを投げればかならず N < n になるので
str(N)とstr(n)の大小関係を返すオラクルだとみなすことができ、これは明らかに二分探索ができる
Mole and Abandoned Mine
こんなの一回見たら忘れられるわけないんだよね
1 から N まで橋だけで繋いで間の頂点にクリークがぶら下がっている形になる
O(3^N)のDPっぽくやる 計算量がやばい AtCoderを信じろ
Sports Festival
なーーんもわからん NP困難やめろ
この配点で僕がしばらく考えてわからないということは貪欲です（メタ考察）
空集合から足していくのはつらそう
全体集合から引いていくのはどうか？
集合から要素を一つ取り除くとき、ある種目の回数は広義単調に増加する
したがって、ある状態での最大値がXだとすると、
それを下回るためにはXであるような要素は全て消さないといけない
これを貪欲に繰り返すだけで解ける
正当性が割と非自明な気がするな
ある値Vを固定してそれ以下を達成するような集合があるか？という問題を考える
このとき極大な集合というのが存在するなら一意に定まり、それが上記の貪欲と一致する
貪欲法を適用して得られる集合をSとする
x in U\S に対して、仮定から S ⋃ {x} の値はVより大きくなる
したがって val(T) <= V であるような集合TはSの部分集合のみであり、Sの極大性が示された
nとmを間違えて1WA 競技プログラミング初心者ですか？
感想
Awkward Response、部で演習室に集まって出たときに冷え散らかしたなあ
