1/7 PKU
2586 Y2K Accounting Bug
ある会社はある年の各月において、利益が出たならその額はsで、損失が出たならその額はdであった。その会社は、その年の任意の連続する5ヶ月において、損得を合計すると赤字になったらしい。その年の利益として考えられる最大値を答えよ。
ビット演算で無理やり通した
2005 Blackjack
ブラックジャックをN個のトランプデッキを使ってやってて、ディーラーの1枚のカードと、自分の2枚のカードが分かってる。ディーラーはもう一枚なんだかわからないカードを持ってる。自分のほうが高い点数を持ってる確率を求めよ。
やるだけ。Aを2枚持ってる場合とかに注意
2188 Cow Laundry
N本のワイヤーが、上下の端につながれて、スパゲッティしてる。どちらかの端において、隣り合う2つのワイヤーの端を入れ替えることができる。スパゲッティしてるのをほどくには何回入れ替える作業が必要か求めよ。
どっちの端でも入れ替えられてややこしそうだけどどっちの端で入れ替えてもスパゲッティ回数は１回しか減らないのでバブルソートの交換回数求めるだけ。N<=1000だからO(N^2)で余裕
3979 分数加減法
分数の足し算か引き算をせよ。
どう考えてもやるだけ
3981 字符串替換
you を we に置き換えよ。
やるだけ
3982 序列
A0, A1, A2が与えられたとき、An = An-1 + An-2 + An-3で定められる数列のA99を計算せよ。
多倍長やるだけ
1493 Machined Surfaces
2つのブロックっぽいものがある。それをがしゃこーんってくっつけたときのすきまの数を求めよ。
やるだけ
2810 Take Your Vitamins
題意の説明が面倒なやるだけ
2176 Folding
文字列を、n(XXX)という感じで折り畳むことができる。これは、「XXXをn回繰り返す」という意味である。折りたたんだあと文字列の長さが最短になるように折りたため。
DP
2831 Can We Build This One?
高速道路建設計画がある。でも全域木をなし、建設コストが最小になるように建設すると、いくつかの道路は建設されない。ある道路の建設費を下げたとき、この条件下でその道路は建設できるか？
Kruskalの応用。クエリと普通の道路情報を一緒にしてソートして（コスト同じならクエリを先にする）、道路情報が来たらunion findでmergeして、クエリが来たらrootが同じか違うか確認する。
2160 Box
与えられた6枚の紙で、直方体ができるか判定せよ。
注意深くやるだけ。ある(x, y, z)が存在して、(x, y)*2、(y, z)*2、(z, x)*2が存在するか判定。
3252 Round Numbers
ある整数Nで、2進表記したとき0の個数が1以上になるものをRound Numberと呼ぶらしい。ある範囲に含まれるRound Numberの数を求めよ。
まず、1からNまでに含まれるRound Numberの数を求めるという問題に置き換える。
そして、例えばN=101100として、(2進)1桁、2桁、3桁、4桁、5桁のRound Numberの数を求める。そして、100xxx、1010xxに当てはまるRound Numberの数を求める。最後に、101100がRound Numberか判定する。
1459 Power Network
電力網があって、ノードには発電所や消費者があったりする。各エッジは流せる電力量が決まってる。発電した電気を消費者へ送る。消費できる電力の最大量を求めよ。
どう考えても最大流やるだけなんだけど、昔作ったDinicライブラリを使ったらTLE。原因がわからないのでEdmonds-Karpで書いたのを使ったら通った。
