はのちゃ爆発

はのちゃが技術ネタとか日常のこととかを書いてます。

AtCoderに初めて参加して(また)大爆死した話

※ 2016/10/25 追記

B問題について、 @chokudai さんから直々に解説を頂きました。

私の「同じケーキを連続で食べる最小日数」の解釈のしかたが違ったようです。 50日->1日->50日パターンでも、連続で食べている日数の合計は 49日 x2 で 98日。 今回の問題で求めるべきはそちらの数値でした。

※ 追記ここまで


また、というのは前回のISUCONに引き続き、的な意味で。

そのまんまですが、気まぐれに参加したら酷いことになったので自戒を念を込めて記事を書きます。

(問題を記事に書いちゃまずいとかは無いと思ってますが、あったら教えてください。対応します。)


AtCoder?

プログラマ諸氏におかれましてはご存知かとは思いますが、オンラインでプロコンできる感じのサービスです。

https://atcoder.jp/atcoder.jp

以前から興味はあったのですが、丁度コンテストが開かれていたのと、気分が向いていたのとで、ふらっと参加してみることにしました。

今回参加したコンテストはこちら。

code-festival-2016-qualc.contest.atcoder.jp

CODE FESTIVAL 2016 というイベントの予選らしいですね。 本戦いける気はしなかったので気にしてませんでしたが。

今回の問題

全部で5問出題されましたが、2問目で盛大に躓いたのでそれ以降は触れてません。 AtCoderだと問題をA,B,C...と順番に呼ぶみたいなので、以後それに倣います。

A - CF

適当な英数字で構成された文字列から CF を取り出すという問題。

このコンテストの名前は CODEFESTIVAL で、いくつかの文字を消すとCFという文字列にすることが出来ます。 好奇心旺盛な高橋君は、他の文字列に対してもこのようにCFを得られるか気になりました。 英大文字アルファベットからなる文字列sが与えられるので、sからいくつかの文字を消してCFという文字列にすることが出来るか判定してください。

さすがにこれは難しいこともなく、正規表現使えばいいか…という感じ。提出したコードは以下。

str = gets.chomp
reg = /C.*F/
 
if reg === str
  puts 'Yes'
else
  puts 'No'
end

書きながら、これ下のif文三演算子でええやんということに気付いた。ハズカシー

str = gets.chomp
reg = /C.*F/
 
puts reg === str ? 'Yes' : 'No'

よし、満足…が、しかし、Rubyの最短コードを見ると、

puts gets=~/C.*F/?:Yes: :No

というエレガントなコードが…コードゴルフしたい訳じゃないけどこれはスマートだ…精進せねば…

B - K個のケーキ / K Cakes

T種類のケーキが全部でK個あります。それぞれの種類のケーキの数も与えられます。 連続して同じ種類のケーキを食べないように、前日と同じ種類のケーキを食べ必要のある最小日数を考える…そんな感じの問題。

K 個のケーキがあります。高橋君は、1日に一つずつ、K 日かけてこれらのケーキを食べようと考えています。 ケーキはT 種類あり、種類i(1≦i≦T) のケーキはai 個あります。 二日連続で同じ種類のケーキを食べると飽きてしまうため、高橋君は、うまくケーキを食べる順番を決めて、前日と同じ種類のケーキを食べる日数を最小にしようと考えました。 高橋君のために前日と同じ種類のケーキを食べる日数の最小値を求めてください。

ここで完全に立ち止まってしまった。模範解答は以下。

max(at − 1 − (K − at), 0)

コードにすると以下のような感じ。

s=gets.to_i
a=gets.split.map(&:to_i).max
p [0,a*2-s-1].max

コードだけだとよく分からなそうですが、やってること自体は非常に単純で、 最も多い種類のケーキの数を2倍し、それから全ケーキ数を引き、さらに1を引く、というだけ。

最初に与えられるパラメータ(全ケーキ数、種類)と、各ケーキの中で最も多いケーキの数が分かれば求まりそう…というところまではいったものの、 どういう規則性があるのかが全く思い浮かばずに撃沈。最大のケーキ数とその次に多いケーキ数の差とか求めてたけど何に使うんだそれ…

が、この解答、考慮漏れのパターンがあるのでは…という疑問があったり。

例えば極端な場合、全ケーキ数が101、ケーキaが100個、ケーキbが1個の場合。 上記の解法で解くと答えは 98 になります。

しかし、この場合、

  1. ケーキaを50個連続で食べる
  2. ケーキbを1個食べる
  3. ケーキaをまた50個連続で食べる

にすると、前日と同じケーキを連続で食べる日数は49日で済むのでは?という疑問。

ACしてないクソザコナメクジが何言ってんだって感じですけど

感想

C以降とりあえず軽く見たものの、既に制限時間のほとんどをBに吸われた後だったので諦めました。

アルゴリズムというか、この手の論理的思考力が錆びつきまくりだなぁと痛感したので、 マメにAtCoderをやっていこうと思います。まずはAtCoder Beginner Contest(通称ABC)から。