fc2ブログ

スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。
  1. --/--/--(--) --:--:--|
  2. スポンサー広告

CodinGame HARD 後編

解き方思いつくと書かずにはいられなくなるこの中毒性からして、法規制もやむなしとする市民の声が多数上がっている。



Super Computer

科学者達から「何日から何日までスパコン使用したい」という申請が来るから、できるだけ多くの科学者に使わせてあげたいという問題。
もう普通に書くと大量データで死ぬのわかりきってるので、どうにか線形時間ぐらいで解けるようにしたい。

まず考えた方針。とりあえず貪欲法で受け入れられるだけ受け入れる。次に受け入れられなかった申請がどの受け入れ済み申請とバッティングしたのか記憶しておいて、各受け入れ済み申請についてもっと多くの申請を受け入れられないか探す。受け入れ申請が増えたら、またその申請について同じことを繰り返し細分化していく……

これでちょっと書き始めたが、どうも書くの面倒くさくなりそうなのですぐ諦めて考え直し。
要は申請を日付順ソートした上で、できるだけカレンダーの左側に詰めるようにしながらなめていけばいいんだ。
まず最大日数分の配列を確保して、申請の使用開始日と同じ要素番号の要素に使用日数を入れていく。開始日同じ申請が複数あれば、使用期間長い方は無価値なので無視する。
そして配列を走査して申請が見つかったら、その申請の使用開始日から使用終了日までの間で一番使用終了日が早い申請を探して受け入れる。使用終了日の翌日から走査を再開して以下繰り返し。

いやここまでする必要すらない。開始日ではなく終了日基準で考えるべきだ。
まず終了日を要素番号、要素を開始日にした配列を作る。そして配列走査して、直前に受け入れた申請の終了日より開始日が遅い申請だけ受け入れていく。

これでコードゴルフでもないのに10行未満で書けた。
完全にアルゴリズム思いつくか思いつかないかだけの問題だが、後から考えるとなんでこんな簡単なことをすぐ思いつかなかったんだと感じる不思議。



Roller Coaster

同じアトラクションにひたすら乗り続けるだけの人生を送る哀れな人々の問題。
1回1000万人乗れるコースターに平均5万人のグループが1000組並んでるから1日900万回運転して累計89兆7448億9256万5569人乗せるってどんな超銀河コースターだ。左に書いてある上限の数値超えてるんだけどいいのか。

最大1000グループしかないんだから、あるグループが先頭の時に乗れるグループ数と人数の組み合わせ1000パターンを先に計算しておけばいいんじゃんと思った。
これもさっきの問題と同じような感じで、思いつけば実装は簡単。

3つ目の実績は馬のやつと同じく言語指定。Bashはまだ触ったことあったが、clojureって聞いたこともない。そもそも関数型言語がわからんから概念から学ばなければ……。述語型言語で挫折した経験もあって手続き型言語以外は苦手意識強いわ。とりあえず後回し。



CGX Formatter

字句解析して見やすいよう整形する問題。
そんなにやること多くないのでif分岐で単純に実装していいでしょう。

提出用6番目のケースだけ手元のテストにないパターンらしく、95%で詰まる。
中身見れないので推測に手間取ったが、おそらくkey=value文の中に改行が入ってる場合、それ消して1行にしたものを出力しなければいけないということだと思う。
次の行の頭が括弧かスペースかタブのときだけ改行するようにしてクリア。



TAN Network

鉄道駅マップを距離付きのグラフ構造化して最短経路求める問題。
HARD1問目の迷路で作ったダイクストラメソッドに距離計算を加えるだけで解けるので楽ちん。

落とし穴として、度で与えられている緯度経度をラジアンに変換しないと、手元テストは解けるのに提出用の4つ目だけ解けない現象が起こる。これはフォーラム見ないと気づけなかった。



Genome Sequencing

与えられた遺伝子の重複したパターンを探してできるだけ短くなるようにくっつける問題。
今回はテストケースに大量データ問題がないので提出用も同じ感じだと信じ、全ての並べ方について虱潰しに調べる愚直メソッドで最短のパターンを探す。

