AtCoder Beginners Selection も中盤に差し掛かっている

-

何か書く暇もなく問題解いてた


現状がこちらとなります。このAtCoder Beginners Selectionは、過去問の中でも特に初心者学習に最適なものを10個選び揃えたものだそうで、私は今6問目に進んでいます。
他にも開発環境構築したりコンテストに初参加したりと色々下書きを溜めているのですが、何か書ききる前に書くことが出てきちゃうんですよね。

というわけで、AtCoder Beginners Selection第6問、ABC088B - Card Game for Twoをやっていきます。


ぱっと見た所感としては、多分奇数偶数を使って解く問題なんじゃないかなあ、と。
奇数番目に大きな数が書かれたカードをAliceが、偶数番目に大きな数が書かれたカードをBobが取るわけで、後はAliceが取ったカードの和からBobが取ったカードの和を引けば答えが出るのではと思いました。

というわけでそのセンでコーディングします。
しかしまあ困るのが「奇数番目/偶数番目に大きな数」というのをどう判別するかなんですよね。
とりあえず降順に並べたら何とかなるかなあ、と思いつつソートについてググったところ、私にはまだ理解の及ばないアルゴリズムが色々とあったので、速度は遅いが最も実装が容易そうなバブルソートを採用することとしました。

やたらテンプレが転がっていたのでコピペした方が早かったのですが、流石に仕組みは知っておかなければ意味がないと思い、自力でバブルソートを組むことを試みました。組めたけど一時間半かかった……。



仕組みは完全に理解したので今後はコピペします。

で、まあ降順でバブルソートできたらもう楽勝ですね。
array[0], array[2], array[4], ... ,array[2n]
の配列に格納されている値がAliceの取るカードの値、
array[1], array[3], array[5], ... ,array[2n+1]
奇数の配列に格納されている値がBobの値となります。

で、あとはsumって引くだけです。


こんな感じで。


対戦ありがとうございました！！！！！！！！！！バブルソートに時間食われすぎたね！！！！！！！！！

コメント

コメントを投稿

このブログの人気の投稿

そして三ヶ月が経った――書くの面倒だっただけでちょっとは進捗あったんだよ――

-
久しぶり 本当に久しぶりである。なつキチである。 別にプログラミングをサボっていたわけではない。勉強頻度が下がったことは否めないが、ABCでC問題まではわりかし解けるようになった。二問に一問程度はC問題を解けるようになったのでこれは成長といっても過言ではないだろう(罠で、DFSやBFS等の基本的アルゴリズムを全く理解していないのでほぼ弱いままである)。 まあぐだぐだしながら40分でC問題まで行けるようになったのでこれからも頑張りたい。だがD問題が分からないので死にそうである。D問題から数学ゲーになってくるよな？(センター数学五割マン) さて本題であるが、今回アプリ開発をしたいなあと思い、発想を膨らませるメモ書きを兼ねてこのブログを書いている。JavaもC#も出来ねえぞ、オブジェクト指向マジイミフとかそんな話はまあ置いておいて、ともかく実装したい機能とテーマを書き付けたい次第だ。 Q. 何を作りたいんですか？ A. デートコース管理アプリかな 「またコイツ彼女いるアピールしようとしてるよ」とか聞こえてきそうであるが、別にそういうわけではない。いや実際あれば便利だよねというか、実際友達との遊びの予定を決めるのにも使えるし、何かと欲しい。というわけで、漠然としたイメージを考えてみる。 カレンダー機能 スケジューラ機能 リマインド機能 まあ必須。イメージとしてはカレンダーの各日付をタップすると、スケジューラが出てくるという感じだろう。リマインドは分単位で出来ればそれで良い。そして機能のメインはスケジューラになると考えられるので、その機能をさらに考える。 スケジューラの機能：場所と時間 遊ぶ場所とそこに滞在する時間を登録出来るようにする。位置データを登録しておいてワンタップでそこの地図が出るようにしたい(Google Mapかな)。そこに行くまでの時間を逆算して、出発するべき時間に通知を出せればなお良い。 また、例えば環状線で大阪巡りをする時なんかは、何時にお店を出れば良いとか、どの電車に乗ればいいかとかをいちいち検索するのが面倒なので、一日全体のマップスケジューリングが出来れば最高。ただその場合、どの交通機関で行くのかとかを事前にこまごまと選んでもらう必要はあるけれど。 スケジューラの機能：場所の検索機能...
続きを読む

