Code Festival 2014 予選B

Welcome to CODE FESTIVAL 2014 予選B - CODE FESTIVAL 2014 予選B | AtCoder

久しぶりに記事書いてみます。

結果

4完 (4 AC / 0 WA)

• A: 00:39
• B: 04:26
• C: 32:12
• D: 83:06

CとD、書くの遅すぎる。
本戦進出圏内ですが、社会人は出られません。
社会は厳しい。

Problem A - あるピアニスト

2つintとって、maxするだけ。
ehaさんがAtCoder最速の9秒だったっぽいです。
さすが響のプロデューサーは違う。

Problem B - 歩く人

aiを順番に足して行って、K以上になったときの、(i+1)を出力すればいい。

Problem C - 錬金術士

とりあえず、「S1とS2からN文字ずつ取る」という制約は抜きにして実装。

• 文字列S1から貪欲に、S3に当てはまる文字を取れるだけ取る。
• その後に、同じようにS2から貪欲に取れるだけ文字を取る。

上記の計算で、S3を作るためにS1から取り出した文字数をa1、S2から取り出した文字数をa2とする。
もし、(a1 + a2 != |S3|)ならばそもそもS3を作れないので、NOを出力。

あとは「S1とS2からN文字ずつ取る」という制約。
上記の計算後、a1かa2どちらかが大きい(もしくは等しいが、その場合はYES)。
大きい方が、文字を余計に使っているため、そっちから、文字が足りない方へ、a1=a2になるまで文字を譲ってあげればいい。
AからZまで見て、譲ってあげられそうな文字を譲って、それでもa1=a2にならないのであればNO、なるのであればYES。

Problem D - 登山家

昔同じような問題を解いていたっぽいのですが、この方法で解きませんでした(解いたことあるの忘れてた)。
PKU : 3250 - Bad Hair Day - Respect2Dの日記

↑の解き方覚えてない思考。
僕の解き方やってる人、他にいるんだろうか。

• 1番低いやつは同じ高さ以外のものは何も見られない。
• 2番目に低いやつは、1番目に低いやつを見ることができる。
• 3番目に低いやつは、1番目に低いやつも2番目に低いやつも、同じように自分より低いものとして扱うことができる。
• ...
• i番目に低いやつは、i-1番より低いやつを全て同じように低いものとして扱うことができる。
• ...

この考え方が最初に浮かんで、低いやつから順番に考えて消していけばうまいこと解けるんじゃね？と適当に考えて、とりあえずソート。

[3 2 1 2 3]という数列で考えます。
とりあえず、一番低いやつ(1)を処理。

2以上から見たら、1はないものと等しく考えられるので、これ以降は1を飛ばして読めるようになります。
図中の矢印のように、これ以降は[1]の右は[3]、[3]の左は[1]であるように考えればよくなります。
（これによって、計算量を落とすことができる）

次に、2を処理。

これで、2以下は考えなくてよくなって、[0]の右は[4]、[4]の左が[0]になる。

と大体こんな感じのやり方をしました。
うまく書けば、O(n)になると思っている(思っているだけなので本当かわからない)。
あ、ソートのO(n log n)を除けばです。

説明めっちゃ適当なので、詳しくはコードを読んでください。
Submission #258604 - CODE FESTIVAL 2014 予選B | AtCoder