並べ方を列挙したら、それぞれのパターンの接続部分がどれくらい埋められるか調べる。
まず遺伝子の先頭を合わせて、どちらか短い方の末尾まで全ての文字が一致しているか調べる。一致しなければ2つ目の遺伝子を1つ後ろにずらしながら同じ判定を繰り返し、一致したらその時の合成遺伝子を返す。2つ目の遺伝子がズレ過ぎて1つ目の外に飛び出したら単純に2つ並べたものが答えになる。
これなら2つ目が中に埋まっているようなパターンも問題なく調べられる。

パッと見ややこしくなったが全体としては難しい処理は含んでない。



Surface

提示された座標の属する湖の面積を求める問題。
面積調査を特に工夫のない単純探索でとりあえず実装したところ、60%でタイムアウトする。

一度調べた湖は何度も調べる必要が無いので、調査直後にもう一度同じ探索を行い、通った全てのマスに自分が属する湖の面積を覚えさせることで効率化を図る。
これで80%までいけたが、今度は再帰回数の限界に達したエラー出る。1万回弱程度しか潜れないのか。

今まで慣れてるからという理由で探索は全部深さ優先探索でやってたが、流石に今回は幅優先探索の方がいい案件だ。配列の要素は1億個弱ぐらい確保できるし。
探索メソッド書きなおしてクリア。



Bender - The Money Machine

相変わらず俗っぽいロボがお金をたくさん拾うための動作を決める問題。
ほぼTAN Networkから距離計算を省いただけで解けるし改めて書く意味がないぐらい。
架空のゴール部屋を用意して、出口は全部そこに繋がってるとすればいい感じ。



Bender - Algorithmic Complexity

計算量をオーダー記法で表す問題。この問題は多分厳密解というものが存在し得ないから、情報量が少ないケースだとどうしたって答えが出せなくなるし、しっくりくる解き方が思いつかない。

なんとなくそれっぽくなる法。
データの計算後の数値の中で最小と最大のものの比と、計算前の数値の中で最小と最大のものをnlognなどの式のnに実際に入れて計算したものの比を比較する。
桁数が一致するものがあればそのオーダーが答え。一致するものがなければ一致範囲を1桁増やして少しでも近い数値を探す。一致するものが複数ある時は、数値自体を比較してどっちがデータの値に近いかを判定する。

これで手元データはクリア、しかし提出用n^3で詰まる。
私は考えた。この問題には答えが8種類しかない。その防壁は薄絹の如くに脆弱にて、たとい提出用データの数値を隠匿するなどという卑劣極まる手段を用いようと、貴様に私の魔技ハードコーディングを阻止すること能わぬ。
こうしてn^3だけ当てはまるような細かい条件を追加して提出用もクリアした(?)

一応調べたらカーブフィッティングという専門研究があって、非線形最小二乗法なるものを使えばかなりの精度で近似できるらしい。





ここまで記録
Hard 100%Done
CodingPoints 7,969
GlobalRank 494/322,690
CountryRank 12/9,262
流石に真面目にやってる人多数圏内に入ってランクの上がりが鈍い。

後半に簡単な問題が固まってるのは気のせいではないと思う。
難易度に直結してるとは限らないけど解答の行数を多い順に並べると
APU>(300)>インディアナ>迷宮>(200)>対巨人軍>アンドロイド>爆弾魔>橋走破>(100)>ウィルス>湖面積>計算量>駅経路>(50)>字句整形>遺伝子>守銭ロボ>コースター>(10)>スパコン
と見事に前半後半に分かれるし。後半問題が前半問題の部分解だったりするし。



次は何をするか。
ベリハ1問目の任天堂提供問題の最後のテスト、書いたことないC++指定な上に、「リアルナード向け」とか不穏な言葉が見えて、既に上から順番にやって100%を目指すというモチベは失われている。

