FC2ブログ

codingame mediumまで攻略メモや感想など

初心者の練習用にいいと聞いてやったら見事にハマったので記録残しておく。
なんとなく楽そうだからrubyでやるよ。



Tutorial

Onboarding

15種類の言語でクリアすると130CPもらえるのでやっとく。条件分岐と変数出力の仕様についてググるだけ。
Bash,C,C#,C++,F#,Java,Javascript,Lua,PHP,Pascal,Perl,Python,Python3,Ruby,Scalaでやった。



Easy

Power of Thor

せっかくRubyなのでコードゴルフにも挑戦してみる。変態仕様の一覧が欲しい。
・STDOUT.sync = trueはなんか知らんけどなくても動く
・splitは引数なくてもデフォルトでスペース区切り
・collectよりmap
・{|x| xなんたら}より{&:なんたら}
・loop do よりloop{}
・remaining_turnsは使わない
・"a"より?a
・ifより三項演算子もしくは||文
・比較演算子を使う
あと今回のテストケース限定の反則技として
・北に行く必要がないのでNを出力する処理を省ける
・東西方向で途中で止まる必要がないので現在地xを更新する処理を省ける
これで現状84byteの日本ランク3位。世界ランク1位は更にこの半分なのでなんか根本的に発想が違う気がする。入力を数値で受け取ってループ中に空文字出力するだけでも44byte使っちゃってるもん。

Horse-racing Duals

ソートしてから前後だけ比べて解いた。
問題は三つ目の実績がBashでないと取れないこと。そしてBashには組み込みのソートがないから外部コマンドのsortを使わざるをえないんだけど、これが遅くて99999個のソートが出来ないので、最後のケースでタイムアウトする。
しかしよく見ると99999個のケースは最初から降順ソートされている……。場合分けして最後だけソートしないことで解決。これでいいのか。
それにしても変数を数値参照するときはいちいち$つけるとか面倒すぎるので言語指定もう勘弁して欲しい。


Medium

APU: Init Phase

凝ったCG使ってるからすごいゲームかと思ったら決められた通り線を繋ぐだけという。

Skynet: the Virus

再帰でagentからgatewayまでの最短経路探索してgatewayに近いラインを切断するようにした。
しかし無計画に書いたのでごちゃごちゃしてる。現状ノードを多重配列に保存して、次のノードを探索するときは配列のクローンからノードを一つ削除したものを再帰用関数に渡してるけど、もうちょっとすっきり書けそう?
タイムアウトするから処理効率悪いのかと思ったら、デバグ用STDERR.putsを置きすぎていただけだったということがあった。意外と表示系重い。

3つ目の実績は余裕があるときにagentの近くを切ればいけそうだけど、もうめんどくさくなったのでランダムに切るようにして何回か提出したら成功した。HARDにも出てくるので後でちゃんと考える。

Winamax Sponsored Challenge

英語が読めなくてwikipedia-戦争(トランプ)の変則ルールの4つ目を採用してるということに気付くのに時間がかかった。
ところでこのゲーム技術の介在する余地が1ミリもない純粋な運ゲーでつまんなそう。

Heat Detector

二分探索する。
最後の距離10000ターン数15のケースは、2の15乗が32768だから余裕で間に合うはずなんだけど、なぜかあと一歩の所で時間切れになる。最初の1ジャンプが大きいと爆弾が初期位置の近くに、小さいと遠くになるようないじわる設定が関係しているような気がする。
なんとなく1.99分探索にしたら成功したのでそれで済ませた。もう少し厳密には1.99064から1.97619の間だけ成功する。

Mars Lander - Level 2

これがミディアムで一番難しいと思うというか、これだけリアルタイム物理演算入るから毛色が違う。
手元のテストと提出用テストが同じなので、燃料の量でステージ判定して決められた動きするだけのスーパーハードコーディングでクリアした。やわらかコーディングは多分ベリハに到達できたら考える、かも。

