brly.github.io

09 February 2015 : 連休

Anime
Game
Ruby

会社の制度を使って連休を取れることになったが、特に予定も入れなかったので とりあえずメモだけ残しておくことにする。

連休は土日も含めると 2/7 - 2/15 の 9 日間だった。

2/7

前日から友人を家に泊めており、その友人が秋葉原に行きたいと行っていたので行った。 友人は256GBのSSDをTSUKUMOで買い、自分は中古のゲームをいくつか買った。

買ったもの。

  • 逆転検事 ¥1600 - 紙風船
  • 逆転検事2 ¥1600 - 紙風船
  • 逆転東方総集編(同人ゲーム) ¥2300 - 紙風船
  • アイドルマスター ディアリースターズ ¥3600 - TRADER

逆転検事を始めた。

2/8

gochiusa

ごちうさのトークイベント に行った。東京証券会館。

監督の方ともう一人制作に携わっている人(名前と役職忘れた)をメイン演者５人に加えて合計7名によるトークイベントだった。

単純に有名な声優さんが観れて嬉しいというのもあったけど、監督の制作秘話とか、演者の個々人の「感動シーン」を 述べるコーナーなどがあり、細かな制作の背景などが知れて面白かった。

game

逆転検事をクリア。 逆転検事2を始める。

2/9

この記事を書き始めた。 逆転検事2を進める。(1,2,3章クリア)

2/10

逆転検事2をクリア。

連続してゲームし続けた疲れのせいもあると思うけど、だいぶ難しく感じた。 後半には複数の事件とたくさんの証拠がそれぞれ入り組んでくるので、物語の状態としてかなり複雑度が高くなっていた気がする。 製作陣が逆転裁判5と同じらしいけど、比較的難しめなように感じたが、こちらの方が好みだ。 ギミックとかストーリーも良かった。

途中で2度くらい攻略サイトのお世話になってしまった。

2/11

コンピュータアーキテクチャ技術入門を読んだ。 会社から支給された本になる。元々読み進めていた。

Donutsプロコンチャレンジ2015に参加した。 2問しか解けなかった。3問目がもう少しで解けそうなところで時間が終わってしまった。

コンピュータの構成と設計3版:下を読み始めた、けど上の本とかなり重複している部分があるので ななめ読みで最後まで進めてしまった。

rubyの小さなプログラムを書き始めた。

CPUの創りかたを読み始めた。

2/12

掃除、洗濯。

CPUの創りかたを読み進める。チャタリングとか、響きが懐かしい単語が沢山出てくる。 今の所読んだ前半部分は基本的に大学の授業でやったようなことがつらつら書かれているのだけれど、 よりカジュアルな文体で描かれているので読みやすい。 このJavaアプレットのサイトで本に出てくる回路を組んでみたりしてみる。

他のWebアプリケーション的なのがこれ以外にもいくつかあるけどあんまりいけてない。気がする。

rubyのプログラムを進捗させる。250行くらい。

2/13

起きたらなんか首が痛かったので何をするにもあんまりやる気が出なかった。

だらだらしてフリーゲームしてたら一日が終わった。

夜にボドゲに参加してカタンを2回した。勝てなかったけど面白かった。

2/14

首がいたくなる原因は寝るときの姿勢だった。

rubyのプログラムを進捗させる。

reading

CPUの創りかたを読んだ。まだ100ページくらいしか読んでいなかったけど、後半部分が特に面白かったので一気に最後まで読めることが出来た。 特に、最後に実行部分への入力信号を制御するための命令デコーダを設計する章は、 それまでの伏線を回収する内容で、するすると頭に入ってきて、読んでいて爽快だった。

命令デコーダ部分が一番複雑で、そこで初めて真理値表、真理値表の圧縮、カルノー図、というふうに、 必要になってから初めて教科書的教養を持ち出して解決しているのが印象的で、 とにかくこの本では、なるべく内容が平易になるように努められていることが見受けられる。

筆者の意訳として

「多少なり複雑なことを理解するときは、物事の複雑さにもよるけれど 普通はその複雑を構成する基礎を学んでから複雑に取り掛かろうとするが、 一方本書では、とりあえずやってみて必要になってからそういうのを学ぶようにする」

