問題文:https://www.codeeval.com/browse/219/

概要

  • 探偵が複数の都市を全て回るとき、その距離の合計値の最小を出力する問題。
  • こう書くと、巡回セールスマン問題だと思いたいですが、なんと、 最小全域木 問題である。やばくないですか。問題文ではHeと 単数形 で書かれていますが…分身できるんですか。
  • 普通にクラスカル法で解けば良いのでその部分の解説は他に譲ります。もしくは私の解答集を見ても。

注意点

  • Falseを出力すべきなのは、
    • グラフが連結でない場合
    • グラフに示されていない点が存在する場合
  • である。たとえば、1 2 1 | 2 4 1の答えは、2ではなくFalseである。つまり、点番号を詰める必要はないということ。
  • 多重辺を持つ場合、 一番後ろの辺を採用 する。例えば、1 2 1 | 2 1 2の場合、点1と点2の間にコスト2の無向辺を張る。

まとめ

記憶が残っている内に参加記を書いておくことにした。

予選

  • A: D問題、65分で書き終わったが、2分探索がオーバーフローしているのに気付かず、109分でAC。129位。ぎりぎり通過。
  • B: 範囲結合で行けると思ったが、微妙にバグらせて、113分でAC。ただ、予選Bは全完が少なかったので、58位。

木曜〜金曜

短縮王、あなごるにて、とりあえず充足解を出したあと、適当にクロック数を減らす。 一方、Union-Findは再帰しない答案が通ってしまったが、本番で通らないとまずいので、最初の答案は残しておいた。

1日目

  • 9:30起床、初のCodeIQパーカーを来て出発。コンビニでおにぎりを買って食べる。こどふぇすで出るおにぎりだけではもたないことがわかっていたので。
    • 去年は(おにぎりが出るのを知らずに)御茶ノ水の日高屋で食べたが、六本木一丁目ではそういうことはできそうにない。
  • 会場で、スタンプラリーを見て戦慄する。適当に参加すれば12〜3個は取れるが、スケジュールが重なっているため、15個取るにはフル参加がほぼ必須である。

本選

  • スタンプ1
  • パーカーボーダーが6問から5問に減ったと知って喜んだが、その分難易度が左に一個ずれただけなのではという危惧を抱く。
  • ネットワークの不具合でやる気の大半が削がれる。Empire of Codeやったり。コード川柳のネタが生える(※1)。
時間 言語 問題(A-J) コメント
44秒 Ruby A ACa[0].size==5&&a[1].size==7&&a[2].size==5というくそコードを生み出す。gets.split.map(&:size)==[5,7,5]とタイプしていたらFAだった。
0:03 Ruby B [*2..6*N]の中央値でしょ -> WA。焦る。
0:09 Ruby C そのまま置けるときは置く、そうでない場合分解が必要かどうか判断する貪欲法。 AC
0:16 Ruby E 適当に置換 WA
0:20 Ruby E WA
0:25 Ruby B N=1の処理を追加するも WA
0:30 Ruby D 最大被覆-1 WA。rprocon 2013FでnCrの計算式を間違えたり、code festival 2015予選A Dで2分探索がオーバーフローしたりとRHDコンテストには魔が潜む、その魔に今回も喰われるのか。2問で終わるのか。 激しく焦る。胸が痛む。
0:33 Python B N〜N*6の確率を全部求め、その最大を答えるという酷い実装。CheckiO probably-diceをコピった。 AC
0:54 Ruby E 2**3通り、-10〜10に対しシミュレーションする。WA
0:55 Ruby E WA
0:57 Ruby E 探索部分のバグを修正成功。 AC
1:20 Ruby D 謎なDFSを生やす。WA
1:38 C++ D 使わないボタンを1個決めて、それぞれに対し最大被覆を計算すれば良いことはわかるんですよ。O(nm)の定数倍で通そうとする無茶。TLE
1:51 C++ D 手持ちのRMQで殴る。rmq=imos(notes);print min(max(rmq.query(1,e.first),rmq.query(e.first,e.second)-1,rmq.query(e.second,10**5+1)) for e in notes)AC パーカー確定胸の痛み、収束する。 かなりやばい。提供されたおにぎりを食べる。
F〜J 読んだけど方針すら立たない
2:16 Ruby B 普通の解き方でAC
3:00 116位。仕方がない。パーカーで良しとします。ところで、今年はパーカーが159着出ました。去年の54着に比べるとかなりの大盤振る舞いありがとうございます。