CLASH OF CODEはちょっとやってみたが、じっくり考えられないのは性に合わないからいまいち。
まず英語解読するのに時間かかる以上、英語圏の人と短時間コーディング勝負はとりわけ不利幅が大きすぎる。

BOT PROGRAMMINGやOPTIMIZATIONの方に手を出しつつベリハつまみ食いして、CP10000以上と国内総合ランク10位ぐらいを目標にするか。
スポンサーサイト



  1. 2016/02/05(金) 04:47:59|
  2. CodinGame
  3. | トラックバック:0
  4. | コメント:0

CodinGame HARD 前編

つづき



The Labyrinth

まず?マスのないマップを作成するために、前の問題のロボットみたいに行き当たりばったりに歩く。一度行ったマス目に来たら、バックトラックしながら行ったことのないマス目を探して歩く。燃料が少ない場合は効率のよい歩き方を考えなくてはいけないが、今回はとても使い切れないほど大量にあるので適当でもなんとかなる。
最初コントロールルームは無視しておいて、?マスもしくはまだ歩いてないマスがなくなった後で向かう。ここに入るとカウントダウンが始まるので、入り口までの最短距離を探索しないといけない。
各マス目に評価値を設定して、そのマス目までのより短いルートを見つけたら評価値を更新、それ以外は探索を打ち切ることで枝刈りするというダイクストラ? なんか違うような気もするけど多分ダイクストラだと思う感じのアルゴリズムを使ったら解けた。

提出用データでしか発生しないバグが生まれて困ったが、単に上下反転してるだけだったのでCUSTOMで再現してデバグしたら解決。
マップデータを配列に読み込む際、端っこは壁になってるから画面外に飛び出すかどうか気にしなくていいと思っていた処理部分で、よく見ると2つ目のケースだけ端っこが開いてるのが原因。上が開いてると出てくる配列の要素番号-1は、rubyの仕様上反対側の端っこと繋がるように使われるだけなのに対し、下が開いてると上限突破して落ちるというバグだった。



APU: Improvement Phase

とりあえず主な処理は以下

・確定判定:隣接ノードの持っているリンクの数から作成可能リンク数を計算し、それがナンバーと一致していれば全確定。ナンバーより1多ければ少なくとも1本は確定。
・仮置きフェイズ:隣接ノード数2の未確定ノードについて、作成可能リンク数1なら(01 10)、2なら(02 11 20)のように分岐させながら仮のリンクを作成して、その変化によって更にリンクが確定できるか確かめる。矛盾が発生したらバックトラック、矛盾はないが完成していなければ次のノードで更に仮置きして全体を走査する。
・ナンバー全消費時処理:自分と相手と自分の隣接ノードと相手の隣接ノードの隣接ノード数を減らす。自分から見て相手ノード、相手から見た自分ノード、自分の隣接ノードから見た自分、相手の隣接ノードから見た相手を削除。自分と相手にリンク情報を追加。
・交差判定:通ったグリッドの交点座標を全て保存しておいて、同じ所を通るリンクを作ろうとしたら失敗扱いとする。
・全接続判定:全リンク数が全ノードナンバー合計の半分になったら使用。1つのノードからリンクを辿って、通ったノードをリストに入れていく。リストサイズとノード全部の数が一致すれば解答成功。

ここまでで一応理論上は全部解ける状態ではあるがスコア70%弱。遅すぎる。

とりあえず全方向について考えてるのが悪い。
よく考えたら仮置きフェイズでは周り全部ノードの状況を気にする必要が無いし、左上から順番に辿っていけばリンク対象のノードは右と下だけに限定できる。というかmediumではそうなってたんだから素直にそれに従えばよかった。
これでCGとexpert除く85%までは到達。更に何らかの枝刈りが求められる。

・島発生判定:リンクを作成し尽くしたノード群が孤立したリンクを形成しているかどうかを、全接続判定でリンク作成するたび判定する。この処理自体が重いので使うと問題によっては逆に解けなくなる。
・下方向先取り判定:右方向にリンク作った時は直後で判定するので問題ないが、下方向のノードが消えた時、その先のノードで矛盾が発生するとしてもだいぶ後にならないとわからないので、先に判定してしまう。