という文章が数カ所見受けられる。これはこの本の特性で、自分はこれにすごい共感できたので そこらへんの一回見聞きして忘れていた教科書的な要素も頭に入りやすかった。

また各レジスタをD-フリップフロップで作り、 命令の完了をクロックの立ち上がり(=値の保持が行われた)としているのも直感的でわかりやすかった。 そこからこのCPUの最大動作周波数の話につながったりして、ずっとなるほどなるほどと言ってた。良書だった。

2/15

rubyのプログラムを少し進捗させてあとはぼーっとしていた気がする。

フリーゲームの飛べない虫をやってた。

03 February 2015 : dwangoプログラミングコンテスト

ARC
C++

dwangoプログラミングコンテスト　dwangoからの『挑戦状』

当日は２問しか解けなかった（◞‸◟）

のでときなおし。

結果

B. ニコニコ文字列

#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <algorithm>
#include <utility>
#include <bitset>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <cstdio>

using namespace std;

#define REP(i,n) for((i)=0;(i)<(int)(n);(i)++)
#define foreach(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)

typedef long long ll;

ll add(int len) {
  ll elems = len/2;
  return (elems * (elems+1) / 2);
}

int main() {
  string s;

  while (cin>>s) {

    ll ans = 0;
    char c = '_';
    ll len = 0;

    const int N = s.size();

    for (int i = 0; i < N; i++) {
      char load = s[i];
      //printf("len=%d\n", len);
      if (c == '_') {
        if (load != '2') continue;
        c = load;
        len++;
      }
      else {
        if (c == '2') {
          if (load == '5') {
            len++;
            c = load;
          }
          else {
            if (len) {
              ans += add(len);
            }
            c = '_';
            len = 0;
          }
        }
        else if (c == '5') {
          if (load == '2') {
            c = load;
            len++;
          }
          else {
            if (len) {
              ans += add(len);
            }
            c = '_';
            len = 0;
          }
        }

        if (c == '_' && load == '2') {
          len++;
          c = '2';
        }
      }
    }
    if (len) {
      ans += add(len);
    }

    cout << ans << endl;
  }
  return 0;
}

C. ゲーマーじゃんけん

解説スライドから式そのまま。Pijの計算方法がわからなかった。

#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <algorithm>
#include <utility>
#include <bitset>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <cstdio>

using namespace std;

#define REP(i,n) for((i)=0;(i)<(int)(n);(i)++)
#define foreach(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)

const double kEps = 1e-9;

typedef unsigned long long ull;
typedef pair<int,int> P;

double nCr[102][102];

double E[102];

P combination_type(int rock, int scissor, int paper) {
  vector<int> v;
  if (rock)
    v.push_back(rock);
  if (scissor)
    v.push_back(scissor);
  if (paper)
    v.push_back(paper);
  sort(v.begin(), v.end());
  int mn = v[0];
  int mn_cnt = count(v.begin(), v.end(), mn);
  int sum = rock + scissor + paper;
  P ret;

  if (v.size() == 1) {
    ret.first = 3;
    ret.second = 0;
  }
  else if (mn_cnt == 1) {
    ret.first = 1;
    ret.second = sum - mn;
  }
  else if (mn_cnt == 2) {
    ret.first = 2;
    ret.second = sum - mn;
  }
  else {
    ret.first = 3;
    ret.second = 0;
  }

  return ret;
}

double solve(int n) {
  const double kDenom = pow(3, n);
  vector<double> pn(102, 0);

  for (int r = 0; r <= n; r++) {
    for (int s = 0; (s + r) <= n; s++) {
      for (int p = 0; (s + r + p) <= n; p++) {
        if (s + r + p < n) continue;
        P tmp = combination_type(r, s, p);
        // printf("r,s,p=%d,%d,%d value=%llu f,s=%d,%d\n",
        //   r, s, p, nCr[n][r] * nCr[n-r][s], tmp.first, tmp.second);
        if (tmp.first == 1 || tmp.first == 2) {
          pn[n - tmp.second] += nCr[n][r] * nCr[n-r][s] / kDenom;
        }
        else {
          pn[n] += nCr[n][r] * nCr[n-r][s] / kDenom;
        }
      }
    }
  }

  for (int i = 0; i <= n; i++) {
    //printf("pn[%d] = %.3f\n", i, pn[i]);
    //pn[i] /= kDenom;
  }

  // expression
  double ret = pn[n];
  for (int i = 1; i <= n - 1; i++) {
    //printf("compute sum at index=%d\n", i);
    ret += pn[i] * (E[i] + 1);
  }
  ret /= (1 - pn[n]);

  return ret;
}

