PCK2015本選参加記

参加記というか、参加した証拠(入賞)すら得られていないので敗北記。

• 浜松 -> 会津若松
• 東海道新幹線と東北新幹線をクリアした後、磐越西線
• 東海道新幹線はINF回目だけど、その後ははじめて
• 東北新幹線は4列
• レールが狭いから?
• なんか新幹線競プロしてたのですぐ着く
• 昨年のICPCを適当に
• 4完
• 磐越西線は闇
• 狭い
• 長い
• さすがに在来線競プロは不可能
• 1時間強
• 18時到着
• そんな寒くない
• ホテルへチェックイン
• ワシントンホテル(みんなそうらしい
• 我々は和室
• 畳の匂い
• 夕ごはん
• ラーメン二郎
• ちょっと並ぶ
• 周りはほとんど高校生や大学生
• 熱い
• 舌やけどした
• 美味しい
• 周りからの視線をちょっと気にする
• (側近の方が居座ってないではやく。。って言ってたから)
• ちょっと早く食べる
• 意外と胃が大きい
• 早食いフェーズはAcceptした気がする
• ちょっと足りないのでプリン
• 甘い
• さらに競プロ
• 一昨年のICPC
• 4完
• 昔解けた素数洞穴解けないけどなんなの
• 時間が溶けた
• 解法合ってるのになんか通らない暗示?
• 睡眠フェーズ
• 寝れるはずがない(n回目
• n ≧ 5
• n = 1とか 2 とかのときよりは余裕で寝れたと思う
• っていうか、福島県寒いって聞いてたけど暑い
• 暑くて眠れない
• 2日目
• 朝食
• 適当に済ませる
• 納豆がないのでつらい
• コンビニへ昼食を求めに行く
• 納豆巻がある
• 買う
• やったね
• バスに乗って会津大へ
• 昼食
• 酢飯に納豆はあわn
• でもおいしい
• プリンもクリームがかたよってたけど美味しい
• 開会式
• 見たことがあるひとが多い
• 筧先生知ってる
• 競技
• 最も辛い瞬間
• とりあえず1問目を相方に任せる
• 3 を読むけどこれ桁DPだ(甘い考察
• ICPCの覆面算だっけ
• 4 を読むけど日本語が分からなくてつらい
• 10分くらい、・・・。って感じ
• ボッコｔかマルグとかで作問者を推察
• なんかこれ多倍長でしょっておもう(幼児並の考察
• なんかこれ繰り返し二乗法でしょっておもう(小学生並の考察
• そもそも問題文読めないし焦っている
• その後10分眺めてなかったことにして、5を読む
• 20秒眺める
• あっこれ校内のオンランジャッジに入ってるUSACOの問題そのままだ
• 解けそう(明確な確信
• 相方や周りのチームの状況を見るけど、1問目なんなんだろう
• なかったことにして 2 問目
• 裏で私が 1 を考察
• これなんか面倒くさい全探では
• 頭いいやり方と悪いやり方がありそう
• 明確に頭がわるいやり方
• 2 問目Acceptしたらしい
• 1 問目時間かかりそうだけどやる
• x,yが2つでy,zが2つでx,zが2つあれば良いなぁ
• 適当に割り振ってソートしてぎゅわんってやる
• 汚いソースコードになってしまった
• なんとか賞とれない
• とれる解法ではない
• いろいろあったけどサンプル一致したので提出
• Accept
• 3 問目も時間かかりそうだけどやる
• メモ化なんていらなさそう
• 覆面算のソースを脳に思い浮かべながらそれをコピー
• 入力がめんどくさい
• バグバグ
• ビット操作に失敗している
• (ここnext_permutation()使ったら良かったね)
• FCSとかヘッダ・チェックサムとか私の頭に実装されていれば良いのに
• つらい
• なんとかつじつまを合わせたけどいろいろ合わない
• 入力形式が違ってた、つらい><
• 時間を失い頭を失う
• なおすと通ったので提出
• Accept
• 4 問目はよくわからないので相方に和訳してと懇願
• 5 問目は絶対的確信があったので3分で実装して提出
• Accept
• 4 問目の和訳が終了したらしい
• どうやら多倍長は計算量がつらいらしく、繰り返し二乗法も使えなさそう
• 2^a * 2^b = 4^(a+b) という新定義を導き出す
• Σ4^(ai+bi) からひいてけばいいのかなぁ
• 4のpiyo乗と2のhoge乗を組み合わせるのつらくね?
• 結構時間がたったあと 2^a * 2^b = 2^(a+b) だったことに気づく
• 数学疎い
• てかこの問題数学とかではないのでは
• なんか2^(a+b)と2^xの形になってるわけだし、2は外せるのでは
• そんなイメージをもって、なんか図を書く
• やっぱa と b 足して、右に伝搬させながら割るだけでは
• この制約で線形解は自明かつ自明
• 解法かっこいいよね
• よい
• 提出
• Accept
• ココらへんで引率の顧問が気になる
• ちょっと後ろ見上げて探す
• 真ん中ら辺
• どうでもよかった(我に帰る
• 6はまだ誰も提出していないので闇
• 7は読むのがめんどい
• 8は割と区間DPで行けそう
• テストケース20個だし、O(n^3)だろうなぁ
• 幅決めて終始点決めて、なんか頑張ってMerge
• かなりつらい
• なんか考えてみると パターンがいろいろありそう
• ちょっとなぁ
• 9も見てみる
• 複数の交差判定を logNあるいはlog^2 n でやりたいわけね
• データ構造ゲーかなぁ
• 解けそう
• Y軸とX軸を分けると楽そう
• ある線が新たに加えられる線分とする
• 直交する線との交差判定(平行線同士は適当で
• ノードにx or y座標の集合を持たせておけば、にぶたんでその区間内に横線があるかどうかわかる
• 区間へのx or y座標の追加と、区間の線分の有無を調べる機能をもたせれば良さそう
• X軸Y軸を入れ替えて2つseg木生やせば余裕そう
• いろいろバグってるけどなんとか終わる(20分前
• (ていうかここで20分前なのね><)
• 提出
• 不正解
• 平行線同士を適当にやったのが裏目に出ていそう
• なんかとまどいつつなおす
• 提出
• メモリ超過
• そんなメモリ厳しいんだ
• で、あとこれ解は正しいんだ
• しっかりメモリのことを考えて丁寧に実装
• メモリと仲良くしたい
• 提出
• 時間超過
• えっ・・・・。
• あーーーー。
• 5秒でO(Nlog^2N)おちるの
• logNが20程度だから・・・400 × 10^5 = 4 * 10^7
• POJかな
• 二分探索の回数を半分にした
• 提出
• 時間超過
• けどちょっと早く終わった気がする
• ・・・。
• 定数倍改善ゲーなの(疑心暗鬼
• 途中にrand() % 2を埋め込んで提出
• 不正解
• 定数倍改善ゲーなの()
• 時間がきてしまった
• 撃墜
• ホテルへ
• あれ名札がない
• 名札がないと明日の昼食が
• スタッフへ
• 何とかしていただけるらしい
• 申し訳がない感じ
• あとから9問目はジャッジのプロに時間制限5秒で、手元で7秒とか言われてかなしい
• かつ解は正しいらしい
• 悲しみの果て
• よくよく考えるとこれ春合宿のときも無駄な定数で落とした気がする
• 私が書いた任意のコードに定数INFがかかっているのでは
• 留年すれば2度目のチャンスがありそう(進路決まってたりして誰も許さなさそう
• あと学ランを着ていて暑くなったので脱いだ
• 名札あった。
• (申し訳がない感じ)^2
• スタッフへ
• じゃんけん大会
• 最初にパーだして負けたのでかなしい
• 翌日9問目について痛恨の事実が判明
• 平衡二分木のSTLのsetを使うところは良かったらしい
• setのlower_bound()するところでSTLのlower_bound()を用いていた
• ランダムアクセス不可能なのでO(N)
• seg[k].lower_bound(x) でよかった
• ていうかなにを考えてSTLを使ったんだろう(多分何も考えてない
• 座標圧縮フェーズでSTLのやつ使った(これはvectorでO(logN))からその流れかも
• そこ直す(3箇所)
• 手元で0.2秒になる
• 出したやつ、O(N^2logN)だしそりゃ間に合わないよね
• 表彰式
• 10位(悲しみ
• あれ解けてたら5位だったのにつらい
• 6やって1WA以内なら8位だったみたいだけどこれは結果論っぽい
• でも6やって9やらなきゃ悔いは少なかったかも

PCK2015予選参加記

• はじまる
• 最初の方は相方のプロに任せてちょっと後半を読む
• 7はパッと見、UnionFind
• そう考えてるうちに3完したらしい
• 7問目の実装
• 10分
• やるだけ
• 出し渋る(?
• 5問目を読む
• 線形
• 5分
• 4問目も相方のプロが解く
• 5問目と7問目を出す
• 5問目AC
• 7問目WA(絶望
• 1箇所Find()していない
• なおす
• AC
• 8, 9問目を読む
• 8はTrie木?
• 9は幾何(閉じ
• 6を読む
• 変化したところだけ見れば良さそうなイメージ
• 実装も軽い
• かんたん
• AC(光
• やっぱり、8はTrie木でできそう
• かんたん
• Submit
• WA
• MLE
• WA
• MLE
• あー
• 世界一MLEする
• メモリが厳しそう
• MLEどれくらいだろう
• 諦めて9問目
• 共通部分
• ライブラリ写経
• Submit
• WA
• WA
• WA
• 世界一WAする
• 終わり
• 凍結前10位
• どうせ、12位くらいかそこらだし予選落ちでは
• 地域枠に頼るしかない実力NASA
• どうだろう

SuperCon2015参加記

• Day1
• 去年の本選は初めてのオンサイトからの緊張と、熱中症で敗北(11位)していた
• 今年は流石に去年よりは頑張ろうという決意を胸に新幹線
• 座席は顧問の隣
• 緊張してきた
• 関東あたりの大雨で新幹線が遅延
• 遅刻が生えそう
• 正確には自分の新幹線はもともと遅れてなかったけど、帳尻合わせなのか停止信号やら後続列車の待ち合わせやらで結局遅れる
• これ大会中、任意の人に抜かされることを暗示しているのではと恐れる
• 10分遅れて大阪IN
• 適当に行ってたら間に合う
• 課題を見る
• 流石にCCAは二次元累積和(確信
• 周期的境界条件というやつらしい(要するにドーナツ状)ので、周り2マスを余分にコピペしておけば便利そう
• (N+4)*(N+4)に拡張したわけね
• 書く
• マッチングも適当に書く(書いたの私の他のプロなんだけど
• マッチング早い
• チームメートがプロ
• 夕食は学食
• ベジタブルカレーを生やす
• 安い
• おいしい
• レシートを見ると、バランスがよかった
• うれしい
• CCAバグる
• 盤面更新してなかった
• すぐ直る
• マッチングとマージ
• 動く
• サンプル一致
• N = 2000も試す
• 0.1s????
• マッチングをホテルで考えることにする
• ハッシュ使うとよさそうだけどめんどい
• 累積和があるので、任意の状態の個数で枝狩りできそう
• 終わる
• ホテルにチェックイン
• 寝れない
• Day2
• 寝れるはずがなかった
• たぶん睡眠時間の最小値でDPしていたと思う
• おかげで睡眠の満足度も睡眠時間と比例関係にあったらしく、最小値を得た
• 朝食
• コンビニ
• 納豆を買おうとしたけどやめた
• 0.1sは流石に詐称だったことに気付いて落ち込む
• #define N 16 とかしてあるせい
• 入力で N を与えたい
• マッチング多少改良して、CCAに悩む
• プロセス並列化とかベクトル並列化とかプロそうにされている
• N = 2000 とか1問20分必要
• (累積和(確信なので頭がついていない
• いろいろやったけど変わらなかった
• 一日無駄にした気がする
• つらい
• 夜
• ホテル近くの飯屋
• おいしい
• ホテル
• ポッキーゲームとかする
• Day3
• 寝れた
• 朝食はコンビニ
• 納豆を買おうとしたけどやめた
• アイデアが生えないし詰んでいる
• ボーと過ごす
• 昼食は学食
• 親子丼だったような
• おいしい
• このままだと最下位
• いろいろ調べてみると、累積和がネック
• あれ、これベクトル化+並列化で O(N)では？
• マクロって遅い??
• どう考えてもにゅわわーーんとしか計算できない気がする
• これ最初に気付くべきだったのでは
• 絶望しながら、一つ一つのマスで周り25マスを単純に数えるやつを書く
• こんなの10分
• なんかめっちゃはやい
• 世界が変わった
• N = 2000 で 50000ステップ200s
• 間に合いそう
• 10分≫2日半なので面白い
• ていうかこんなやるだけ、だれでも書けるのでは
• 最も頭がついていない瞬間だった
• きっと今頃、ほかの人々ビット演算のプロしたり、ハッシュのプロしたりしているんだろうなあと思う
• CCA30行くらいなので面白い
• ホテルに戻りCCAの案を練る
• Day4
• のんのんびよりを見る
• かなり寝れた
• 早速ホテルで考えた案を試す
• ベクトル化の性質上無理なことに気が付く
• ビット演算とか実装間に合いそうじゃないし時間がなくてつらい
• なんかもうすべてが面倒になった
• 結局最下位では
• そのまま終わり
• 10分で書いたCCAのソースが解答になってしまってつらい
• 惰性から周囲2マスの余分なコピー適当(O(N^2))でやってたけど、これなくせたのではと気付く
• なんか感覚的に速度が2/3くらいになりそう
• 午後は遊んだ
• 梅田で迷う
• 去年の修学旅行でも迷った気がする
• 世界一道迷いしている
• こんなところで日本道迷いオリンピックは不要
• 最終日なので、ちょっと頑張って起きている
• Day5
• 友達の部屋で起きている
• 起きている
• 意識がなくなる
• 3時くらいに起きる
• 自分の部屋に戻る
• 意識が消滅
• TLEを生やす(9時に起こされる)
• 全く荷造りしていない
• 9時出発なのにつらい
• 全力でバッグに詰め込む
• 15分経過
• 迷惑かけているつらい
• 全力で1階へ
• 途中で鍵を忘れたことに気付く
• つらい
• 最長経路している
• 自分にとって1Fと6F(自分の個室)しか不要なので座圧してほしい
• ごめんね
• 表彰式
• あれ、やっぱり最下位(全完)では
• 自分の学校、校訓がないことを知る
• そういえば聞いたことがない
• 休憩時間にがっこうぐらしを見る
• よく聞こえないけど頑張る
• 結果
• ブービー賞(全完)だった
• 6位
• 2日目あたりに頭ついていたりすればもうちょっとよかったのかも
• 適当なところをもうちょっと真面目にやったりできた気がする
• 累積和が悪い
• 競プロとSuperconは違うんだね
• 善戦()だった
• PCK予選も善戦()にならないようにしないと

PKU3368 Frequent values

問題概要

a[] = { a₁, a₂, a₃, ... , a_n } の増加部分列が与えられる。
a[i,j]の区間の最頻値が何度現れるかというクエリQ個(Q ≦ 10⁵個)に答えよ。

解法

見た感じセグ木で解けそうな問題。
それぞれの数字の出現回数を求めて、ノードに最大値と合計の情報を持たせたセグ木に入れる。
合計の情報は累積和でやっても同じ。
クエリに対しては、合計の情報より二分探索で左端と右端を求めてRangeMaximumQuery。
左端と右端は微妙に被るので、例外処理する。
これで計算量はO((さんきゅー + N) log N) くらいになる。

ソース

#include<bits/stdc++.h>
using namespace std;
typedef pair< int, int > Pi;

struct SegmentTree {
  int sz;
  vector< int > data, big;
  SegmentTree(int n) {
    sz = 1;
    while(sz < n) sz *= 2;
    data.assign(2 * sz + 1, 0);
    big.assign(2 * sz + 1, 0);
  }
  Pi Lower_Bound_Lower(int k, int x) { // 上の節目からどれだけ離れているか
    if(k >= sz - 1) return(make_pair(k - sz + 1, data[k] - x));
    if(data[2 * k + 1] >= x) return(Lower_Bound_Lower(2 * k + 1, x));
    return(Lower_Bound_Lower(2 * k + 2, x - data[2 * k + 1]));
  }
  int RangeMaximumQuery(int a, int b, int k, int l, int r) {
    if(a >= r || b <= l) return(0);
    if(a <= l && r <= b) return(big[k]);
    return(max(RangeMaximumQuery(a, b, 2 * k + 1, l, (l + r) >> 1), RangeMaximumQuery(a, b, 2 * k + 2, (l + r) >> 1, r)));
  }
  int Query(int a, int b) { // [a,b)
    Pi Left = Lower_Bound_Lower(0, a), Right = Lower_Bound_Lower(0, b);
    int l = data[sz - 1 + Left.first] - Left.second - 1, r = Right.second;
    if(Left.first == Right.first) return(data[sz - 1 + Left.first] - r - l);
    int hasiL = data[sz - 1 + Left.first] - l;
    int hasiR = data[sz - 1 + Right.first] - r;
    return(max(max(hasiL, hasiR),RangeMaximumQuery(Left.first + 1, Right.first, 0, 0, sz)));
  }
  void Update(int k, int x) {
    k += sz - 1;
    data[k] += x;
    big[k] = data[k];
    while(k > 0) {
      k = (k - 1) >> 1;
      data[k] = data[2 * k + 1] + data[2 * k + 2];
      big[k] = max(big[2 * k + 1], big[2 * k + 2]);
    }
  }
};


int main() {
  int n, q, digit[100000];
  while(scanf("%d", &n), n){
    SegmentTree seg(200002);
    scanf("%d", &q);
    for(int i = 0; i < n; i++) {
      scanf("%d", &digit[i]); digit[i] += 100000;
    }
    int cnt = 1;
    for(int i = 1; i < n; i++) {
      if(digit[i - 1] != digit[i]) {
        seg.Update(digit[i - 1], cnt); cnt = 1;
      } else {
        ++cnt;
      }
    }
    seg.Update(digit[n - 1], cnt);
    
    for(int i = 0; i < q; i++) {
      int a, b;
      scanf("%d %d", &a, &b);
      printf("%d\n", seg.Query(a, b));
    }
  }
}

JOI春合宿2014 Day2-1 Water Bottle

解法

隣り合っている建物について辺を張って,最小全域木作って，Queryに早く答える。
BFSすれば,隣り合っている建物がわかって嬉しい(経路中に建物をまたぐ移動は嬉しくないのは自明)
これでO(HW)。
それで,辺のコストが小さい順につないでいけば,最短距離がわかって(集合と集合がつながったタイミングのコスト)さらに嬉しい。俗に言う最小全域木。
この際に,俗に言うデータ構造をマージする一般的なテクを使ったら部分点70が生えた。
よくよく考えると、O(HW + HW log HW + (P log^2 Q)) ≒ O(2*10^8)くらい(適当)。
間に合ったりしても良さそうだけど,定数や入出力が重かったりしてわりとつらい。(←嘘ついた、マージしても間に合う。(下のソース)
さらに高速化を考えなければいけないんだけど、そのときにLCAを使うとよい。
最大値もダブリングして一緒に計算すれば,1つのクエリーに対数時間で答えることが出来て、 O(HW+HWlogHW+(P + Q)logP) ≒ O(10^8)になって,100点が生える。

ソース

#include<bits/stdc++.h>
using namespace std;
struct edge {
  int u, v, cost;
  bool operator<(const edge& e) const {
    return cost < e.cost;
  }
  bool operator==(const edge& e) const {
    return(u == e.u && v == e.v && cost == e.cost);
  }
};
struct edge2 { 
  int to, cost;
};
typedef pair< int, int > Pi;
typedef pair< int, Pi > Pii;
typedef vector< edge > Edges;
typedef vector< vector< edge2 > > Graph;
const int INF = 1 << 30;
const int LOG_MAX = 20;

struct UnionFind {
  vector< int > data;
  UnionFind(int sz) {
    data.assign( sz, -1);
  }
  int Union(int a, int b) {
    a = Find(a), b = Find(b);
    if(data[a] < data[b]) swap( a, b);
    data[b] += data[a];
    data[a] = b;
    return(b);
  }
  int Find(int a) {
    if(data[a] < 0) return(a);
    else return(data[a] = Find(data[a]));
  }
};

int H, W, P, Q;
int A[200000], B[200000], S[200000], T[200000];
bool mas[2000][2000];
Pi Number[2000][2000];
Edges edges;
Graph graph;
int Depth[200000];
int up[LOG_MAX][200000];
int upc[LOG_MAX][200000];


void bfs() {
  queue< Pi > que;
  static const int dy[] = { 0, 1, 0, -1}, dx[] = { 1, 0, -1, 0};
  fill_n( *Number, 2000 * 2000, make_pair(-1, -1));
 
  for(int i = 0; i < P; i++) {
    que.push(make_pair(B[i], A[i]));
    Number[A[i]][B[i]] = make_pair(0, i);
  }
  while(!que.empty()){
    Pi p = que.front(); que.pop();
    for(int i = 0; i < 4; i++) {
      int nx = p.first + dx[i], ny = p.second + dy[i];
      if(nx < 0 || ny < 0 || nx >= W || ny >= H || mas[ny][nx]) continue;
      if(Number[ny][nx] != make_pair(-1, -1)) continue;
      Number[ny][nx] = Number[p.second][p.first];
      Number[ny][nx].first++;
      que.push(make_pair(nx, ny));
    }
  }
  return;
}
 
void make_graph() {
  for(int i = 0; i < H; i++) {
    for(int j = 0; j + 1 < W; j++) {
      int u = Number[i][j].second, v = Number[i][j + 1].second;
      if(u < 0 || v < 0 || u == v) continue;
      int cost = Number[i][j].first + Number[i][j + 1].first;
      edges.push_back((edge){u, v, cost});
    }
  }
  for(int i = 0; i + 1 < H; i++) {
    for(int j = 0; j < W; j++) {
      int u = Number[i][j].second, v = Number[i + 1][j].second;
      if(u < 0 || v < 0 || u == v) continue;
      int cost = Number[i][j].first + Number[i + 1][j].first;
      edges.push_back((edge){u, v, cost});
    }
  }
  return;
}

void make_MST() {
  graph.resize(P);
  UnionFind uf(P);

  sort( edges.begin(), edges.end());
  edges.erase(unique(edges.begin(), edges.end()), edges.end());
  for(int i = 0; i < edges.size(); i++){
    edge& e = edges[i];
    if(uf.Find(e.u) == uf.Find(e.v)) continue;
    uf.Union( e.u, e.v);
    graph[e.u].push_back((edge2){e.v, e.cost});
    graph[e.v].push_back((edge2){e.u, e.cost});
  }

  for(int i = 1; i < P; i++) {
    if(uf.Find(i - 1) == uf.Find(i)) continue;
    graph[i - 1].push_back((edge2){i, INF});
    graph[i].push_back((edge2){i - 1, INF});
    uf.Union(i - 1, i);
  }
  
}
int dfs(int idx, int prev, int cost) {
  if(prev == -1) {
    for(int i = 0; i < LOG_MAX; i++) {
      up[i][idx] = -1;
    }
    Depth[idx] = 0;
  } else {
    up[0][idx] = prev, upc[0][idx] = cost;
    Depth[idx] = Depth[prev] + 1;
    for(int i = 1; i < LOG_MAX; i++) {
      if(up[i - 1][idx] < 0) {
        up[i][idx] = -1;
      } else {
        up[i][idx] = up[i - 1][up[i - 1][idx]];
        upc[i][idx] = max( upc[i - 1][idx], upc[i - 1][up[i - 1][idx]]);
      }
    }
  }
  for(int i = 0; i < graph[idx].size(); i++) {
    edge2& e = graph[idx][i];
    if(e.to != prev) dfs( e.to, idx, e.cost);
  }
}

void make_LCA() {
  dfs( 0, -1, 0);
}

int queryLCA(int a, int b) {
  if(Depth[a] > Depth[b]) swap(a, b);

  int ret = 0;
  for(int k = LOG_MAX - 1; k >= 0; --k) {
    if((Depth[b] - Depth[a]) >> k & 1){
      ret = max(ret, upc[k][b]);
      b = up[k][b];
    }
  }
  if(a == b) return(ret);
  for(int k = LOG_MAX - 1; k >= 0; --k) {
    if(up[k][a] != up[k][b]) {
      ret = max( ret, max( upc[k][a], upc[k][b]));
      a = up[k][a]; b = up[k][b];
    }
  }
  return(max(ret, max(upc[0][a], upc[0][b])));
}

 
int main() {
 
  scanf("%d %d %d %d", &H, &W, &P, &Q);
  getchar();
  for(int i = 0; i < H; i++) {
    for(int j = 0; j < W; j++) {
      char c;
      scanf("%c", &c);
      mas[i][j] = (c == '#');
    }
    getchar();
  }
  for(int i = 0; i < P; i++) {
    scanf("%d %d", &A[i], &B[i]);
    --A[i], --B[i];
  }
  for(int i = 0; i < Q; i++) {
    scanf("%d %d", &S[i], &T[i]);
    --S[i], --T[i];
  }
 
  bfs();
  make_graph();
  make_MST();
  make_LCA();

  int ret;
  for(int i = 0; i < Q; i++){
    printf("%d\n", (ret = queryLCA(S[i], T[i])) < INF ? ret : -1);
  }
}

#include<bits/stdc++.h>
using namespace std;
struct edge {
  int u, v, cost;
  bool operator<(const edge& e) const {
    return cost < e.cost;
  }
  bool operator==(const edge& e) {
    return(u == e.u && v == e.v && cost == e.cost);
  }
};
typedef pair< int, int > Pi;
typedef pair< int, Pi > Pii;
typedef vector< edge > Edges;
const int INF = 1 << 30;
 
int H, W, P, Q;
int A[200000], B[200000], S[200000], T[200000];
bool mas[2000][2000];
Pi Number[2000][2000];
set< int > data[200000];
Edges edges;
int answer[200000];
 
struct UnionFind {
  vector< int > dat;
  UnionFind(int sz) {
    dat.assign( sz, -1);
  }
  int Union(int a, int b) {
    a = Find(a), b = Find(b);
    if(data[a].size() > data[b].size()) swap(a, b);
    dat[b] += dat[a];
    dat[a] = b;
    return(b);
  }
  int Find(int a) {
    if(dat[a] < 0) return(a);
    else return(dat[a] = Find(dat[a]));
  }
};
 
void bfs() {
  queue< Pi > que;
  static const int dy[] = { 0, 1, 0, -1}, dx[] = { 1, 0, -1, 0};
  fill_n( *Number, 2000 * 2000, make_pair(-1, -1));
 
  for(int i = 0; i < P; i++) {
    que.push(make_pair(B[i], A[i]));
    Number[A[i]][B[i]] = make_pair(0, i);
  }
  while(!que.empty()){
    Pi p = que.front(); que.pop();
    for(int i = 0; i < 4; i++) {
      int nx = p.first + dx[i], ny = p.second + dy[i];
      if(nx < 0 || ny < 0 || nx >= W || ny >= H || mas[ny][nx]) continue;
      if(Number[ny][nx] != make_pair(-1, -1)) continue;
      Number[ny][nx] = Number[p.second][p.first];
      Number[ny][nx].first++;
      que.push(make_pair(nx, ny));
    }
  }
  return;
}
 
void make_graph() {
  for(int i = 0; i < H; i++) {
    for(int j = 0; j + 1 < W; j++) {
      int u = Number[i][j].second, v = Number[i][j + 1].second;
      if(u < 0 || v < 0 || u == v) continue;
      int cost = Number[i][j].first + Number[i][j + 1].first;
      edges.push_back((edge){u, v, cost});
    }
  }
  for(int i = 0; i + 1 < H; i++) {
    for(int j = 0; j < W; j++) {
      int u = Number[i][j].second, v = Number[i + 1][j].second;
      if(u < 0 || v < 0 || u == v) continue;
      int cost = Number[i][j].first + Number[i + 1][j].first;
      edges.push_back((edge){u, v, cost});
    }
  }
  return;
}
 
int main() {
 
  scanf("%d %d %d %d", &H, &W, &P, &Q);
  getchar();
  for(int i = 0; i < H; i++) {
    for(int j = 0; j < W; j++) {
      char c;
      scanf("%c", &c);
      mas[i][j] = (c == '#');
    }
    getchar();
  }
  for(int i = 0; i < P; i++) {
    scanf("%d %d", &A[i], &B[i]);
    --A[i], --B[i];
  }
  for(int i = 0; i < Q; i++) {
    scanf("%d %d", &S[i], &T[i]);
    --S[i], --T[i];
    data[S[i]].insert(i);
    data[T[i]].insert(i);
  }
 
  bfs();
  make_graph();
  sort( edges.begin(), edges.end());
  edges.erase(unique(edges.begin(), edges.end()), edges.end());
  
  UnionFind uf(P);
  fill_n( answer, Q, -1);
  
  for(int i = 0; i < edges.size(); i++){
    edge& e = edges[i];
    if((e.u = uf.Find(e.u)) == (e.v = uf.Find(e.v))) continue;
    int unioned = uf.Union( e.u, e.v);
    int u = e.u, v = e.v;
    if(unioned == u) swap(u, v);
    for(set< int >::iterator it = data[u].begin(); it != data[u].end(); ++it){
      set< int >::iterator cell = data[v].find(*it);
      if(cell != data[v].end()){ // あったらそのときのコストが解
        answer[*it] = e.cost;
      } else {
        data[v].insert(*it);
      }
    }
  }
  for(int i = 0; i < Q; i++){
    printf("%d\n", answer[i]);
  }
}

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;
}

JOI春合宿2008 Day4 Typhoon

解法

適当に座標圧縮してセグ木に台風の情報を持たせれば通る問題。
持たせ方に迷ったけど、そのまま節に突っ込めばO(Qlog(N+Q)logK)くらいになっていい感じになることに気づいた。
台風が小さい方から追加していけば節の台風の番号群は昇順になるから、それからクエリごとにセグメントツリー的に範囲を二分していって、二分探索してサイズを求めれば良さがある。

ソース

#include<bits/stdc++.h>
using namespace std;
typedef long long int64;
typedef pair< int, int > Pi;
typedef pair< int, Pi > Pii;
 
vector< int > nums;
int n, m, k, a[100000], b[100000];
int p[100000], q[100000], r[100000];
 
const int sz = 1 << 19;
vector< int > seg[2 * sz + 1]; 
 
void add(int a, int b, int value, int k, int l, int r){
  if(a >= r || b <= l) return;
  if(a <= l && r <= b) {
    seg[k].push_back(value);
  } else {
    add( a, b, value, 2 * k + 1, l, (l + r) >> 1);
    add( a, b, value, 2 * k + 2, (l + r) >> 1, r);
  }
}
int query(int a, int b, int tA, int tB, int k, int l, int r){
  if(a >= r || b <= l) return(0);
  if(a <= l && r <= b) return(lower_bound( seg[k].begin(), seg[k].end(), tB) - lower_bound( seg[k].begin(), seg[k].end(), tA));
  return query( a, b, tA, tB, 2 * k + 1, l, (l + r) >> 1) + query( a, b, tA, tB, 2 * k + 2, (l + r) >> 1, r) + lower_bound(seg[k].begin(), seg[k].end(), tB) - lower_bound( seg[k].begin(), seg[k].end(), tA);
}
 
 
int main(){
  cin >> n >> m >> k;
  for(int i = 0; i < n; i++){
    cin >> a[i] >> b[i];
    nums.push_back(a[i]);
    nums.push_back(b[i]);
  }
  for(int i = 0; i < m; i++){
    cin >> p[i] >> q[i] >> r[i];
    nums.push_back(p[i]);
  }
  sort( nums.begin(), nums.end());
  nums.erase( unique(nums.begin(), nums.end()), nums.end());
  for(int i = 0; i < n; i++){
    a[i] = lower_bound( nums.begin(), nums.end(), a[i]) - nums.begin();
    b[i] = lower_bound( nums.begin(), nums.end(), b[i]) - nums.begin();
  }
  for(int i = 0; i < m; i++){
    p[i] = lower_bound( nums.begin(), nums.end(), p[i]) - nums.begin();
  }
  for(int i = 0; i < n; i++){
    add( a[i], b[i] + 1, i + 1, 0, 0, 1 << 19);
  }
  for(int i = 0; i < m; i++){
    cout << query( p[i], p[i] + 1, q[i], r[i] + 1, 0, 0, 1 << 19) << endl;
  }
}

JOI春合宿2014 Day4-3 Straps

解法

みた感じDPだけど微妙に出来なみがあるDP。ちょっと考えて、
dp[i][j]: i番目のストラップまで見たときに、残り端子数がj個のときの嬉しさの最大値
と定義してあげると上手くいく。
jが負値になる(=端子がj個足りない)ことがあるので、配列外参照しないようにいい感じにやる。
初期状態がdp[0][N + 1] ← 0としてあるのは、そのため。N個くらい以上端子が足りなくなったら絶望だからそこら辺にずらしておく。

ソース

#include<bits/stdc++.h>
using namespace std;
const int INF = 1 << 30;

int dp[2][4001]; //ストラップ接続数の余裕
int N, A[2000], B[2000];
int main(){

  cin >> N;
  for(int i = 0; i < N; i++){
    cin >> A[i] >> B[i];
  }
  fill_n( *dp, 2 * 4001, -INF);
  dp[0][N + 1] = 0;
  for(int i = 0; i < N; i++){
    for(int j = 0; j <= 2 * N; j++){
      if(dp[i&1][j] == -INF || j + A[i] - 1 < 0) continue;
      dp[(i + 1)&1][j] = max(dp[(i + 1)&1][j], dp[i&1][j]);
      dp[(i + 1)&1][min( 2 * N, j + A[i] - 1)] = max( dp[(i + 1)&1][min( 2 * N, j + A[i] - 1)], dp[i&1][j] + B[i]);
    }
  }
  cout << *max_element( dp[N & 1] + N, dp[N & 1] + 2 * N + 1) << endl;
}

JOI春合宿2014 Day1-2 Growing Vegetables is Fun

解法

この問題いろいろなコンテストで再出題されてる気がする。
その草を昇順降順に並べたときのコストをBIT使って素早く求めておいて、 その情報を元にそのIOI草を左か右どっちに配置するか比べる。

ソース

#include<bits/stdc++.h>  
using namespace std;
const int INF = 1 << 30;

struct BIT{
  vector< int > bit;
  size_t sz;
  int sum(int idx){
    int sum = 0;
    for( ; idx ; idx -= idx & -idx) sum += bit[idx];
    return sum;
  }
  void add(int idx, int value){
    for( ; idx < bit.size(); idx += idx & -idx) bit[idx] += value;
  }
  BIT(int size):sz(size){
    bit.resize(size, 0);
  };
};
typedef pair< int , int > Pi;
int main(){
  int n;
  cin >> n;
  vector< int > vc(n);
  vector< Pi > cp(n);
  BIT bit1(n + 1), bit2(n + 1);
  for(int i = 0; i < n; ++i){
    scanf("%d", &vc[i]);
    cp[i] = make_pair( vc[i], i);
  }
  sort( cp.begin(), cp.end());

  int cnt = 1;
  for(int i = 0; i < cp.size(); ){
    do{
      vc[cp[i].second] = cnt;
      ++i;
    } while(i < cp.size() && cp[i - 1].first == cp[i].first);
    ++cnt;
  }

  BIT& b = bit1;
  vector< int > hoge[2];
  for(int j = 0; j < 2; ++j){
    hoge[j].resize(n);
    for(int i = 0; i < n; ++i){
      hoge[j][i] = i - bit1.sum(vc[i]);
      bit1.add( vc[i], 1);
    }
    reverse( vc.begin(), vc.end());
    b = bit2;
  }
  long long count = 0;
  for(int i = 0; i < n; ++i){
    count += min( hoge[0][i], hoge[1][n - 1 - i]);
  }
  printf("%lld\n", count);
}