AtCoder Beginners Selection に参加する～第四問が解けない～

-
イメージ
頑張るぞい 今の私にぴったりというか、ニーズにドンピシャのアレ (AtCoder Beginners Selection - AtCoder Beginners Selection | AtCoder - https://goo.gl/7C8JdP)があったので挑戦してみます。 参加ァ！！！ 一問目はプラクティスで解いたことがあったので二問目へ。 これはサクッとACできました。嬉しい。 三問目もサクッとできた――と思ったんだけれども、どうにも挙動が怪しい。文字列と数字を混同していたために上手くいかなかったようでした。 しかしそれに気付いて無事にAC。 さて、問題は四問目から。 ここからはB問題となるわけです。 プロならば目を瞑っていても解けるでしょうが、私はビギナー、既にいっぱいいっぱいとなっています。 問題は以下。 少しだけですが数学色が出てきやがりました。 別に小学生でも解けるような問題だろって？ 確かにそうですね。しかしあなたは私が小学生以下の知能しかないということを見落としています。 「まあ何かアレでしょ、2使って 素因数分解っぽい何か をすればいいんでしょ？」 と、数学を理解している方から参考書で 撲殺 されそうなことを考えながら論理を組み立てるのが私です。恐れ入ったか？　震えて眠れ。 まあパッと見で繰り返しとif文を使うんだろうなぁと思いつつ、とりあえず脳死でscanf関数をカキカキしようとして、幾つ変数を用意すれば良いんだろうと困りました。改めて問題を見るとそこには 1<=N<=200 の記載が。 ここでなつきちの脳裏に電流。「こういう時は配列を使えばいい」――そんなワードが思考の海から浮かび上がりました。 正しくそれは天啓。 「あっこれ進研ゼミで(ry」と叫びたくなる某漫画の主人公の気持ちがとてもとてもよく分かりました。 ニヤニヤ笑いで int a[200]; と宣言してやりました。 ちゃんとべんつよが身に着いていてなつきち素直に感涙です。（自分を褒めないとモチベが保てない系の人間です） 基本中の基本だろって？　それ is そう。でもググらずに思い出せたの褒めて。 さて、自分ageはここまでにして更に考察を進めていきます。 この問題を解くにあたって必要な...
続きを読む

どうも第四問を解くには色々べんつよが必要らしいのでべんつよする

-
イメージ
べんつよたのしい（おめめぐるぐる） というわけでぽはようございます。なつきちです。 前回詰まってたAtCoder Beginners Selection の第四問について、偉大なるC言語学習サイト（苦しんで覚えるC言語 - https://goo.gl/XVKYuJ）に助けを求めたところ、動的配列なるものに行き着きました。 そしてそれを理解するためには今まで避けていた悪名高きポインタの理解が必要だったので、頑張っておべんつよしていました。 おかげでポインタ半分くらい理解した（ほんまか？） まあぶっちゃけおべんつよして分かったこととか中国幼女定理さん（ @littlegirl0820 ）からいただいた助言とかで、「別にmalloc関数使わなくてもよくね？」と気付いたのですが、知識を深められたので良しとします。 さて、中国幼女定理さんのご助言によってFor 文を組み合わせれば任意の配列を入力できる（見てそりゃそうだなってなった）ということに気付いたので、カキカキします。 まあこんな感じでしょう（よく見るとscanf関数の中で"n"に&をつけていませんが）。変数宣言が幼稚なのも許してください。まだ幼いのです。 続いて前回考察したことを実装します。偶数かどうか確認してから割っていくというアレですね。 ただこの問題は「入力された 整数全てを2 で割ったものに置き換える 」ことを1セットとした上で、それが何セット繰り返せるのかを出力する必要があります。従ってカウント方法に気をつけなければならないんですよね。 流れとしては こんな感じにすればいいのかな？ 奇数偶数を判定するにも、2で割るにも、この工程そのものをループするにも繰り返しを使うので、繰り返しの入れ子構造になりそうですね。 こうなると関数のモジュール化をした方がいい気がしてきたので、ググりつつ進めます。 ――が、よくわからず混乱したので脳筋ゴリラの如くmain関数1つでごり押しすることに。 奇数が出る度に変数を++し、ループ終了後にその変数をチェックすることによって「全て偶数であるか」を判定します。 色々不備はあるだろうけどとりあえずこれで。 で、...
続きを読む