int main() {
  // nCr
  memset(nCr, 0, sizeof nCr);
  nCr[0][0] = 1;
  for (int i = 1; i <= 100; i++) {
    nCr[i][0] = 1;
    for (int j = 1; j <= i; j++) {
      nCr[i][j] = nCr[i-1][j-1] + nCr[i-1][j];
    }
  }

  // do
  memset(E, 0, sizeof E);
  E[1] = 0;
  for (int i = 2; i <= 100; i++) {
    E[i] = solve(i);
    //printf("E[%d] = %.3f\n", i, E[i]);
  }

  int in;
  while (scanf("%d", &in) != -1) {
    printf("%.7f\n", E[in]);
  }
  return 0;
}

D. タクシー

部分点1

1 <-> N 間の移動量を探索して、あとは直線の場合で解く。O(N * bの合計)。

#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <algorithm>
#include <utility>
#include <bitset>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <cstdio>
#include <numeric>

using namespace std;

typedef long long ll;

const int kN = 100002;

int N;
ll L;

ll A[kN];
ll B[kN];
ll C[kN];

ll S[kN];
ll T[kN];

ll solve() {
  ll sum_b = accumulate(B, B+N, 0LL);

  if (N > 5000 || sum_b > 5000) {
    return -1LL;
  }

  ll ans = 1LL<<59;
  ll end_to_start = min(A[N-1], L - A[N-1]);

  for (ll init_move = sum_b; init_move >= -sum_b; --init_move) {
    vector<ll> tmp;
    for (int i = 0; i < N; i++) {
      tmp.push_back(B[i]);
    }

    tmp[N-1] -= init_move;
    tmp[0] += init_move;

    ll cost = abs(init_move) * end_to_start;
    for (int i = 0; i < N-1; i++) {
      ll delta = tmp[i] - C[i];
      tmp[i] -= delta;
      tmp[i+1] += delta;
      cost += abs(delta) * (A[i+1] - A[i]);
    }

    ans = min(ans, cost);
  }

  return ans;
}

int main() {
  while (cin>>N>>L) {
    for (int i = 0; i < N; i++) {
      cin >> A[i] >> B[i] >> C[i];
    }
    ll ans = solve();
    cout << ans << endl;
  }

  return 0;
}
部分点2

移動量を探索するのではなくT-Sから求める(解説スライド)。O(N^2)。

#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <algorithm>
#include <utility>
#include <bitset>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <cstdio>

using namespace std;

typedef long long ll;

const int kN = 100002;

int N;
ll L;

ll A[kN];
ll B[kN];
ll C[kN];

ll S[kN];
ll T[kN];

ll solve() {
  if (N > 5000) return -1LL;

  memset(S, 0, sizeof S);
  memset(T, 0, sizeof T);

  S[0] = B[0];
  T[0] = C[0];
  for (int i = 1; i < N; i++) {
    S[i] = S[i-1] + B[i];
    T[i] = T[i-1] + C[i];
  }

  ll ans = 1LL<<59;
  ll end_to_start = min(A[N-1], L - A[N-1]);

  for (int z = 0; z < N-1; z++) {
    ll x = T[z] - S[z];
    ll cost = 0;
    vector<ll> tmp;
    tmp.assign(B, B+N);

    cost += abs(x) * end_to_start;
    tmp[0] += x;
    tmp[N-1] -= x;

    for (int i = 0; i < N; i++) {
      ll delta = tmp[i] - C[i];
      tmp[i] -= delta;
      tmp[i+1] += delta;
      cost += abs(delta) * (A[i+1] - A[i]);
    }

    ans = min(ans, cost);
  }

  return ans;
}

int main() {
  while (cin>>N>>L) {
    for (int i = 0; i < N; i++) {
      cin >> A[i] >> B[i] >> C[i];
    }
    ll ans = solve();
    cout << ans << endl;
  }

  return 0;
}
満点

