[Yukicoder] アメーバがたくさん・n連勤 (and マスと駒と色塗り)

アメーバがたくさん

問題

前処理

  • まず、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番目のアメーバが停止した時点で合計何匹のアメーバが数直線上に存在するか？」

マスと駒と色塗り

問題

解答例

Painting Wall

n連勤

問題

解答例

シンクロニカの公開用IDを得る方法

  • シンクロニカラウンジにて、自分のIDを得る方法について
  • フレンド検索で自分を検索することはできませんが、「スコアデータ」->「個人プレイ成績」を閲覧すると、URLの末尾に40文字の文字列が見えます。

  • これを https://lounge.synchronica.jp/Friend/info/ の後ろに付けることで、自分の情報を実際に見ることができます。よって、これを公開用IDとして良いのではないかと思われます。

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

[Yukicoder] ゆきこちゃんの15パズル

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 2014 参加記

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は来年は新筐体で。

お土産