The Paranoid Android

なんだか仰々しいけど、前にエレベーターか出口がない時は停止すればいいだけという単純な問題。Skynet: the Virusがぐちゃぐちゃした反省を踏まえてちゃんとHARD用のクラス分けしといた。

これのoptimizationは
・STDINより$>
・pushより<<
・”abc”より:abc
・配列を普通の変数で受け取ると勝手に配列になる
・.map{&:to_i}は12文字もあるので都度to_iの方がいい時も
・to_iが1文に2回出てくるならいっそ文字列化してからevalで強引に数字に戻した方がいいかも
・エレベーターとゴールを一緒くたに扱う
これでで168byteの日本ランク1位取れたが、世界1位は1問目と同じぐらいだし、もっと削る余地はありそうではある。

Teads Sponsored Challenge

少し考えた結果、端から端までを全ルート探索して、一番長いルートの半分の切り上げが答えになるというところまでたどり着いた。しかしイテレータを二重にぶん回してたのでノード数万超えのケースで詰まった。
最長経路探索問題って難しいんじゃなかったかなあなどと思ったが、処理削るリスト構造思いついたらあっさり高速化して解決。

Indiana - Level 1

綺麗にクラス分け出来たと思うし、ほぼバグ無しで通った。おそらくlevel2も安心。

Stock Exchange Losses

これも最初全ケース2重走査してたので大量データで死んだ。買うのは高値更新してる時だけ、売るのは安値更新してる時だけにすれば走査1回で済むとうことに気づくかどうか。

Network Cabling

自由度高い最短経路探索かと一瞬身構えるも、横ケーブルが1本しかないので実際簡単。
仮に横ケーブル引いて、その都度縦ケーブル長を計算してから二分探索していく形でできた。しかしどうもそんなことしなくても全体の平均値に一番近い家を通る所に引けばそれでいいらしい。

Conway Sequence

特にテクニックはなくそのまま実装するだけ。頭だけで考えるとこんがらがる。

Telephone Numbers

Teads Sponsored Challengeに自分でノード生成するステップ加えたようなもので解けた。

Dwarfs standing on the shoulders of giants

単方向リストなのでSkynet: the Virusからノード削除を省いて単純化したようなもので解けた。

Bender, a depressed robot

ちょっとやることが多いが特に問題なし。
ループ判定は各マス通るたびにロボの状態を保存しておいて、以前のものと一致してるか判定するのが厳密だが、面倒なので10000ターン以上経ったらループしているということにした。昔のアーケードゲームに出てくる「永久パターン防止キャラ」なるものはこんなんだし、まあいいでしょう。

Scrabble

ルールが良くわからない。同じ文字を2回使ったらダメというルールで作ったら提出用ケースは100%になったが、手元の5番目の答えはtweenなので失敗する謎。

The Gift

人によって荷物を持てる量が違って、あんまり一人に多くの荷物をもたせるのはかわいそうみたいなことだと思う。
最大積載量小さい順にソートして、トランプのディールみたいに1つずつ配る。すると同じ最大積載量の中では前の人の方が多く持ってる状態になってるので、現在積載量順にソートしてから出力すると答えになった。

Mayan Calculation

読み込んで変換して計算して変換してって色々やる。ローマ数字なんかだともっとややこしくなところ、ゼロがあるおかげでアラビア数字と互換性が高くなってるマヤ文明に感謝。(ただ厳密にはこれ位区切り用の文字でゼロと言い切れないらしい)
多重配列の縦横がどっちがどっちだかよく混乱するが、今回は方言のケースまでほぼバグ無しで通ったので気持ちよかった。



そして今HARD中。流石に歯ごたえ出てくるしまあじっくり進める。
スポンサーサイト



  1. 2016/01/11(月) 06:17:35|
  2. CodinGame
  3. | トラックバック:0
  4. | コメント:0