解説スライド的には部分点2の解法から凸関数であることが分かるので三分探索で解ける、ということだと思われる。 O(N * lg(100k * N))。

#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <algorithm>
#include <utility>
#include <bitset>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <cstdio>
#include <numeric>

using namespace std;

typedef long long ll;

const int kN = 100002;

int N;
ll L;

ll A[kN];
ll B[kN];
ll C[kN];

ll S[kN];
ll T[kN];

ll tmp[kN];
ll end_to_start;

ll f(ll x) {
  ll cost = 0;
  for (int i = 0; i < N; i++) {
    tmp[i] = B[i];
  }

  cost += abs(x) * end_to_start;
  tmp[0] += x;
  tmp[N-1] -= x;

  for (int i = 0; i < N; i++) {
    ll delta = tmp[i] - C[i];
    tmp[i] -= delta;
    tmp[i+1] += delta;
    cost += abs(delta) * (A[i+1] - A[i]);
  }

  return cost;
}

ll solve() {
  ll ans = 1LL<<59;
  end_to_start = min(A[N-1], L - A[N-1]);
  const ll sum_b = accumulate(B, B+N, 0LL);
  ll lb = -sum_b, ub = sum_b;

  for (int z = 0; z < 100; z++) {
    ll lhs = (lb+lb+ub) / 3LL;
    ll rhs = (lb+ub+ub) / 3LL;

    ll lv = f(lhs);
    ll rv = f(rhs);
    ans = min(ans, min(lv, rv));

    if (lv < rv) {
      ub = rhs;
    }
    else {
      lb = lhs;
    }
  }

  return ans;
}

int main() {
  while (cin>>N>>L) {
    for (int i = 0; i < N; i++) {
      cin >> A[i] >> B[i] >> C[i];
    }
    ll ans = solve();
    cout << ans << endl;
  }

  return 0;
}

E. 電波局

部分点1.
#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <algorithm>
#include <utility>
#include <bitset>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <cstdio>

using namespace std;

#define REP(i,n) for((i)=0;(i)<(int)(n);(i)++)
#define foreach(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)

const int kM = 1002, kQ = 1002;

int N, M;
int A[kM], B[kM], C[kM];

int Q;
int D[kQ], E[kQ], F[kQ];

bool user[202][202];  // by constraints
bool tmp[202][202];

void solve() {
  if (N > 200 || M > 200 || Q > 200) {
    for (int i = 0; i < Q; i++) puts("-1");
    return;
  }

  memset(user, 0, sizeof user);
  for (int i = 0; i < M; i++) {
    int a = A[i], b = B[i], c = C[i];
    for (int j = 1; j <= c; j++) {
      for (int k = 1; k <= j; k++) {
        int la = a + j - 1;
        int lb = b + k - 1;
        if (lb > la) continue;
        user[la][lb] = 1;
      }
    }
  }

  for (int i = 0; i < Q; i++) {
    int d = D[i], e = E[i], f = F[i];
    int val = 0;

    memcpy(tmp, user, sizeof user);

    for (int j = 1; j <= f; j++) {
      for (int k = 1; k <= j; k++) {
        int ld = d + j - 1;
        int le = e + k - 1;

        if (!tmp[ld][le]) {
          tmp[ld][le] = 1;
          ++val;
        }
      }
    }
    printf("%d\n", val);
  }
}

int main() {
  while (cin >> N >> M) {
    for (int i = 0; i < M; i++) {
      cin >> A[i] >> B[i] >> C[i];
    }
    cin >> Q;
    for (int i = 0; i < Q; i++) {
      cin >> D[i] >> E[i] >> F[i];
    }
    solve();
  }
  return 0;
}
部分点2.

なんか TLE がとれないので諦めた（◞‸◟）

11 January 2015 : 2014年振り返り

Poem

新年に入ってから既に１週間以上立ってるけれど、振り返り。

一人暮らし

一人暮らし自体は大学１回生ぶりなので５、６年ぶりくらいになる。やっぱりしんどい。

色々な家事にかける時間やエネルギーを考えると、高コストな選択をしがちになる。

今はルンバとかの購入を本気で考えている。

仕事

エンジニアとしての社会人生活の幕開けである。

最初の１ヶ月くらいの Java 研修、２ヶ月弱くらいのチーム開発研修では Java/javascript を書いてた。