夕方

  • スケジュールが遅延するも、短縮王の本番環境は予定通り16時に開く。解説を聞きながら適当に通す。Bが通らずやばい。とりあえずC++版を送る。ACDはRuby版とC版を送る。
  • スタンプ2: タイピングをやる。残り40体ぐらいで死ぬ。終。
  • スタンプ3: ボードゲームをやる。面子みたいなやつ。ビア&プレッツェルというらしい。適当にやったら1位だったみたい。終。
  • スタンプ4: akensho氏トークライブ。AtCoderの裏側をいろいろ聞けてよかった。
  • スタンプ5: 問題解説のスタンプを押し忘れたので戻る。
  • スタンプ6: 太鼓の達人。天下一音ゲ祭2014課題曲であるきたさいたま2000は去年やったので、今年は夏祭り(普)。太鼓の反応悪くないですか。終。
  • スタンプ7: DDR。Mickey Mouse March。ランクSSSらしい。終。ランカーのプレイは見ずに出る。
    • どちらも去年と同じマシンなのかな。来年はぜひ新筐体で。DDRにセツナトリップが入ってないというツイートも見かけましたので、ぜひよろしく。
  • にぎり鮨を5分で流しこむ。 全く味わっていない。
    • でもまあ、太鼓とDDRをやりに行ったからこそ主食締め切りに気づきました。告知が遅かった印象。もし食事を得られていなかったらと思うと悪寒が。
  • スタンプ8: LayCurse氏トークライブ。ネタ帳大事ですね。あと、細かいポイントのくだり、全部飛ばされたので、Advent Calendar参加を増やすかどうか怪しいです。現状判断できかねますので、スライド公開お願いします。
  • コード川柳、できたので投稿。「RE テストケースを 推測だ」今思えば「コーナーケース」のほうが良かったかもしれないが、まあ、表彰とか考えてませんので、これでよし。ちなみに会期中ハッシュタグ検索使ってません。
  • スタンプ9: 書道コーディング。(※1)をこちらに消費することに決定(プログラミングあるあるとは少し違うというのもあり)。「回線が 落ちてつらみの Festival」だってFestivalって楽しむものよね??
  • スタンプ10/11: コード川柳・短縮王のスタンプをもらう。ステッカーとバッジをもらう。
  • スタンプ12: エキシビション観戦。
  • 生春巻き・ソースやきそば・おでんを自分の席で食す。 味わえた。
  • エキシビション、去年より難易度上がってませんか。解説聞いても解けるか怪しい。あと短縮王B、C言語版通った。
  • あさプロ難易度ボーダーが50位/150位から30位/100位に変更。Easy出るお^ω^

  • 起床フェーズがやばいことは明白だったので、今年も宿泊希望。品川プリンスホテル。
  • アミューズメントアイランドセガ、行ってみたが、22時閉店だったっぽい。戦慄を感じる。
  • 0時まで短縮王で寿命を縮める。
  • 本選D・E、想定解法で通す。 それぞれ233Bytes、115Bytes。 びっくり。
  • 本選HをC++で通す。main関数自体は18行。解説の凄さを感じた。
  • yukicoder No.302を通す。
  • 狭い湯船 に浸かり、就寝

2日目

  • 7:10起床。AC。

あさプロ

  • スタンプ13
