読者です 読者をやめる 読者になる 読者になる

右上➚

プログラミングに関するメモをのこしていきます

yukicoder 2015/05/08

yukicoderさんのコンテストに出てきましたー

★から★★★までの四問ということでもしかしたら完答いけるんじゃないかとか甘いことを考えていたのですが...ww

結果

3完で19位でしたー4問目はTLEの連発で...解法全く思いつけませんでしたねー
ただ前よりはちょっとは力ついてきたのかななんて思ってますww(甘いかな

復習

No.203 ゴールデン・ウィーク(1) - yukicoder

与えられた2週間の中で最長の連休を求めよという問題ですね!
2週間の情報の与え方が

oxoooxx
xxoxxoo

のように一週間ごとにわかれているのでそのまま素直に一週間ごとに入力受け付けるとハマる気がしますw
単純に14要素の配列を用意してそこに入れていけば単なる最長の連続区間を求める問題ですね!!

No.204 ゴールデン・ウィーク(2) - yukicoder

いやーやられまくりましたねwwランキングを見るとわかるのですが、めちゃくちゃ罠問題という感じでしたw
submit回数がすごいことになってましたね全体的に

問題は、先ほどのゴールデンウィークの問題とほぼ一緒なのですが、今回は有給を使うことが出来ます!!幸せっぽいですね
これだけならまあ簡単なのですが...

引っ掛けポイントはこの二週間以外の部分です!

2週間分の平日(x)と休日(o)が分かるカレンダーが与えられます。 この2週間の期間以外は、平日とします。

この文を読み飛ばしているとWAまみれになります。というかなりました...
これさえ見逃さなければ素直にガリガリ数えていくだけですので、実装としてはそこまで難しくはないと思います。
もっときれいな実装や解法があるんでしょうけど、それは追々...

No.205 マージして辞書順最小 - yukicoder

与えられた文字列群の先頭から一文字ずつ選んで組み上げられる文字列のうち、辞書順最小になるものを求めよという問題。
すべての文字列の先頭文字のうち、最小のものを選んでいけばよいっぽいのですが、ひっかかりポイントとして、

az
za

というような問題があります。
この場合、a が最小なので

z
za

となります。
次の一文字を決定する際に、何も考えずに辞書順最小の文字を考えると

(空)
za

となります。
そして出来上がる文字列は azza となります。
正しい答えは azaz ですよね。ここがハマリポイントぽいです。

今回はこのコーナーケースがサンプルにあったので発見しやすかったですね。なかったらはまってたと思います。

No.206 数の積集合を求めるクエリ - yukicoder

わかんなかったー!くそー...

とりあえずナイーブな実装で multiset でAの各要素 - Bの各要素の集合を作り、 0の数が Q = 0の時の解, 1 の数が Q = 1 の時の解, ... というようにしてみました。 解はあっているっぽかったのですが、案の定 TLE ...
此の実装だと O(L * M) かな? L, M10 ^ 5 までいくのでこれじゃダメダメですねー...

で、解答見たのですが、解答読んでもよくわからない...ちょっと考えてみます...

まとめ

前よりはまし!すこしだけ!