そのあとは今の部署に配属されて、たまに C/C++ を書く機会があったりなかったりくらい。

コードリーディングとかプログラムの解析とかコーディング以外の仕事が多い。

入社時の心持ちとしては、Web企業だと思っていたのでより早くより良いコードを沢山書いて なんぼみたいなイメージがあったのだけど今はそうではなくて、大学の研究の時のスタイルに近いかもしれない。

同じチームの人は強い人しかいないので、恵まれた環境にあると思う。

お金

学生の時に比べ、とにかく扱うことの出来る額が大きくなるので、消費に対して自制が必要になる。

学生の時よりも気軽に円盤を買ってる。

プログラミング言語のこと

毎年一つ新しい言語を覚えようというやつで今年は Go だった。

martini revel とかのWebフレームワークを触った。

Go は Ruby/Python の代替だ、という話をどこかで聞いて、確かに趣味で書いてた Ruby のコードを高速化するために Go に書き換えるという経験があって、 その時はコードベースも小さいし割とすんなり移行出来た。その時は結局速度が足りなかったけど..

テキスト処理、HTTPサーバ/クライアント、外部コマンドの実行などを簡単に書きたい時 Go は良い選択肢になるかもしれない。

並行処理がとっつきやすいとか話題に出るけど goroutine 使っても全然駄目なコードはいくらでもかけるので(書いた)のでそうでもないなぁという印象。

あと東京にいたので Go Conference Autumn 2014 に行った。なかなか面白かった。 プログラミング言語の作者を初めて見た。

エディタのこと

長いこと Emacs に浸かっていたけど、10月くらいから Atom を使い始めて、 今はMacのデスクトップ環境でプログラム/文章を書く場合は Atom を使うようになった。

仕方なくサーバーの中でソースコードをいじる時だとか、 Emacsの gud-gdb を使いたい時とかはあれだけど、それ以外は Atom。

なんか Markdown Preview がリッチで楽しい。

IDEはあんまり好きじゃないし、あと linter ていう flymake 的なのをボタン一つで入れれば それなりに使えるはず。

あとは困ったら Cmd + Shift + P でコマンドパレットが開くので、それで大体のことが出来る。

本のこと

今年(2014)読んだ本。

  • 入門Git
    • git 使ったことないので買った。中身は入門(primer)じゃない。さるできの後に読んだので良かった。
  • コンピュータの構成と設計(3版)上
    • 配属後、とにかくコンピュータアーキテクチャ力不足を痛感したので。
  • オブジェクト指向入門(2版) 原則/コンセプト
  • リファクタリング(新装版)
    • まだ途中。
  • あと研修中に会社から渡された本。あんまし覚えてない。 やっぱり自分で読みたいのを読むのが頭に入るんじゃないかな。

積んでる本。

  • コンピュータの構成と設計(3版)下
    • 今はもう5版とか出てるのに。安かったからいいけど。
  • オブジェクト指向入門(2版) 方法論/実践
  • CPUの創りかた
  • 統計学が最強の学問である
  • めぞん一刻(借り物)
    • 2015年中に読んで返したい。

来年のこと

そこそこにがんばりたい。

22 December 2014 : AtCoder Regular Contest 031

ARC
C++

AtCoder Regular Contest 031

結果 oo*-

C. 積み木

愚直アプローチ

ナイーブに反転数を求める.

#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <algorithm>
#include <utility>
#include <bitset>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <cstdio>

using namespace std;

#define REP(i,n) for((i)=0;(i)<(int)(n);(i)++)
#define foreach(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)

ll solve() {
  vector<P> vp;
  for (int i = 0; i < n; i++) {
    vp.push_back(P(b[i], i));
  }

  sort(vp.begin(), vp.end());

  ll ans = 0;

  for(int i = 0; i < n; i++) {
    P p = vp[i];
    int idx = p.second;
    int val = p.first;

    // l
    ll lcnt = 0;
    for (int j = idx - 1; j >= 0; j--) {
      if (b[j] == -1) continue;
      //printf("lcnt - %d vs %d\n", val, b[j]);
      if (val < b[j]) {
        ++lcnt;
      }
    }

    // r
    ll rcnt = 0;
    for (int j = idx + 1; j < n; j++) {
      if (b[j] == -1) continue;
      //printf("rcnt - %d vs %d\n", val, b[j]);
      if (val < b[j]) ++rcnt;
    }
    ans += min(lcnt, rcnt);
    b[idx] = -1;
  }
  return ans;
}

