2015年2月8日日曜日

JOI2015本選参加記

眠れない日々だった
3完 + 部分点 の 312 点でした
本選通過したようです
プロがたくさん生える合宿だ＞＜つらい
  • 自分の高校からは4人出場らしいので、部活の顧問を加えて5人でオリセンに入ろうとする
  • 怖い
  • まだ時間がありそう
  • なので、その前に明治神宮へ行き神頼みを実施する
  • 荷物が重い
  • 15:00くらいにチェックイン
  • 大会のプレッシャーに押し潰されそうになる
  • 落ち潰された
  • プラクティスフェーズが生える
  • 自分の席の位置が一番前の真ん中でハラスメント
  • 緊張する
  • やろうとする
  • Firefoxが固まってる(訴訟
  • 自分のせいだつらい(悲観
  • スタッフの方々が対処してくれたみたい
  • 説明を何も聞いてなかった
  • 察する
  • ソースコードが保存できない
  • 自分が押してたのは Ctrl+X,Sだと思っていたのに Fn+X,Sだった
  • キーボードの配置がつらくて首元が冷える
  • 30分くらいで全完する
  • 暇だったので1問目に悩む
  • 遅延評価のセグメント木とBinaryIndexTreeで解けそうだったので実装する
  • できてるみたい
  • 講演会が生える
  • 聞く
  • 機械学習やってみたいね
  • 食べる
  • お腹すいてたのでたくさん食べる
  • コーラをこぼしそうになる
  • 自己紹介フェーズがあるみたい
  • ハラスメント的な自己紹介があったりと多種多様
  • 自分は何言おうかコミュ障並の頭で悩む
  • 緊張する
  • 1人あたりの時間が少なそうだから,言いたいことを1つに決める
  • 『男の子が好きです、その気がある人は(ry』
  • 最後の方に付随者が生えて嬉しい
  • その彼から名刺を貰う
  • 嬉しい
  • その後宿泊施設へ
  • 全員個室らしい
  • 同校の人たちと色々話す
  • 11時頃に睡眠フェーズがやってきた
  • 寝る
  • 寝れない
  • 寝たふりをする
  • 寝れない
  • 起きる
  • 寝れない
  • 緊張(別の理由があるきがする)のあまり眠れない
  • 気づいた時には2時半
  • つらいことを考え始める
  • JOI本選0完不可避
  • さすがに焦りを感じ寝る努力をする
  • 寝れない
  • 寝る→寝れない→寝る→・・・の閉路ができてた気がする
  • これSCCしてみたら1つしか強連結成分が無いんだなあとよくわかんないことを考えはじめる
  • 気づいた時には5時半
  • つらい
  • 頭が重い
  • 自分のような人は睡眠フェーズに失敗するのは自明だったんだと後悔する
  • この時間に本選落ちが確定してる
  • かなりねむい
  • とてもねむい
  • 朝食
  • ねむくてよくわかんないや
  • ふつうに美味しかったと思う
  • 待機室へ
  • 気持ち悪いつらい
  • 絶望
  • 競技会場へ
  • ここまで来たら仕方ない
  • やるしかNASA
  • OverViewシートから察しようとする
  • 2問目のメモリ制約と制限時間が目立つ
  • 始まった
  • 1問目
  • むずい
  • なんか難化している
  • 軟化な気がする
  • 眠くてよくわからない
  • ちょっと考えると、その鉄道の使用回数がわかればあとは比べるだけということがわかる
  • セグメントツリーの範囲加算が使えそう(オーバーKILL)
  • 流石に眠い頭でこんなものを実装できるわけない&これは1問目だよなと疑う
  • imos法が生える
  • Imos[i] += Imos[i - 1];だけでいいのに焦りしかないのでよくわかんないことをする
  • バグらせる
  • 30分が経過しそう
  • 焦る
  • 経過した
  • 人権を失う
  • 多分みんな1問目は既に通してるんだよなあと自分の頭の無さに絶望する
  • よくわからないデバッグをしてサンプル一致したので提出
  • Accept
  • 家帰って書いたソースコードです(落ち着いてかけてるからソースは汚くない)
  • #include<bits/stdc++.h>
using namespace std;
typedef long long int64;
int main(){
  int N, M;
  cin >> N >> M;
  vector< int > P(M);
  for(int i = 0; i < M; i++){
    cin >> P[i];
    --P[i];
  }
  vector< int > A(N - 1), B(N - 1), C(N - 1);
  for(int i = 0; i < N - 1; i++){
    cin >> A[i] >> B[i] >> C[i];
  }
  vector< int64 > Imos( N + 1, 0);
  for(int i = 1; i < M; i++){
    int u = P[i - 1], v = P[i];
    if(u > v) swap( u, v);
    ++Imos[u];
    --Imos[v];
  }
  for(int i = 1; i < N - 1; i++){
    Imos[i] += Imos[i - 1];
  }

  int64 ret = 0;
  for(int i = 0; i < N - 1; i++){
    ret += min( A[i] * Imos[i], C[i] + B[i] * Imos[i]);
  }
  cout << ret << endl;
}
  • レスポンスがFastって感じだ
  • 提出後フィードバックは15分以内はとても保健があると思う
  • 2問目
  • 焦ってるのでよくわからない
  • どう考えてもDPっぽい
  • DP書こうとする
  • O(N^3)しか無理じゃんと思ってやめる
  • どうするんだろう(途方
  • 難しそうだしやめよう(これがダメだった
  • 人権を失った(2回目)
  • 3問目を見る
  • さらに焦ってるのでさらによくわからない
  • ダイクストラして二分探索して最小全域木作って累積和だとかいう嘘々ワードが計算用紙に飛び交う
  • つらい
  • 予選落ちするべきだったんだと後悔する
  • とりあえず話にならないから、やるだけを書く
  • できない
  • そもそもDijkstraをバグらせてる
  • うれしい(うれしくない
  • Dijkstraを世界一書けない
  • プラクティスでDijkstraを実装するべきだった
  • いろいろ頭悪そうなことしてる
  • Dijkstraできる
  • 制約的にやるだけでも部分点60をとれそう
  • RE(部分点60)
  • 読み通り
  • ここらへんで2時間が経過した気がする
  • 目が覚めてくる
  • 高速化は意外にも部分点ソースを眺めていると自明にできそう
  • 単調増加になっている
  • 前のコスト的なのを保存してやるだけ
  • Accept
  • 嬉しい
  • 水500ml一本を消費
  • トイレへ行きたくなる
  • 行く
  • すっきり
  • 2問目に戻る
  • 目が覚めてきたのでさっきまで頭数が開始から単調減少して負数個になっていたけどここで増加し始める
  • メモリ制約から察するに dp[2000][2000][2]を確信
  • [2]はいらなかったらしいけど定数倍な
  • ループむずい
  • 既出問でこんなものがあった気がする
  • 具体的には ICPC Summer 2011 - Magical Girl Sayaka-chan これを思い出す
  • 円環を2つの直線で考えたような気がする
  • よくよく考えれば dp配列は開始位置が変わってもそのままでよかったことに気づく(遅い
  • 書く
  • すらすら書ける
  • バグる
  • 人権を失う(3回目
  • ダメだ
  • この辺で3時間が経過した気がする
  • 焦る
  • 最後のピースを無視してただけだった
  • #include<bits/stdc++.h>
using namespace std;
typedef long long int64;

int N;
vector< int > A;
int64 dp[2000][2000];
inline int NEXT(int a){ return((a + 1) % N); }
inline int PREV(int a){ return((a + N - 1) % N); }

inline int64 rec(int left, int right, bool flag) {
  if(left == right) return(flag ? 0 : A[left]);
  if(~dp[left][right]) return(dp[left][right]);
  int64 ret = 0;
  if(flag) {
    if(A[left] < A[right]) ret = rec( left, NEXT(right), false);
    else ret = rec(PREV(left), right, false);
  } else {
    ret = max( rec(PREV(left), right, true) + A[left], rec(left, NEXT(right), true) + A[right]);
  }
  return(dp[left][right] = ret);
}


int main()
{
  fill_n( *dp, 2000 * 2000, -1);

  cin >> N;
  A.resize(N);
  for(int i = 0; i < N; i++) {
    cin >> A[i];
  }
  int64 ret = 0;
  for(int i = 0; i < N; i++) {
    ret = max( ret, rec( PREV(i), NEXT(i), true) + A[i]);
  }
  cout << ret << endl;

  return(0);
}
  • これも後日書いたやつ。余分な次元を省略してあります
  • 提出
  • Accept
  • 大分落ち着きを取り戻す
  • だけどノーマル3完はプロN人(N≧20)に負けると思う
  • 4問目か5問目
  • 4問目を読む
  • やりたいことはすぐわかる
  • これをどうやって効率的に解くのか全くとして分からない
  • 考える
  • わからない
  • 時間が終了に近づいてきていることに気づく
  • もうちょっと考える
  • わからない(こなみ
  • THE 全探索
  • これ以降は少ない時間の中,全探索に特化する人間になることを決意する
  • USE next_permutation()
  • WA 0点
  • つらすぎでしょ
  • 全探索すら書けない
  • 人権を失う(INF回目
  • 特に間違いが見当たらないので再度提出(意味がない
  • WA 0点(2回目
  • 本当に間違いが見当たらないので再々度提出(意味がさらにない
  • WA 0点(3回目
  • なんか全探索できてなさそうなので適当にprintf()デバッグする
  • なぜかnext_permutation()で全パターンが生成されていない(おどろいた(こなみ
  • 予選のときもあったような気がしたけどGCCからのハラスメントに違いないと思う
  • よくわからなさ
  • THE 再帰
  • next_permutation()が使えないなら再帰を書いて全列挙
  • 学校の授業が役に立ってバグをはやさなかった
  • 提出
  • 部分点 8点
  • うれしい(うれしくない
  • GCCの使用をやめたくなる
  • こんな部分点誰でも取れると自戒して5問目の部分点を狙う
  • 2次元累積和
  • 忘れた
  • 5問目の部分点4点すら取れない
  • つらいので帰りたくなる
  • よくよく考えれば何やっても間に合いそう
  • 1次元の累積和
  • 書けた
  • たくさんループを回す
  • 提出
  • 部分点 4点
  • ここから20分くらいある
  • 4問目が全くわからないのでまだ5問目が可能性あるなあと思って考察
  • 障害物が小さいケースは全通りの枠から引っかかる枠を引けば早そうだと気づく(残り15分
  • 算数できない
  • 全通りの計算はかろうじて出来た
  • あとはごにょごにょやろうとする
  • 重複があることに気づく(残り10分
  • どうやって処理するんだろう
  • 終わり
  • 解説聞く
  • 得点分布で身の危険を感じる
  • ボーダー 304, 308, 312, 324あたりっぽい
結論:ここまで寝れないとは思わなかった

4問目を解いた。二分探索してDPっぽい。
解説聞けばなるほどって感じだけどわかんなかった。
#include<bits/stdc++.h>
using namespace std;
typedef long long int64;
const int64 INF = 1LL << 55;

int toChild[1000000][3];
int Buffer[99999];
vector< int > Dwill;
int64 dp[1000000];
int N, M;

int MakeTree(){
  queue< int > que;
  for(int i = 0; i < N; i++){
    que.push(i);
    toChild[i][0] = -1;
    toChild[i][1] = -1;
    toChild[i][2] = -1;
  }
  int nextIndex = N;
  while(que.size() > 1){
    int a = que.front(); que.pop();
    int b = que.front(); que.pop();
    int c = que.front(); que.pop();

    toChild[nextIndex][0] = a;
    toChild[nextIndex][1] = b;
    toChild[nextIndex][2] = c;
    que.push(nextIndex);
    ++nextIndex;
  }
  return(que.front());
}

int64 getDP(const int64& Value, int index) {
  if(~dp[index]) return(dp[index]);
  if(toChild[index][0] == -1){
    if(Buffer[index] == 0) return(1);
    else if(Buffer[index] >= Value) return(0);
    else return(INF);
  } else {
    int64 array[] = { getDP(Value, toChild[index][0]), getDP(Value, toChild[index][1]), getDP(Value, toChild[index][2])};
    sort( array, array + 3);                                                                                             
    return(dp[index] = min(INF - 1, array[0] + array[1]));
  }
}

bool Calclation(int64 Value, const int& root){
  int High = Dwill.end() - lower_bound( Dwill.begin(), Dwill.end(), Value);
  fill_n( dp, 1000000, -1);
  return(getDP(Value, root) <= High);
}

int main() {
  cin >> N >> M;
  for(int i = 0; i < M; i++){
    int D, P;
    cin >> D >> P;
    --P;
    Buffer[P] = D;
  }
  Dwill.resize(N - M);
  for(int i = 0; i < N - M; i++){
    cin >> Dwill[i];
  }
  sort( Dwill.begin(), Dwill.end());
  int root = MakeTree();
  int64 low = 0, high = INF;
  while(high - low > 0){
    int64 mid = (low + high + 1) / 2;
    if(Calclation(mid, root)) low = mid;
    else high = mid - 1;
  }
  cout << low << endl;
}
投稿者 時刻:

0 件のコメント:

コメントを投稿

登録: コメントの投稿 (Atom)