この2つ合わせるとCGが解けるようになったのでそれなりの効果はあるようだが、Expertが強大すぎてもっと画期的なアイデアでないと意味がない。

交差判定を見直す。上記のだと次に交差してしまう線を引く時になるまで失敗しているかわからないので効率が悪そう。
まずノードがないグリッドの交点全てについて隣接ノードを保持したインスタンスを生成し、リンクを作成した時に通った交点の隣接ノードから見た隣接ノードを削除する。
更にその変化したノードについて確定判定を……と考えたがこれは1周回って処理中のノードに帰ってきてしまった時に割り込みが発生してバグの温床になったので取りやめ。
そこまでしなくてもこの処理は非常に強力で、提出用Expertの全体に確定判定を5回繰り返すだけで仮置きフェイズに入るまでもなく解けてしまう。どんどん壁が作られて自由を失っていくイメージ。

というわけでどうにか完成。これはすごい時間かかった……。STDERR.putsだとちょっと長くなると表示できなくなるから大量データのデバグは大変すぎる。仮置きリンクはデバグ用映像に出せないから宝の持ち腐れ状態だし。間違ったのを置いた瞬間エラー起こすんじゃなく、取り消しコマンドで消せれたりすればもうちょっと楽だったろう。



Skynet strikes back

今回は1つのノードから複数のゲートに繋がる箇所がある。余裕がある時はそこを切ればいいんだけど、単にエージェントから近い複数ゲート持ちノードを選んでも、最後のケースではうまいこと遠くに誘導されて失敗するように設定されてる。

まずエージェントから一番近いゲートを探し、すぐそこに迫っているなら即切断する。組合せ爆発しないよう3個ぐらい先を見れば十分。
余裕があるときは、さっき見つけた一番近いゲートへのリンクを仮切断した上で、更一番近いゲートに向かってエージェントを仮進行させる。
仮切断仮進行を繰り返し、初めてエージェントが複数ゲート持ちノードに仮到達した時、そこのリンクを真切断する。この繰り返しも4回ぐらいで十分。

前回の多重配列をクラスにして書き直したらめっちゃすっきりしたのもあり、かなり楽に書けた。



Skynet: The Bridge

EASYのが簡単すぎたのと入力形式も変わってるのとで初めてやるのと変わんない。

今回もさっきまでの問題と同じように、まずこのゲームのシミュレータを作り、暫定コマンドを適当に選んでシミュレートし、死んだらバックトラックして別のコマンドに変える、を繰り返せば良さそう。

ただし全員生き残るパターンを探す→無理なら多少犠牲が出るパターンを探す、ってやると全探索が含まれていて組合せ爆発起こしそうなので、ある程度の所で探索を打ち切る効率化は必要か。あと状況に合わせてコマンドの優先度を変えていったりとか……
……と考えていたが特に工夫なく組んだら3つ目の実績まであっさり取れたわ。



The Paranoid Android - One step further

これもこれまでのパターンからしてシミュレートで探索するところだが、問題が単純なのでそこまでしなくてもミディアムのに条件継ぎ足すほうが早いんじゃないかと思った。(同じ解き方するのに飽きてきた)

1-5.エレベーターがない階では作る
6.一番近いエレベーターを選ぶ
7.一番近いエレベーターが遠すぎる時は自分で作る(ステージの広さで「遠すぎる」の基準は変化)
8.ゴールまでの階数分エレベーター作成可能数が余ってる時は真下まで行って作る。重なってるエレベーターがある時は多少遠くてもそっちを選ぶ。
9.自分の真上にエレベーターがあるときは作る(作成可能数が余ってる場合)
10.ゴールの左右を走査、エレベーターがあったら下に降りるを繰り返し、通った地点におけるエレベーターの使用と建設を禁止する。

だいたいこんな感じで解けた。厳密解じゃないけど、タイトルの下に貪欲法って書いてあるから今回は近似解でもまあいいんじゃないかという解釈。