int main() {
  while (cin >> n) {
    for(size_t i = 0; i < n; i++)
    {
      cin >> b[i];
    }
    printf("%lld\n", solve());
  }
  return 0;
}
BIT(Binary Indexed Tree)

小さい方 or 大きい方から順番に対応する場所に add していって, 左側と右側の場合の反転数を Bit で lgN で計算する.

#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <algorithm>
#include <utility>
#include <bitset>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <cstdio>

using namespace std;

#define REP(i,n) for((i)=0;(i)<(int)(n);(i)++)
#define foreach(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)

int b[100020], n;

struct Bit {
  const int N;
  vector<int> data;
  Bit(const int size) : N(size + 2), data(n + 4) {}
  void add(int idx, int value) {
    for (int x = idx; x <= N; x += x & -x)
      data[x] += value;
  }
  int sum(int idx) {
    int ret = 0;
    for (int x = idx; x > 0; x -= x & -x)
      ret += data[x];
    return ret;
  }
};

typedef long long ll;

typedef pair<int,int> P;

ll solve() {
  ll ans = 0;
  Bit bit(n);

  vector<P> vp;
  for(int i = 0; i < n; i++)
  {
    vp.push_back(P(b[i], i+1));
  }

  sort(vp.begin(), vp.end(), greater<P>());

  for(int i = 0; i < n; i++)
  {
    int idx = vp[i].second;
    int lhs = bit.sum(idx);
    int rhs = bit.sum(n) - lhs;
    ans += min(lhs, rhs);
    bit.add(idx, 1);
  }
  return ans;
}

int main() {
  while (cin >> n) {
    for(size_t i = 0; i < n; i++)
    {
      cin >> b[i];
    }
    printf("%lld\n", solve());
  }
  return 0;
}

D. 買い物上手

全探索アプローチ

全探索をナイーブに実装すれば部分点は取れる.

#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <algorithm>
#include <utility>
#include <bitset>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <cstdio>

using namespace std;

#define REP(i,n) for((i)=0;(i)<(int)(n);(i)++)
#define foreach(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)

int N, M;

int S[102], T[102], K[102];

int A[102][102];

double solve() {
  double ans = 0;
  for (int Set = 0; Set < (1<<N); Set++) {
    bitset<102> bs;
    int exp = 0;
    for (int i = 0; i < N; i++) {
      if (!(Set >> i & 1)) continue;
      exp += S[i];
      for (int j = 0; j < K[i]; j++) {
        bs.set(A[i][j]);
      }
    }
    int sum = 0;
    for (int i = 0; i < M; i++) {
      if (bs[i]) sum += T[i];
    }
    ans = max(ans, (double)exp / sum);
  }
  return ans;
}

int main() {
  while (cin >> N >> M) {
    for(size_t i = 0; i < N; i++)
    {
      cin>>S[i];
    }
    for(size_t i = 0; i < M; i++)
    {
      cin>>T[i];
    }
    for(size_t i = 0; i < N; i++)
    {
      cin>>K[i];
      for(size_t j = 0; j < K[i]; j++)
      {
        cin>>A[i][j];
        A[i][j]--;
      }
    }
    printf("%lf\n", solve());
  }

  return 0;
}
最大流

解説解読中….

10 December 2014 : 丼丸注文入門

Donmaru

この記事は 丼丸 Advent Calendar 2014 の10日目の記事です.

丼丸注文入門

(この記事は清澄白河店での体験を元に記述されている.)

この記事は, 丼丸にまだ行ったことのない人を対象読者としており, 実際に丼丸の注文のイメージが行えるようになることを目的としている.

丼丸とは

丼丸自体の説明/紹介については 公式サイト や 丼丸アドベントカレンダー2014 の記事 などに任せたい.

丼丸でのフロー

丼丸の楽しみ方には大きく2通りあり, テイクアウトとイートインであるが, 清澄白河店ではテイクアウトのみのお店となっている.

