2014年03月19日

AtCoder Beginner Contest #003 に挑戦

夜中にAtCoder Beginner Contest #003 の問題を解いていったので、とりあえずまとめ。
ちなみに自分の解答はこちら(ABC

A - AtCoder社の給料
〜Salaryが0なんてつらい〜


サブタイトルはあれだ、変数名だ。
int salary = 0; とか いろんないみで、勘弁してください……w

さて、コード見ましょう。

まあ、シンプルですよね。全部足して、Nで割ればなんとかなりました。「結合法則」っちゅーやつですっけ。

B - AtCoderトランプ
〜if文に要注意〜


もう、これは先にコード見よう。

これ、「何をすればいいか」は分かっていたものの、いろいろと罠に引っかかってました(罠というか、自分で置いた石というか……)
とりあえず! 何をすればいいか!
たとえば……
S:d@hl@a
T:d@hli@
この二つの文字列が与えられたとします。
SとTの文字列を頭から一つずつ確認(Sの一文字目とTの一文字目、Sの二文字目とTの二文字目……Sの最後の文字とTの最後の文字)すると、以下の3つのどれかが起きるはず!(SとTに与えられる文字列は同じ文字数なのは保証されているので)

@比較した文字に@が含まれていたとき
A比較した文字が同じだったとき
B比較した文字が違うとき

それぞれの場合について考えてみましょう!

@比較した文字に@が含まれていたとき
たとえばさっきの例だと2文字目、5文字目、6文字目が該当しますね!
まず、2文字目を考えてみます。
2文字目はSもTも「@」なので、"a","t","c","o","d","e","r" のなかの、どの文字を入れても負けフラグは立ちませんね。
ただし、同じ文字を入れないとダメですが。たとえばSの2文字目に"a"、Tの2文字目に"t"とかしちゃうと負けちゃいますよね。けど、今回は「このゲームで勝つことができるかどうかを判定するプログラム」なので、気にしないことにします。
続いて5文字目。
Sは"@"ですが、Tは"i"という文字が入っています。
Sを"a","t","c","o","d","e","r" のなかの、どの文字に変更しても、同じ文字にはなりません。
ということは、先ほどの例は「負け」なんですね!
ここから、もし片方だけ"@"だったら、もう片方の文字が"a","t","c","o","d","e","r"のどれかに該当するかを調べれば良い、該当すればまだ勝ち目はある、該当しなかったらその時点で負けフラグが立つので、それ以降の文字列については調べる必要がない、ということがわかりました。
なので、さっきの例はもう6文字目について検討する必要はありません……が、練習のために一応検証してみましょう。
6文字目。
Sには"a"、Tには"@"という文字があります。
"@"を"a"という文字に変えることができればOKですね。ちゃーんと"a","t","c","o","d","e","r" という7つの文字の中に"a"は含まれているので、これだけをみたら負けフラグは立ちませんね。

A比較した文字が同じだったとき
同じだったらそれでええやん。何もいじる必要はなし。
と言うことで、この時点(さっきの例で行くと1文字目、3文字目、4文字目)では負けフラグは立ちません。

B比較した文字が違うとき
これを見つけた瞬間負けフラグが立ちます。
だって、変えようがないじゃないですか!

ここまで分かったらコードを書いてみましょう……が、なかなか上手くいきませんでした。
まず、「もし片方だけ"@"だったら、もう片方の文字が"a","t","c","o","d","e","r"のどれかに該当するかを調べれば良い」をどうやって書けばいいか分からなかった!
結局、"a","t","c","o","d","e","r"という文字を一つずつリストに突っ込んで、もう片方の文字が該当するか。contains使って入ってるか調べてもらいました。
あと、if文がごちゃごちゃしたり、SとTの両方の同じところに"@"が入ることを考えてなかったり、負けフラグがたった時点でfor文を抜けないといけないということを忘れていて「あっれー、負けフラグ立たねぇ」となってたり、「どちらも@じゃないけど、比較した文字が同じだった場合」を考えてなかったがためにif文に入ってくれなかったり、いろいろでした(´・ω・`) ちゃんと整理して書き出した方がいいと改めて学びました。
これはもう少し勉強して、もっとかっこよくわかりやすく書けるよう練習したいところです。

C - AtCoderプログラミング講座
〜例示は理解の試金石、ふたたび〜


これはためしてみたほうがはやい!
たとえば。
1から10までの数字のなかから、3つ選んで合計をだしますよ、というときに、一番大きくなる選び方はどれ? と言われたら、大きい順に並べて前から3つ(つまり8、9、10の3つ)を選びますよね。
で、問題を読むとこう書いてあります。
「高橋くんのレートが C の時に、レート R の競技プログラマーの講座動画を見ると、高橋くんのレートは (C+R)⁄2 に変化します。」
ということは……
レートA、レートB、レートCの3つの動画を、A→B→Cの順番で見よう! と決めたとき、レートがどうなるかというと。
Aの動画を見たとき:A/2
Bの動画を見たとき:( A/2 + B ) / 2 = A/4 + B/2
Cの動画を見たとき:( A/4 + B/2 + C ) / 2= A/8 + B/4 + C/2
これから分かることといえば、Cが一番大きいまま残る、Aが一番小さくされてしまう……ということは! Cに一番大きい数字を持ってきて、Aに一番小さい数字を持ってくれば、最大効率が出せるんじゃね? と。
さらに言うと、レートが低い順に見れば、最大効率が出せる、と。
ここまで決まれば、後はコードを書くだけです!

ArrayListを二回使ってしまったのが心残りですが、まあとりあえず、動いたし……。さすがにこれはもっと綺麗に書ける気がする。
あと、collection.sortってのを覚えたのでひとつかしこくなりました。

まとめ


・さきにちゃんと「どう組むか」を考えよう
・collection.sort 便利
・if文書くときには注意セヨ
・半分眠りながらコード書くな
タグ:JAVA
posted by Dahlia* at 09:20| Comment(0) | 競技プログラミング
この記事へのコメント
コメントを書く
お名前:

メールアドレス:

ホームページアドレス:

コメント: