/\/\/\/
まず最初勘違いしていましたが、奇数＜偶数である必要はないんですよね
ですから、mapなどを用い
奇数の列で1, 2番目に多い a1, a2と
偶数のそれ b1, b2 を用意して基本a1とb1
a1==b1だったとき、max(a2, b2)をa1またはb1の代わりに用いればよいです
ただし、コーナーケースとして、a2, b2が存在しないときはn/2を出力します
またa2が存在しない場合はb2を、b2が存在しない場合はa2を用います
abc171-v
A
'A'-'a'
B
sort
C
ややこしい。
n-=(n%26==0?26:n%26);
n/=26;
D
mapを使ってずる
まあずるではないけど
Dのほうが簡単
E
こどふぉでやったことあるような問題が出てきましたねぇ
CodeForcesとか、Codechefはこういう問題が好きな傾向がある
さて、これは累積XORみたいなもの
N=4の場合で考える(累乗になるのでXORをxとしています)
a2 x a3 x a4, a1 x a3 x a4, a1 x a2 x a4, a1 x a2 x a3
みたいな書かれ方をしているこれを便宜上
p1, p2, p3, p4とする
ここで、p2 x p3 x p4=a1となる！
それはすなわち、(すべてのXOR) xor p1=a1ということ！
だから、O(2*N)で求められる！
ただ、いまいちNは偶数という制約の意図が分からない
追記:)Nが奇数のとき
N=3のときを考えると
a2 xor a3, a1 xor a3, a1 xor a3 より
p2 xor p3=0!=a1となるので、バグってしまいます
F
うわ、文字列の挿入...
これは、もちろん全探索は不可能ですね
ですので組み合わせ数を数える形になると思います
個人的に方針は二つあり、
(i) 実際に位置確認しつつ挿入後の形を予想
(ii) 全通りからsの順含む文字列を引く
(i)は出来なさそうだし、(ii)は被るパターンがある
例えばサンプル1だったらooooooofとかは被る
難しいね
解けません
展望
初めてEが解けた！
うれしいね♪
abc080
virtual
A
やる
B
やる
C
え、そもそもの(問題文の)日本語が難しい
理解するのにとんでもなく時間かかった
うーん、まず全探索を考える
bit全探索を用いると[tex:O(210)]位になると思うのだが間に合うだろうか
TLEのみ心配だったけど普通に高速でした
D
区間スケジューリング問題->貪欲法かDPの匂い
制約の一つ、S-0.5の部分は面倒なので、
と置き換えると、始点と終点のみに着目して計算していけば良さそうであることが容易に理解できる
それを時間でsortしていけばいいとわかる
さて、まず使うデータ構造だが、配列だと厳しいところがありかつsortする必要があるのでpriority_queueを、時間は「始まりか終わりか」「何のチャンネルか」という３つの要素が必要であるからtupleを使用する(tupleにしたのはqueueの型をvectorにするときの挙動がわからなかったため、pairであれば分かるので要素数も定まっているしtupleを用いようと思った)
また、今各チャンネルについて録画をしているか否かを判定するhantei、今使用している録画機の数curを設ける
多分一番の肝となるのは「終点と始点が重なったとき」の処理だろう
だが、これを処理するのは案外簡単で、
同じチャンネルで複数のテレビ番組が同時に放送されることはありません。
という制約を利用することにより始点優先ソート(おそらく昇順ソートなので始点を0、終点を1と保存)にしておいてhanteiを用いすでにそのチャンネルが録画されているときは追加しないとすればよい
かなりいかれたコードが出来上がった(多分自分が今までに書いたコードで一番汚い)が、WAを食らった
しかも1つのテストケース(04.txt)だけで食らっているのでおそらくコーナーケース
なのでひたすらいろんな自作ケースを与え、コーナーを探す
そしたら恐らくこれというものが見つかりました
4 3 1 4 1 2 6 2 4 8 1 6 10 3
t=6の時、録画機は3台使われている必要がありますが、2と出力された
なので現在時刻を管理するnowなどが必要になります
紆余曲折あり、なんとかAC
つらかった...
Submission #22327988 - AtCoder Beginner Contest 080
展望
もっと問題を解くのが早くなるといいね