店舗がイートインに対応しているかどうかは公式サイトで確認できる.

清澄白河店のページがあるのだが, 持ち帰り専門店: NO と記述されている.

が, 実際には持ち帰り専門店だ.

ここで紹介するフローはテイクアウトのみになることを予め断っておく.

主な処理フローは

  1. 注文する
  2. お金を払う
  3. 丼が出来るまでまで待つ
  4. 完成した丼を受け取り帰宅する

であり, それぞれについて記述していく.

1. 注文する

いわずもがな, 注文入門において, 注文は重要アクションだ.

しかし, 丼丸の店内に入ったことのある人ならば分かるかと思うが, 丼丸の店舗では店内の壁や,あるいは店の外の壁を使って, 店舗で取り扱っている「丼」を表している.

おそらく, すべてのメニュー(=丼)を把握するのは, 初めて訪れた人には困難であり, レジの人に「ご注文はお決まりですか」と聞かれてしまったり, あるいは順番待ちの末に自分の番が来ても決まらずに, 適当に目に入った “それ” を注文してしまう可能性が高い.

なので, 初心者はお店に向かう前に予め食したい「丼」をセレクトしておいた状態で お店に向かうことで, 後悔せず注文が行えるものと思われる.

どのような丼があるかについては、やはり公式サイトの メニューを参照されたし.

また, 公式サイトで紹介されているのは基本丼(という呼称を身内では定義しているのだが) であり, 丼丸の各店舗で取り扱われている可能性が高い丼のため, 安心できる.

丼丸の各店舗では, 基本丼に含まれないオリジナル丼が数多く存在するので, そういった「丼」を食べることももちろん楽しみの一つだ.

また, 丼丸では丼の注文時に以下のオプションが適用出来る.

  • シャリ大盛り
  • ネタ大盛り
  • 特盛り(シャリ, ネタ共に大盛り)

参考までに清澄白河店での値段を記載すると (価格は税抜き)

  • 並盛り : 500円
  • シャリ大盛り : 600円
  • ネタ大盛り : 700円
  • 特盛り : 800円

であり, 自分の胃袋と相談して最適なオプションを加えたい.

また, 公式サイトのメニューを見た人は気付いたかもしれないが, おまかせ刺身盛 という 丼丸なのに, ご飯無しのメニューがある.

そして丼丸の各丼では「シャリ抜き」で注文することで各丼の刺身盛り(刺身のみ)が注文出来る.

これは

  1. 刺身の量は丼丸のシャリの上に乗っている量と変わらない
  2. 値段は20円引き(尋ねたところ, シャリが20円分ということだった)

であり, 例えば自分でご飯は炊いてしまったが丼丸をどうしても食べたい時などに利用出来る.

2. お金を払う

注文に応じた料金を支払う.

丼丸に通っている人には説明するまでもないことだが, 0 の付く日は料金が税込で税抜価格となり, 若干安くなる.

3. 丼が出来るまで待つ

丼丸は注文を受けてから, 調理(主に盛り付けと思われる)が始まる.

その間は完成するまで待つ.

4. 完成した丼を受け取り帰宅する

この丼を受け取る時も気を抜いてはいけない.

丼を受け取る際に「しょうゆと割り箸」か「インスタントのお吸い物」のどちらかを選んでもらうことが出来る.

店舗や店員さんによってはどちらにするか尋ねられることなくどちらかを入れられてしまう可能性があるので,

自分の意とそぐわない方を入れられてしまうことを防ぐため, 受け取る直前に希望を伝えることをお勧めする.

おわりに

自分なりの経験からこのような記事を書いてみた.

お店に行ったことのない方の注文のイメージの助けになれば幸いだ.

あとがき

私は, 今年に入ってから上京し, 東京で初めて丼丸のお店を訪れた.

私の故郷は長野県であり, 公式サイトを見ると, 長野県にも点在しているようだが, 私の住んで居た 長野市には存在せず, それまで出会うことはなかった.

長野県は山に囲まれている海なし県であり, そもそも海鮮を食べる機会が少なく, また稀に機会があったとしてもあまり美味しくない印象であった.

そんな私の海鮮に対するイメージを払拭してくれたのが丼丸だった.

ACには19日にも登録してあるので, また別の角度から丼丸に関する記事を投稿したい.