時間 言語 問題(A-H) コメント
52秒 Ruby A Math.sqrt(n).to_i!=n TLE。今思えば最低ですが、この時は仕方がない。
0:03 Ruby B 2つに分けて、ハミング距離。 AC
0:07 Ruby A (1..100).map{e e**2}.bsearch{e e>=n}-n。頭がおかしいですが、やむをえません。 AC
0:10 Ruby C ソートして、上位K個の和が既にR*Kを越えているか、または下を1個減らしたときに足すべき値は何か。WA。焦る。
0:11 Ruby C N==1の時、reduce(:+)はnilになる。(0,:+)。WA
0:13 Ruby C N==Kの時、a[0,K]の要素数はKではなくK-1。下を1個減らす必要はない。 AC
0:20あたり C D lcsを試すも、サンプルが通らない。スコア計算関数を修正。まだ通らない。切断位置はN/2である必要はないのか。じゃあB問題と違ってN%2の場合分けも要らないな。
0:32 C D AC Easy順位確定。7位。
1:08 Ruby E 左右に分けて、sum((i+1)*a[i]+1 for i in range(N))。サンプル合わず。
1:15 Ruby G 各数字の前で切ってソートすればいいんじゃね->… 1 2 9 3 …で他の部分を切ってしまい2と9を切らない。間違えました、はい。ソース破棄。
1:21 Ruby F 高さでソートして貪欲。O(K)。TLE。ちなみにO(N)の答案を書いてわかりましたがこの解法は嘘解法でした。
1:30 Middleは77位。3問解きたかったね。仕方ないね。
  • スタンプ14: 入賞。タンブラー先着順に関してしか利益がないので、うーむ。

  • あさプロE 左右にわけられるのは白石の場所のみ。サンプルは通った。しかしTLE。
  • 今半すき焼き弁当。 味わえました。
  • スタンプ15: chokudai氏トークライブ。そんなにアルゴリズムぽんぽん出てきませんToT
  • タンブラー引き換え。 よかった´ω`
  • shinh氏トークライブ。私のコード紹介ありがとうございます。詰めが甘くてすみません。
  • なんか係の人が忙しそうだったのでスタンプはいいやと。
    • ただ、本当は、こういうことを思わせた時点でアウトではある。

早解きリレー

  • ゼッケン、去年はアルファベットだけど、今年整数だ。問題番号なのか解く順番なのかわからないっす。
  • 順位順で、普通にEを担当。実装は2問目。
  • 最初、すぐに反転させれば良いと勘違いしてWA。「解けそうだ」とか言ってすみません。h<=6やm<=30のときは待ってから反転させることで0にできますね。AC。途中で戻らずにすみました。
  • ちなみに解いた順番の関係でEはFAらしい。
  • 他は見てるだけになってしまった感が。申し訳ない…

ハッピーアワー

  • 本来の趣旨から少し外れ、コンテンツ表彰の前の短い歓談時間的扱いになった気がしますが、仕方ないかなと。
  • 短縮王は、総合2位、しかたないねToT
  • コード川柳、kyudenamida氏、「もっと真面目な川柳にいいねするべき」とのことでしたが、Twitterの性質上やむを得ないのかも。

帰路

  • 電車の中であさプロE AC。sum((i+1)*a[i]+1 for i in range(N))は2段階の和で表せるので、DP可能。
  • リレーの問題、通して見ましたが、CとかDとかFとか本番中に解ける気がしない。G・Hなら解けるけど。てかこの問題セットだと思考停止状態で解けるのはB・G・Hだけですわ。Eも考察が必要ですが少しだけなので。E担当でよかった´ω`

まとめ

  • 1日目夕方を見れば分かる通り、とてつもなくタイトでした。食事を味わえなかったのも残念。
  • トークライブ途中退室を推奨しているかのような印象をあたえてしまう恐れ、有ったのでは。21 Completeとか。無茶でしょ
  • 太鼓の達人・DDRは来年こそ新筐体で。あー、まあ、需要過多になる危険があるか…

  • それはそれとして、全体としては、濃い2日間で楽しめました。ありがとうございました。

お土産

  • https://twitter.com/cielavenir/status/665833405490139136
  • パーカー
  • 本選Tシャツ、リレーTシャツ(カーネーション?)
  • あさプロタオル
  • トートバッグ
    • 今回、手提げショルダー両用なので、かなりありがたいです。
  • リストバンド、ボールペン、メモパッド、ステッカー、缶バッジ、タンブラー

追記(151116)

  • ショートコーディングOzy本、電子版が良いけどKindleは専用アプリが必要なのでちょっと、という人はこれを買いましょう。pdfなのでデバイスに依らず閲覧できますよ。
  • http://tatsu-zine.com/books/short-cording

http://yukicoder.me/problems/6

  • まず、N,D,Tを取得した後、アメーバの初期位置(e)を取得し、(e%D+D)%D(=mod)ごとに分けます。
  • 「modごとに分け」て以降にDを考慮しなくても良いよう、分けられたアメーバは、その中で [(e-mod)/D-T,(e-mod)/D+T] という範囲(閉区間)に分裂するとします。
  • ※言語によってはeが負だとバグるので、mod計算はきちんとやったほうが良いでしょう。

    • Ruby/Pythonだとe//D-TでACですが、C++ではそうではない。
  • ここからが本題で、現在yukicoderに上がっている解説ですと、範囲集合を事前にソートするとしていますが、それは必ずしも必要ではありません。逐一マージすれば良いからです。

  • マージするには、二分探索で右側を求め、左側と重なっているかチェックして、右側はいくつ先まで重なっているかもチェック。それらを消して、新しい範囲を挿入すればよいです。

  • 事前にソートしない利点として、以下のように変形した問題も容易に解けることが上げられます。

  • 「N個の初期位置が与えられる。あなたは与えられた順番通りにN匹のアメーバを数直線上に配置する。配置されたアメーバは、分裂を開始してT秒後に停止する。停止するまで次のアメーバを配置することはない。さて、i番目のアメーバが停止した時点で合計何匹のアメーバが数直線上に存在するか?」
  • この考え方を使うことで解ける問題があります。そう、CODE FESTIVAL 2015 予選B D問題 (マスと駒と色塗り)です。

    • なお、残念ながら、この問題は制約が大きいため、Ruby/PythonだとTLEします。PyPy/Crystalは導入されていないため、通るかはわかりません。ただ、C++でもset解法でなければならず、deque解法は75点(ちなみにvectorは40点)だったので、通る可能性は低いかもしれませんが。
    • あと、if(l<=left->second+1)の「+1」は必須。
    • http://code-festival-2015-qualb.contest.atcoder.jp/submissions/549169
  • ※ ついでに言うと、CheckiO Painting Wallも逐一マージが想定解です。

  • シンクロニカラウンジにて、自分のIDを得る方法について
  • フレンド検索で自分を検索することはできませんが、「スコアデータ」->「個人プレイ成績」を閲覧すると、URLの末尾に40文字の文字列が見えます。
  • これを https://lounge.synchronica.jp/Friend/info/ の後ろに付けることで、自分の情報を実際に見ることができます。よって、これを公開用IDとして良いのではないかと思われます。

  • なお、maimaiもフレンドコードを見られませんが、この方法で得ることもできません。なおフレンド申請は「ご近所リストの○番目に申請」という形式で実装されています。

