fc2ブログ

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
<<16春Me: | ホーム | CodinGame HARD 前編>>

コメント

コメントの投稿

管理者にだけ表示を許可する

トラックバック

トラックバックURLはこちら
http://pseudonym.blog94.fc2.com/tb.php/1069-b71ad6fe
この記事にトラックバックする(FC2ブログユーザー)