Indiana - Level 2

まずシミュレートでルートを探索するが、岩がいつどこから来るのか実際に岩が出現するまでわからないので、まだ回転方向のコマンドを決められない。どのマスを通るかだけを記録する。後ろに戻ることが出来ないゲームなので、探索効率化はそこまでしなくても大丈夫。マスごとに入った方向と出た方向の組み合わせ履歴を保存しておいて、同じ組み合わせが現れたらその先は調べないことにする程度。
始まったら通る予定のマスをどんどん通れるように回転させていく。直前になってから変えていたのでは、2回回転させるパターンが間に合わない。
更に余裕がある時は仮ターン進行させることで岩の様子を見て、一番最初に主人公にぶつかるであろう岩を探し、その岩の通り道のどこかのマスを回転させることで道を塞ぐ。

なんだか道作成処理と岩破壊処理の合流ポイントの部分が偶然解けているだけのような気もするが、例題の種類が少なくて正しさが確かめられない。ベリハへ課題持ち越し。

回転方向と進行方向の両方でLEFTとRIGHTがでてくるのややこしいと思った。clockwiseとcounterclockwiseなら……長いし余計わかりにくい。
あと1ターン目に入らないと主人公がどこから来るのかわからなくてシミュレーション開始できないのなんか気持ち悪い。



Thor VS Giants

今までで最もゲームっぽい。

毎度おなじみシミュレートして探索。EASYのがgiantの行動シミュレーションに使える……かと思いきや。
最も単純な実装ではまず斜め移動して軸を合わせてから直線で近付く形になるが、実際にはThorに対する角度が45度周辺の時は斜め、それ以外はまっすぐという感じに近づいてくる。更には重なってしまった時にどう動くかも考えなくてはいけなくて……。
この仕様詳細を左側の説明に書いてないのずるくないか。コーディングを楽しむという目的から外れてるというか。

どうも移動法を完全には調べきれなくて、若干シミュレートと実際の挙動が一致していないが、状況に応じてコマンド調べる優先度入れ替えたりしたら解けたのでそれで済ませた。ちょっと不完全燃焼。

移動法を考えなくてもいいように、giantに触れないように全giantの平均位置に向かって移動してある程度まとまったら攻撃、というシミュレートなし行き当たりばったり方針が推奨されているのか? でも最後の問題は行き詰まるような気がするな。

どうでもいいバグとして、方角を一文字目と最後の文字の切り出しで判断しようとすると、STRIKEのSとEが引っかかるという罠が。なんだこの単語チョイス。



Vox Codei

ボンバーマン。

まず全マスに仮仮爆弾を置いてみて、爆発した時に破壊されるブロックの数を計算する。一番多かったマスを仮爆発させたという体で、更に仮仮爆弾により次の仮爆弾の位置を探すことを繰り返し、ブロックがなくなったら成功として実爆弾設置作業に入る。
失敗した時は1つ目に置いた仮想爆弾の位置を覚えておいて、その場所は選ばないようにまた同じ処理を繰り返す。
実爆弾は3ターン後に爆発するようにして、置きたい場所のブロックがまだ破壊されていなかったら、WAITしてその爆弾設置は後回しにする。

連鎖爆破させないと間に合わない問題とかがあるときつかったところだが、今回はラウンド数設定がガバガバだったので簡単だった。ベリハにはありそう。





ここまで記録
Hard 50%Done
CodingPoints 5,569
GlobalRank 951/313,638
CountryRank 24/9,148

HARDは最初問題見た時はウワッとなるが、ウンウン唸って考えると光明が見えて、試行錯誤続ければ正解に辿りつけたりつけなかったりする、個人的にかなり心地いい難易度と感じる。
今のところ迷路と経路探索とバックトラッキングばかりなので違うタイプの問題もやりたい。後半はパッと見た感じ色々ありそうだから期待。
  1. 2016/01/28(木) 05:09:21|
  2. CodinGame
  3. | トラックバック:0
  4. | コメント:0

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
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。