http://yukicoder.me/problems/247

この問題はシミュレーションとなっていますが、シミュレーションは必要ではないです。

  • まず、各駒について、完成状態とのマンハッタン距離を取ります。1つでも2以上であれば、その配置は作ることができません。
  • 次に、その盤面が15パズルの盤面として正しいかを確認します。これは、(空マス以外の転倒数+空マスの上下動数)%2が偶数であれば正しいということが言えます。転倒数については
  • https://ja.wikipedia.org/wiki/%E8%BB%A2%E5%80%92_(%E6%95%B0%E5%AD%A6)
  • を参照して下さい。

  • これらの2条件がそろうとき、問題の配置は正しいと言えます。

  • 今回は転倒数の計算はO(nlogn)ではなくO(n2)でよいので、2重ループを書けばよいです。さらに、入力を読み込む途中に適宜転倒数の計算を行うとループの記述が1個消えます。これをまとめると以下のようになります(暫定最短コードです)。

Code Festival 2015 参加記を書いたので、2014についても可能なかぎり復元する。 なお、rprocon 2013は日帰り懇親会のみのため復元しません。

1日目

  • 御茶ノ水の日高屋で朝食

本選

  • パーカーボーダーは6問。rprocon 2013と同じ。
  • rprocon 2013Fを方針は合っていたのにnCrの計算を間違えて落とした(結果としてパーカーfailed)ので、今年は雪辱を晴らしたい。
時間 言語 問題(A-J) コメント
35秒 Ruby A AC FAは取れなかったが、相手は自動生成かな?仕方ないね
0:02 Ruby B AC
0:12 Ruby C 106全探索。TLE
0:14 Ruby C 閾値を105に。AC
0:32 Ruby D 12TLE/WAのあと、N+1 2を出力すれば良いことが判明。AC
0:48 Ruby F lcm/gcdの処理はできたが、後処理が合わない。WA。焦る。
1:14 C++ E lis/ldsを組み合わせる。AC
1:56 C++ J 幅優先探索。TLE
3:00 F通せず。パーカーfailed。無残。

夕方

  • 食事(食べ放題)後、chokudai氏トークライブ、診断人氏パフォーマンス、LT、タイピング、DDR、太鼓、エキシビション
  • 食事、美味しかったです。
  • あさプロは50位と150位でわかれるそう。私はMiddleですね。

  • 起床フェーズがやばいことは明白だったので、宿泊希望。秋葉原ワシントンホテル。
  • 解説を元に、本選Fを通す。個別指導塾行かずに済んだ。

2日目

  • 7:30起床。AC。
  • 書道コーディング。scala/scalac hybridなHello Code Festival出力。

あさプロ

時間 言語 問題(C-H) コメント
0:08 C++ C 2方向ダイクストラ。WA
0:25 C++ D 区間スケジューリングよろしく後ろでソートして、貪欲っぽく。WA。焦る。
0:36 C++ C 2箇所からとも繋がっていない場合のチェックを加える。 AC
0:50 E 読むが、わからない
1:12 C++ D 二部最大マッチングに持ち込むもTLE
1:28 C++ D 2分探索して削除を繰り返す…mapだと複数の値持てないし…ええーいvectorガチャ!実行時間1.2秒! AC (LA)
1:30 23位。35以内、入賞

  • 食事後、colun氏トークライブ、渡部有隆氏トークセッション、AI Challenge観戦
  • 今半すき焼き弁当。美味しかったです。

まとめ

  • 食事、美味しかったです。
  • 2日目、時間重ねないで…
  • 太鼓の達人・DDRは来年は新筐体で。

お土産