ei1333の日記

ぺこい

CODE FESTIVAL 2017 Final 参加記

えー覚えている範囲で真面目に書きます. ラーメンの画像は別の記事で. (←画像を紛失したため悲しいね

会場到着前

  • @beet_aizu さんと東京駅で合流し秋葉原へ
  • ラーメンを食べようと秋葉原散策(決まってなくてうろうろしてただけだね
  • ラーメンはこの時間やってません
  • やっとラーメンを食べます

会場到着後

本戦

  • ぞい！
  • A 問題を読む
  • 何をしてもできそうなんですが, バグりそう
  • 尺取りっぽくやりたい気持ちになったためそれを書く
  • サンプルを通してみると微妙にバグっていることがわかるので, 適当にサンプルを合わせます
  • 提出
  • コ ン パ イ ル エ ラ ー
  • 言語: Rust (1.15.1) じゃあないんだよね
  • 提出が難しすぎるため
  • はい帰宅
  • C++で出す
  • Accept
#include<bits/stdc++.h>
 
using namespace std;
 
const string temp = "AKIHABARA";
 
int main()
{
  string S;
  cin >> S;
 
  int ptr = 0;
  for(int i = 0; i < S.size(); i++) {
    if(ptr < temp.size() && S[i] == temp[ptr]) {
      ++ptr;
    } else if(temp[ptr] == 'A') {
      ++ptr;
      --i;
    } else {
      cout << "NO" << endl;
      return (0);
    }
  }
  if(ptr < temp.size()) ++ptr;
 
  if(ptr >= temp.size()) cout << "YES" << endl;
  else cout << "NO" << endl;
}
  • B 問題を読む
  • 絶対に 'a', 'b', 'c' それぞれの文字数の関係で答えが決まるのでそれを数える
  • よくわからないためサンプルを通して文字数を出力してみる
  • この結果と問題の雰囲気を感じると (最大の文字数) - (最小の文字数) ≦ 1 なら可能(未証明1)だということがわかる
  • ペナルティがないのでとりあえず提出
  • Accept
#include<bits/stdc++.h>
 
using namespace std;
 
int main()
{
  string S;
  cin >> S;
  int sz[3] = {};
  sz[0] = count(begin(S), end(S), 'a');
  sz[1] = count(begin(S), end(S), 'b');
  sz[2] = count(begin(S), end(S), 'c');
//  cout << sz[0] << " " << sz[1] << " " << sz[2] << endl;
 
  if(max({sz[0], sz[1], sz[2]}) - min({sz[0], sz[1], sz[2]}) <= 1) {
    cout << "YES" << endl;
  } else {
    cout << "NO" << endl;
  }
}
  • うんうん、雰囲気で競プロしているね
  • C 問題を読む
  • 5分考える
  • なにもわからない
  • コンテスト終了, 人生破滅
  • 自明な {2^{23} * 23 * N} みたいなのが間に合わないかなという気持ちが湧き上がってくる
  • 提出
  • Time Limit Exceeded
  • うく
  • 5 分考える
  • 時差 {i} の人は, {i} 時か {24 - i} 時のどちらかを選べることが分かる(それはそう
  • なにもわからない(やばいね
  • えーなんとなく時差が小さい人から, {i} 時と {24 - i} 時に置いてみて現在までの解が悪化しないほうにおいてみる解法(未証明2)を書いてみたくなる
  • 山登りっぽくやって通らない? 通るね
  • サンプルが通ったので出してみる
  • Accept(ん?)
#include<bits/stdc++.h>
 
using namespace std;
 
int main()
{
  int N, F[50];
 
  cin >> N;
  for(int i = 0; i < N; i++) {
    cin >> F[i];
  }
  sort(F, F + N);
 
  int cur[50] = {};
 
  auto getCost = [&](int idx)
  {
    int ret = 114514;
    for(int i = 0; i <= idx; i++) {
      for(int j = 0; j < i; j++) {
        ret = min(ret, min(abs(cur[i] - cur[j]), 24 - abs(cur[i] - cur[j])));
 
      }
    }
    return (ret);
  };
 
  memset(cur, 0, sizeof(cur));
  for(int j = 0; j < N; j++) {
    int s = F[j], t = 24 - F[j];
 
    cur[j + 1] = s;
    int st = getCost(j + 1);
 
    cur[j + 1] = t;
    int gt = getCost(j + 1);
 
    if(st >= gt) cur[j + 1] = s;
  }
  cout << getCost(N) << endl;
}
  • D 問題を読む
  • むずそう
  • D は DP の D なので {O(N^2)} の DP をすることを考える
  • 少し考えると, 参加者の並びが固定の場合なら本当に DP で解けることがわかる
  • dp[idx][sum] := idx 人目まで見て, 今までに sum 人参加できたときの座布団の枚数の最小値
  • あとは参加者の並び
  • いろいろ迷走するんですが, ソートしたい！ｗ みたいな気持ちになる
  • えーソートして最適な順番が一意に定まらないと解ける問題に見えないため
  • ソートするには比較関数が必要ということに気づく
  • 勘を働かせると h+p でやりたくなって(未証明3), やると全てのサンプルが通る
  • サンプルが一致したので出しますね
  • 提出
  • Accept
#include<bits/stdc++.h>
 
using namespace std;
 
const int INF = 1 << 30;
 
int main()
{
  int N;
 
  cin >> N;
  vector< pair< int, int > > st(N);
  for(int i = 0; i < N; i++) {
    cin >> st[i].first >> st[i].second;
  }
  sort(begin(st), end(st), [&](pair< int, int > x, pair< int, int > y)
  {
    return (x.first - y.second < y.first - x.second);
  });
 
  int dp[5001];
  fill_n(dp, 5001, INF);
  dp[0] = 0;
  int ret = 0;
  for(int i = 0; i < N; i++) {
    for(int j = N - 1; j >= 0; j--) {
      if(dp[j] <= st[i].first) {
        dp[j + 1] = min(dp[j + 1], dp[j] + st[i].second);
        ret = max(ret, j + 1);
      }
    }
  }
 
  cout << ret << endl;
}
  • E 問題を読みます
  • 区間先輩....
  • F 問題を読みます
  • 構築先輩....
  • G 問題を読みます
  • 数え上げ先輩...
  • ここから険しい時間帯が {\infty} 分継続する
  • 疲れたため {1} 時間睡眠をとる
  • (以下睡眠中の出来事です)
  • E 問題は区間に対する操作なので階差をとってみたい気持ちになる
  • 区間の操作は楽になった
  • えー階差にして良いことがなにもわからない
  • 回文の判定こわれる, どうやるねん
  • 階差をとるのを諦める
  • F 問題は構築なので実験したい気持ちになる
  • 実験のコードを書こうとする
  • バグる
  • 嫌になったためおしまい。
  • G 問題は数え上げなので難しいなあと思う
  • (この時点では微妙に誤読してる)
  • 手の付け方がわからない
  • えーん
  • (睡眠終わり)
  • 起床する
  • G 問題を読み直すと {i} 番目以前の操作を何度行っても {i + 1} 番目以降の状態は変化しないことがわかる
  • 前から石の初期数を決めて処理するのは後ろの石の数によって変化してしまい無謀なため, 後ろから見たくなる
  • 後ろからみたとすると, 現在の要素の石の個数は (最初にその位置に置いた石の数)+( {i+1} 番目以降で操作をした回数) となる
  • 状態として 操作した回数と要素位置をもって, メモ化再帰を雰囲気に則って書くとそれらしいものが生える
  • その位置におく初期の石の数を全通り試すとして, それぞれの石の数に対しその要素が最終的に何個になるか=その位置での操作回数は何回かがわかればよくてやっぱり雰囲気
  • できた
  • 提出
  • Accept
#include<bits/stdc++.h>
 
using namespace std;
 
using int64 = long long;
const int mod = 1e9 + 7;
 
int N, K;
int64 fact[101];
int64 dp[101][100001];
 
int rec(int idx, int add)
{
  if(idx == 0) return (0);
  if(~dp[idx][add]) return (dp[idx][add]);
  long long ret = 0;
  for(int i = 0; i <= K; i++) {
    if(i <= idx && idx <= add + i) {
      int sqr = (add + i) % idx;
      (ret += 1LL * fact[idx - 1] * sqr % mod) % mod;
      (ret += rec(idx - 1, add + (add + i) / idx)) %= mod;
    } else {
      (ret += 1LL * fact[idx - 1] * (i + add) % mod) %= mod;
      (ret += rec(idx - 1, add)) %= mod;
    }
  }
  return (dp[idx][add] = ret);
}
 
int main()
{
  cin >> N >> K;
  fact[0] = 1;
  for(int i = 1; i <= N; i++) {
    (fact[i] = fact[i - 1] * (K + 1)) %= mod;
  }
  memset(dp, -1, sizeof(dp));
  cout << rec(N, 0) << endl;
}
  • H, I, Jを読む
  • やばいため
  • E を考える
  • 嘘が生えるため出す
  • WA
  • WA
  • WA
  • F の解法が突然生える
うくにきあ！
  • WA(えぇ...)
  • コンテスト終わり(37位)
  • オンサイトでは最悪をいつもしているんですが, 今回は悪くなくない？悪くないね
  • なんかパーカーが暖かくなってる気がする（うれしい

1日目その後

  • 大陸対抗トークライブさん...
  • コネクションハントさんを微妙にする
  • 解説をちょっと聞く
  • 書道コーディングする(うしのアイコンを書く)
  • 寿司
  • ピザ
  • 肉
  • 最悪コード川柳を生やす
  • エキシビジョンマッチで海外勢の終了n秒前提出の全完ではえーってなる

1日目終わり

  • こわれた一件で自分の現在位置がわからないため
  • {1} 時間ぐらい散歩をします(迷っていただけ)
  • ホテル間違えて受付にここじゃないね と言われながらなんとか
  • テレビをつけてアニメを見ます(ホテルでの楽しみ)
  • @takimoto123_ さんと @beet_aizu さんでAVCをやろうという話になります
  • 去年のこどふぇすのトーナメントセット+αを解く
  • ぐう
  • 3 時にねね

2日目始まり

  • 7 時に目覚めます
  • 7 時半に目覚ましがなります
  • 8 時にシャワーを浴びます
  • 8 時半に準備を始めます
  • 9 時にホテルをでます
  • 途中で @takimoto123_ さんに話しかけられます
  • 一緒にデート
  • つく

Tournament Round

Round 1

  • A の問題文を 10 分くらい書けて読んでやっとわかります
  • 解法はわからないため 5 分で 200 点を書いて提出
  • 順位表を見ながらあと 200 点取れば通過できるやろ！ｗと思って B の 200 点をとってへらへらしながら順位表を見ると 11 位
  • 上位 10 人通過のため
  • おわり(おわりのため)(最悪)

そのあと

  • トークライブきいたり
  • 昼食食べたり
  • 昼食になったり

Relay

  • 順位っぽいアでだいたい分担
  • 黄コーダーとかそれ以上とかが多いためヤバいね
  • ACACAC
  • 貢献できなくてけわしい
  • 自分は G,H あたりを読みます
  • G がわかりません
  • なんか一生考えてるとコーナーケースがないと信じた貪欲っぽいアをしたい気持ちになる
  • G を担当
  • アを実装するとAccept
  • 気づいたらあと2問になっていて, 解法がわからないため

2日目おわり

  • @beet_aizu さんとラーメンを食べに行きます
  • おいしいね
  • 東京駅で解散しておみやげ買って
  • 家に帰って, 課題をしています(は????)
  • 今に至る
  • 課題が終わっていません悲しいね

最後に

  • 関係者や参加者の方々, ありがとうございました！！
  • 来年も行きたいぞい
  • うっしっし