http://ei1333.hateblo.jp

こっちへ移転しました

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

JOI春合宿2014 Day1-1 Bus

解法

よくわからない。
最初に乗る辺(バス停 1 から生えてるやつ) を決めて、それぞれの最短到着時刻をダイクストラで求める。
普通にやると遅くなるのは自明なので、あらかじめ辺を遅い順にソートしておくと、嬉しくなる(日本語難しいからソースコード(ry )。前の辺に乗った時よりも到着時刻が早くなっていれば、そのときの到着時刻と出発時刻をデキューに突っ込む。早くなってなければ、そのバスに乗っても意味がなさそうだから無かったことにする。
各クエリに答える時間はにぶたんでいい感じに求まる。
オーダーよくわかんない。

ソース

#include<bits/stdc++.h>  
using namespace std;
const int INF = 1 << 30;
 
struct Edge{
  int to, st, gr;
  bool operator<(const Edge& e)const{
    return st < e.st || (st == e.st && gr < e.gr);
  }
};
typedef vector< vector< Edge > > Graph;
typedef pair< int , int > Pi;
 
Graph info;
vector< int > min_time;
 
int Dijkstra(int idx){
  priority_queue< Pi, vector< Pi >, greater< Pi > > que;
  que.push( Pi( info[0][idx].gr, info[0][idx].to));
  min_time[0] = info[0][idx].st;
  while(!que.empty()){
    Pi p = que.top(); que.pop();
    if(p.second + 1 == info.size()) return p.first;
    if(p.first > min_time[p.second]) continue;
    for(int i = 0; i < info[p.second].size(); ++i){
      Edge& e = info[p.second][i];
      if(e.st < p.first) break; //バスの出発時刻のほうが早い
      if(min_time[e.to] <= e.gr) continue;
      min_time[e.to] = e.gr;
      que.push( Pi( e.gr, e.to));
    }
  }
  return -1;
}
 
 
int main(){
 
  //A: 出発バス停, B: 到着バス停, X: 出発時刻, Y: 到着時刻
 
  int N, M;
  int A, B, X, Y;
  int Q, L;
 
  scanf("%d %d", &N, &M);
  info.resize(N);
  min_time.resize(N, INF);
 
  for(int i = 0; i < M; ++i){
    scanf("%d %d %d %d", &A, &B, &X, &Y);
    --A, --B;
    info[A].push_back( (Edge){ B, X, Y});
  }
 
  for(int i = 0; i < N; ++i){
    sort(info[i].rbegin(), info[i].rend());
  }
 
  deque< Pi > good;
  
  int prev = INF;
  for(int i = 0; i < info[0].size(); ++i){
    int accept = Dijkstra(i); //Pi(到着時刻, 出発時刻)
    if(accept == -1) continue;
    else if(prev > accept){
      prev = accept;
      good.push_front( make_pair(prev, info[0][i].st));
    }
  }
  good.push_front( make_pair( -1, -1));
 
 
  scanf("%d", &Q);
  while(Q--){
    scanf("%d", &L);
    deque< Pi >::iterator it = lower_bound( good.begin(), good.end(), make_pair( L + 1, -INF));
    --it; //到着時刻直近で出発時刻が小さいもの
    printf("%d\n", it -> second);
  }
}

JOI2015予選参加記

精神状態があまりよろしいものではなかった
5完＋部分点20でした
追記:予選通過,本戦出場者各位よろしくね

• 団体受験なので、家を出て学校の部室へ向かう
• 無事学校に到着
• 僕のバッグが廊下の壁に掲示してあるポスターを2分して、1つは「落ち」る。
• 予選「落ち」というフラグを回収したかと絶望
• 実はこれは、二分探索あるいは半分全列挙だったことを疑う
• 知らない
• だいぶ緊張している
• 10分前くらいだったけど、よくわからない格ゲーを友達とやる
• 2連敗
• 1時間で3完してればいいか位の目処をたてる
• はじまった
• とりあえず1分くらいで6問分流し読み
• 4問目簡単そう、文字なマップ系が2問あって強そうくらいな感想を得る
• 1問目むずかしい
• 冒頭の通り緊張のせいで精神状態がよくなくて、うまくソースを書けない
• 思いついたことをそもままアウトプットしたソースがこちら

• #include<bits/stdc++.h>
  using namespace std;
   
  template<typename T1, typename T2> istream& operator>>(istream& is, pair<T1,T2>& a){ return is >> a.first >> a.second; }
  template<typename T1, typename T2> ostream& operator<<(ostream& os, pair<T1,T2>& a){ return os << a.first << " "<<a.second; }
  template<typename T> istream& operator>>(istream& is, vector< T >& vc){ for(int i = 0; i < vc.size(); i++) is >> vc[i]; return is; }
  template<typename T> ostream& operator<<(ostream& os, vector< T >& vc){ for(int i = 0; i < vc.size(); i++) os << vc[i] << endl; return os; }
   
  #define ForEach(it,c) for(__typeof (c).begin() it = (c).begin(); it != (c).end(); it++)
  #define ALL(v) (v).begin(), (v).end()
  #define UNQ(s) { sort(ALL(s)); (s).erase( unique( ALL(s)), (s).end());}
  #define fr first
  #define sc second
   
  typedef pair< int , int > Pi;
  typedef pair< int , Pi > Pii;
   
  typedef long long int64;
  const int INF = 1 << 30;
  
  int main(){
    int A, B, C, D, P;
    cin >> A;
    cin >> B;
    cin >> C;
    cin >> D;
    cin >> P;
  
    int ret = 0;
    if(P <= C) ret = B;
    else{
      ret = B;
      ret += D * (P - C);
    }
    cout << min( A * P, ret) << endl;
  }
  

• 世界一汚いソースコード
• まあこんな問題でバグるはずがないということで、提出(13:05)
• 2問目
• 問題分がわかりにくそう
• 読解力のない僕を駆逐しようとしている感
• JOIくんがゲームを支配しているプロだと感じながら、適当に書く
• サンプル通った
• テンプレートに感謝、入出力が楽
• これもバグるはずがないだろうということで、提出(13:15)

• #include<bits/stdc++.h>
  using namespace std;
   
  template<typename T1, typename T2> istream& operator>>(istream& is, pair<T1,T2>& a){ return is >> a.first >> a.second; }
  template<typename T1, typename T2> ostream& operator<<(ostream& os, pair<T1,T2>& a){ return os << a.first << " "<<a.second; }
  template<typename T> istream& operator>>(istream& is, vector< T >& vc){ for(int i = 0; i < vc.size(); i++) is >> vc[i]; return is; }
  template<typename T> ostream& operator<<(ostream& os, vector< T >& vc){ for(int i = 0; i < vc.size(); i++) os << vc[i] << endl; return os; }
   
  #define ForEach(it,c) for(__typeof (c).begin() it = (c).begin(); it != (c).end(); it++)
  #define ALL(v) (v).begin(), (v).end()
  #define UNQ(s) { sort(ALL(s)); (s).erase( unique( ALL(s)), (s).end());}
  #define fr first
  #define sc second
   
  typedef pair< int , int > Pi;
  typedef pair< int , Pi > Pii;
   
  typedef long long int64;
  const int INF = 1 << 30;
  
  int main(){
    int N, M;
    cin >> N;
    cin >> M;
    vector< int > A(M);
    cin >> A;
  
    vector< vector< int > > B( M, vector< int >(N));
    cin >> B;
  
    vector< int > Point( N, 0);
    for(int i = 0; i < M; i++){
      int hazure = 0;
      for(int j = 0; j < N; j++){
        if(A[i] == B[i][j]){
          Point[j]++;
        } else {
          hazure++;
        }
      }
      Point[A[i] - 1] += hazure;
    }
    cout << Point;
  }
  

• 3問目
• 書いてみるととても簡単
• 極めてやるだけ
• 考えないといけない系を想定していたけどこれは驚いた
• 書けた
• 謎の値が出力される
• 配列外参照に違いないと疑うも、配列外参照する要素がない
• ここからintがいけない、long longだ！とかいう謎のデバッグを始める
• 出力するとおかしくなってる気がするしこれはコンパイラが悪い
• 変数の中身を丁寧に扱おうとする(以下ソースのgetの部分だね)
• 何故かおかしくなくなった
• gccからのハラスメント
• 別におかしくなさそうなので提出(13:30)

• #include<bits/stdc++.h>
  using namespace std;
   
  template<typename T1, typename T2> istream& operator>>(istream& is, pair<T1,T2>& a){ return is >> a.first >> a.second; }
  template<typename T1, typename T2> ostream& operator<<(ostream& os, pair<T1,T2>& a){ return os << a.first << " "<<a.second; }
  template<typename T> istream& operator>>(istream& is, vector< T >& vc){ for(int i = 0; i < vc.size(); i++) is >> vc[i]; return is; }
  template<typename T> ostream& operator<<(ostream& os, vector< T >& vc){ for(int i = 0; i < vc.size(); i++) os << vc[i] << endl; return os; }
   
  #define ForEach(it,c) for(__typeof (c).begin() it = (c).begin(); it != (c).end(); it++)
  #define ALL(v) (v).begin(), (v).end()
  #define UNQ(s) { sort(ALL(s)); (s).erase( unique( ALL(s)), (s).end());}
  #define fr first
  #define sc second
   
  typedef pair< int , int > Pi;
  typedef pair< int , Pi > Pii;
   
  typedef long long int64;
  const int INF = 1 << 28;
  
  
  int main(){
    int H, W;
    string mas[100];
    int num[150][150];
  
    cin >> H >> W;
    for(int i = 0; i < H; i++){
      cin >> mas[i];
    }
    for(int i = 0; i < H; i++){
      for(int j = 0; j < W; j++){
        num[i][j] = INF;
      }
    }
  
    for(int i = 0; i < H; i++){
      for(int j = 0; j < W; j++){
        if(mas[i][j] == 'c') num[i][j] = 0;
      }
    }
    for(int i = 0; i < H; i++){
      for(int j = 1; j < W; j++){
        num[i][j] = min( num[i][j], num[i][j - 1] + 1);
      }
    }
    for(int i = 0; i < H; i++){
      for(int j = 0; j < W; j++){
        if(j != 0) cout << " ";
        int get = num[i][j];
        if(get == INF) cout << -1;
        else cout << get;
      }
      cout << endl;
    }
  }
  

• 流れが悪いながらも4問目
• 何も考えずにDP書けそう
• 実際にも書けた
• 多分この問題のみが一発で書けたソースだと思う
• 去年のbitDPとかなんだったんだろう
• とか盛大にJOIを批評しつつも提出(13:47)

• #include<bits/stdc++.h>
  using namespace std;
   
  template<typename T1, typename T2> istream& operator>>(istream& is, pair<T1,T2>& a){ return is >> a.first >> a.second; }
  template<typename T1, typename T2> ostream& operator<<(ostream& os, pair<T1,T2>& a){ return os << a.first << " "<<a.second; }
  template<typename T> istream& operator>>(istream& is, vector< T >& vc){ for(int i = 0; i < vc.size(); i++) is >> vc[i]; return is; }
  template<typename T> ostream& operator<<(ostream& os, vector< T >& vc){ for(int i = 0; i < vc.size(); i++) os << vc[i] << endl; return os; }
   
  #define ForEach(it,c) for(__typeof (c).begin() it = (c).begin(); it != (c).end(); it++)
  #define ALL(v) (v).begin(), (v).end()
  #define UNQ(s) { sort(ALL(s)); (s).erase( unique( ALL(s)), (s).end());}
  #define fr first
  #define sc second
   
  typedef pair< int , int > Pi;
  typedef pair< int , Pi > Pii;
   
  typedef long long int64;
  const int64 INF = 1LL << 58;
  
  int main(){
    int64 N, M;
    cin >> N >> M;
    vector< int64 > D(N);
    cin >> D;
    vector< int64 > C(M);
    cin >> C;
  
  
    // dp[i][j]: i日目に街jにいるときの疲労度の最小値
    vector< vector< int64 > > dp( M + 1, vector< int64 >( N + 1, INF));
    dp[0][0] = 0;
    for(int i = 0; i < M; i++){ //日数
      for(int j = 0; j < N; j++){ // 今いる街 0
        if(dp[i][j] == INF) continue;
        dp[i + 1][j] = min( dp[i + 1][j], dp[i][j]);
        dp[i + 1][j + 1] = min( dp[i + 1][j + 1], dp[i][j] + D[j] * C[i]);
      }
    }
    int64 ret = INF;
    for(int i = 0; i <= M; i++){
      ret = min( ret, dp[i][N]);
    }
    cout << ret << endl;
  }
  

• 精神状態がよくなる
• 顧問の先生と今年は多分、4完ボーダーより上だなあという話を入れる
• 顧問の先生が4.5完がボーダーという読みが入る
• とても焦る
• 精神状態がよくなくなった
• 5問目は実装ゲーっぽいので6問目を読む
• うーん
• 5問目を読む
• うーん
• どっちを解くべきか迷う
• 部分点が生死を極めると信じて、とりやすそうな6問目を書く
• 適当な末尾再帰
• 全探だね
• 適当すぎてバグったりしたけど、すぐ直った
• 入力ケース1だけ通った(14:22)
• 2を微妙に放置してみるもこれは天文的な時間がかかりそう
• (ソースコード紛失しました)
• 5問目を読む
• 5問目どうやって早くするんだろう
• 愚直な全探索を書く
• サンプル1だけ通った(14:30くらい)
• 2以降はやばそう
• トイレに行く
• 戻ってくる
• 終わってない(諦め
• (ここへんから理不尽なバグが続く)
• JOI紋章と似た感じのやり方かなあという考察をする
• 直近に'.'へと変化した数字の八方向以外は、盤面とは関係無いような気がする
• そこの八方向だけみるようにする
• 終わらない(謎)
• 見るべき座標たちの数が指数関数的に増加してる
• 見るべき座標はそこまで増加しないはずだろう！！とキレはじめる
• コンパイラによるハラスメントを疑う
• やめたい
• よくわからなくてつらい
• JOI予選落ち不可避
• 適当にデバッグも改善傾向が見られない
• やめよう
• 顧問の先生の名前が浮かぶ
• 関数の名前をそれにする
• セグメント例外(絶望
• 競プロ初心者にもなれなかった
• よくわからないけど、プログラムの流れ的に起こりえないはずの条件文をたくさん加える
• なぜか通った
• 条件無視とかつらみ
• 歓喜
• 入力ケース2
• 終わらないと思わせつつ、5秒位たって出力というプロな溜めが入る
• 全部の入力ケースが通った
• 時間がやばそうだけど、時間制限ない
• 提出(15:11)

• #include<bits/stdc++.h>
  using namespace std;
   
  template<typename T1, typename T2> istream& operator>>(istream& is, pair<T1,T2>& a){ return is >> a.first >> a.second; }
  template<typename T1, typename T2> ostream& operator<<(ostream& os, pair<T1,T2>& a){ return os << a.first << " "<<a.second; }
  template<typename T> istream& operator>>(istream& is, vector< T >& vc){ for(int i = 0; i < vc.size(); i++) is >> vc[i]; return is; }
  template<typename T> ostream& operator<<(ostream& os, vector< T >& vc){ for(int i = 0; i < vc.size(); i++) os << vc[i] << endl; return os; }
   
  #define ForEach(it,c) for(__typeof (c).begin() it = (c).begin(); it != (c).end(); it++)
  #define ALL(v) (v).begin(), (v).end()
  #define UNQ(s) { sort(ALL(s)); (s).erase( unique( ALL(s)), (s).end());}
  #define fr first
  #define sc second
   
  typedef pair< int , int > Pi;
  typedef pair< int , Pi > Pii;
   
  typedef long long int64;
  const int INF = 1 << 30;
  
  vector< string > str;
  int H, W;
  int dy[] = { -1, -1, -1, 0, 1, 1, 1, 0}, dx[] = { -1, 0, 1, 1, 1, 0, -1, -1};
  queue< Pi > points;
  bool ended[1000][1000];
  
  bool hori_sensei_love_function(){
    bool flag = false;
  
  
    queue< Pi > buff_points;
    queue< Pi > que;
  
    while(!points.empty()){
      Pi p = points.front(); points.pop();
  
      int i = p.first, j = p.second;
      int get = 0;
      if(!ended[i][j] && isdigit(str[i][j])){
        for(int k = 0; k < 8; k++){
          int ny = i + dy[k], nx = j + dx[k];
          get += str[ny][nx] == '.';
        }
        if(str[i][j] - '0' <= get){
          flag = true;
          ended[i][j] = true;
          que.push(Pi( i, j));
        }
      }
  
    }
  
    while(!que.empty()){
      Pi p = que.front(); que.pop();
      int i = p.first, j = p.second;
  
      str[i][j] = '.';
      
      for(int k = 0; k < 8; k++){
        int ny = i + dy[k], nx = j + dx[k];
        if(isdigit( str[ny][nx] ) && str[ny][nx] != '9' && !ended[ny][nx]){
          buff_points.push( Pi( ny, nx));
        }
      }
    }
  
  
    while(!buff_points.empty()){
      points.push( buff_points.front());
      buff_points.pop();
    }
  
    return flag;
  
  }
  
  bool foo(){
    bool flag = false;
  
    for(int i = 0; i < H; i++){
      for(int j = 0; j < W; j++){
        if(isdigit(str[i][j])){
          if(str[i][j] == '9') continue;
  
          int get = 0;
          for(int k = 0; k < 8; k++){
            int ny = i + dy[k], nx = j + dx[k];
            get += str[ny][nx] == '.';
          }
  
          if(str[i][j] - '0' <= get){
            flag = true;
            ended[i][j] = true;
          }
        }
      }
    }
  
    for(int i = 0; i < H; i++){
      for(int j = 0; j < W; j++){
        if(ended[i][j]){
          str[i][j] = '.';
          for(int k = 0; k < 8; k++){
            int ny = i + dy[k], nx = j + dx[k];
            if(isdigit( str[ny][nx] ) && str[ny][nx] != '9' && !ended[ny][nx]){
              points.push( Pi( ny, nx));
            }
          }
        }
      }
    }
  
    return flag;
  }
  
  int main(){
    cin >> H >> W;
  
    str.resize(H);
  
    for(int i = 0; i < H; i++){
      cin >> str[i];
    }
  
    int ret = 0;
    bool changed = foo();
    if(changed) ret++;
  
    while(changed){
      changed = hori_sensei_love_function();
      if(changed) ret++;
    }
    cout << ret << endl;
  }
  

• 6問目を考え始める
• 朝のポスターの2分を思い出す
• 制約的に半分全列挙を疑う
• 書いてみる
• 書けた
• かけてなかった
• 死んだほうがいい
• 書けたみたい
• そこからどうするんだろう
• セグ木を疑う
• 必要なところだけ作る例のアレかな
• 時間がなさそう
• 時間が残されていない
• やめた
• 提出ミスでの死だけは勘弁ということで全てを確認
• 良さそうと思ったところで終了

実行結果(短そうなやつだけ)
問題1

179204
5415
293725
6000
474688

問題4

1242866
2377989
51767722
9684358
144764153

問題5

1735
993949
994510
343350
442542

問題6(1だけよ)

2816001618489474

PCK2014もうひとつの本選

本選行きたかったなあ
4完0WAで4位でした

• ジョギングの疲れがとれない
• (体力が足りないといわれて毎日10km走ってるけどこれは逆効果だ)
• 疲れがとれなくて眠み生えてる
• 13:45
• 問題が先行公開されてたので開く
• 1問目だけ先に解いてしまおう
• 問題文を読む
• 面倒くさそう
• 読解力がない(1回目)
• やめたい
• 線上に点がなかったらなんかやればよさそう
• 10分くらいだっけな、もうひとつでFAとれたみたい(1問目AC)

• int main(){
    int N;
  
    cin >> N;
    for(int i = 0; i < N; i++){
      int r, t;
  
      cin >> r >> t;
  
      int shift = (t / 30) * 5; //スタートの番号
      int pos = r / 100; //場所
      bool flag = (t % 30 == 0); //線状か
      
      vector< int > ret;
      ret.push_back(shift + pos);
      if(r % 100 != 0) ret.push_back(shift + pos + 1);
      if(!flag) ret.push_back(shift + pos + 5);
      if(!flag && r % 100 != 0) ret.push_back(shift + pos + 6);
      
      for(int j = 0; j < ret.size(); j++){
        cout << (j == 0 ? "" : " ") << ret[j];
      }
      cout << endl;
    }
  }
  

• 予選の反省があるから問題にざっと目を通す
• 6問目と8問目は解けそう感
• まあいいや2問目
• やろうとする
• 誤読に気づく
• やろうとする
• 方針が違うことに気づく
• やろうとする
• まだ方針違うみたい
• 読解力がない(2回目)
• 文字列の長さの合計がどれくらいになるか求めようとする
• わかんない
• まあいいか
• なぜか我が校のサーバーが逝き始める
• これ顧問が会津いってるからだ
• 顧問がいないのをいいことに誰かが外部から攻撃してる説
• これはPCKのライバルからの陰謀だと確信
• さらに端末の動作が鈍くなってついには動かなくなった
• これは発狂不可避
• サーバーの再起動やらなにやらを繰り返す
• マジで誰だよ
• まともに問題読めないしコーディングができない
• ローカルのパソコンでやろう
• 端末が動かない間に色々整理できたし結果的にはよかったのかもしれない
• 2問目適当にバックトラックしてサンプル通って提出
• やったねAC(2問目AC)

• int w;
  
  void rec(int sum, int idx, string emacs){
    if(abs(sum) > w || pow( 3.0, idx - 2) > w){
      return;
    }
    if(sum == w){ //できたー
      cout << emacs << endl;
      exit(0);
    } else { //できてないー
      rec( sum + (int)pow( 3.0, idx), idx + 1, "+" + emacs);
      rec( sum - (int)pow( 3.0, idx), idx + 1, "-" + emacs);
      rec( sum, idx + 1, "0" + emacs);
    }
  }
  
  int main()
  {
    cin >> w;
    rec( 0, 0, "");
  }
  

• あのプログラムオーダーどれくらいだろ
• 無駄な再帰を明確にしてるから、O(logn)より結構大きいくらい
• 変数名でvim勢を煽っていくスタイル(小声
• 提出状況を確認したら3問目複数提出あるけど0ACな模様
• 予選の5問目枠を確信
• 触れないことにしよう
• 次何解こう
• 6問目は僕の頭でも理解できる問題文っぽい
• O(n^4)の二次元累積和がぱっと見、浮かぶけどTLEだろうな
• 多少バグらせながらも解く
• WA(絶望)
• やっぱバグらせていた
• すぐ察して提出
• TLE(妥当)

• int main()
  {
    int N, mas[302][302] = {{}};
    cin >> N;
    for(int i = 1 ; i <= N ; i++ ){
      for(int j = 1 ; j <= N ; j++ ){
        cin >> mas[i][j];
        mas[i][j] += mas[i-1][j] + mas[i][j-1] - mas[i-1][j-1];
      }
    }
    int ret = -INF;
    for(int i = 1 ; i <= N ; i++ ){
      for(int j = 1 ; j <= N ; j++ ){
        for(int k = 1 ; k <= i ; k++ ){
          for(int l = 1 ; l <= j ; l++ ){
            int all = mas[i][j] - mas[k-1][j] - mas[i][l-1] + mas[k-1][l-1];
            int blank = 0;
            if(abs(i - k) >= 2 && abs(j - l) >= 2){
              blank += mas[i - 1][j - 1] - mas[k][j - 1] - mas[i - 1][l] + mas[k][l];
            }
            ret = max( ret, all - blank);
  
          }
        }
      }
    }
    cout << ret << endl;
  }
  

• こんなもので通る訳がない(自明
• きっとDPとかしてO(n^4)をO(n^3)にするんだろう(考察
• あーーー
• んーーー
• ・・・・・・
• あたまついてない
• INF個くらい必要そう
• これは敗北
• この辺から焦りはじめる
• 4問目のAC率が高そう、8問目がreal本選erに結構解かれている
• 8問目読む
• なんか2008年くらいのPCKにこんな問題あったけどにぶたんで解いたっけ
• 重さの要素が加わっただけだ
• とりあえず本を入れる位置を全探で決めてどれくらい入るかは貪欲で求める
• なぜかバグらせなかった
• にぶたんはこのときかかなかった
• 提出
• TLE
• 貪欲で求める部分をにぶたんに書き換える
• 多少バグらせたけどできた
• ACを確信
• TLE(困惑)
• やめた
• 4問目を読む
• 問題文ながぽよ
• 読解力がない(3回目)
• あーー
• なんでデッドロックでグラフを作れるんだろう
• そんなことはどうでもいいらしい
• 閉路検出してデッドロックが発生するか判定せよ的な感じの問題文になった
• 解法書いてあるじゃん
• 本当にそのままなのかな
• 適当にグラフ作って閉路検出しようとする
• 閉路検出のスキルが自分にはないことに気づく
• どうやるんだろう
• グラフ世界一扱えない
• こころが沈んできた
• 強連結成分分解でできる説
• 実装やだ
• DFSで試すだけでしょ
• すべての場合についてデッドロックが発生する
• 私の頭がデッドロックしそうとかよくわかんないことを考え始める
• 辺にも使用済かの情報が必要なのか
• あーこれ巡ったら頂点を使って内容に戻すべきだな
• なんかできてる
• つ計算量
• 大丈夫だろ、提出
• うっしゃ(4問目AC)

• typedef vector< vector< Pi > > Graph;
  Graph g;
  int V;
  bool used[300];
  
  int dfs(int idx){
    if(used[idx]) return true;
    used[idx] = true;
    for(int i = 0; i < g[idx].size(); i++){
      if(g[idx][i].second == 0){
       g[idx][i].second = true;
       if(dfs(g[idx][i].first)) return true;
      }
    }
    used[idx] = false;
    return false;
  }
  
  int main()
  {
  
    cin >> V;
    g.resize(200);
    for(int i = 0; i < V; i++){
      int u, d;
      string s;
      cin >> u >> s >> d;
      u--, d--;
      if(s == "lock"){
        g[d + 100].push_back(Pi(u, false));
      } else {
        g[u].push_back(Pi( d + 100, false));
      }
    }
    for(int i = 0; i < 100; i++){
      if(!used[i] && dfs(i)){
        cout << 1 << endl;
        return(0);
      }
    }
  
    cout << 0 << endl;
    return(0);
  }
  

• こころぴょんぴょんしてきた
• 3問目を読んでみる
• 読解力がない(N回目)
• なんかややこしい
• 問題文を誤読していることに複数回気づく
• 読解力がない(INF回目)
• シミュレーションやるだけ説
• まあ書く
• かけたと思ったらサンプル合わない
• 誤差る
• 問題文の誤読に気づく
• 読解力がない(∞回目)
• なおす
• でない
• 問題文の誤読に気づく
• 多分この問題誤読の回数の最大値を得れた気がする
• 誤読なくした
• ソース直した
• でた
• 提出
• うぇい(3問目AC)

• typedef vector< vector< Pi > > Graph;
  
  int main(){
    int N, R, T, p[100];
    cin >> N >> R >> T;
    for(int i = 0; i < N; i++){
      cin >> p[i];
    }
  
    int stap[1001] = {};
    int pos[100] = {};
    int ret = 0;
    bool first = false;
    for(int i = 1; i <= T; i++){
      for(int j = 0; j < N; j++){
        pos[j] = (pos[j] + p[j]) % R;
      }
  
      for(int k = 0; k < N; k++){
        if(stap[pos[k]] > 0){
          stap[pos[k]]--;
        } else {
          ret++;
        }
      }
      if(first++){
        for(int k = 0; k < N; k++){
          stap[pos[k]]++;
        }
      }
      
    }
    cout << ret << endl;
  }
  

• こんな簡単なシミュレーションで通るのにあの正答率は何(煽り
• 再び1位に浮上したらしい
• あと1時間30分くらいある
• 5問目を軽く読む
• 圧倒的木DP感
• 木DP書いたことない
• 書けそうもない
• 8問目再び
• 計算量O(2 ^ n log m)くらいだよな
• (後記: 実は大嘘 O(m・2^n log m)っぽい(やばい)) 
• メモ化した
• ACを確信
• TLE(困惑
• 気になるところを変えてn回出してみるもTLE×n回
• 高速化の余地なし
• これもうわかんねえな
• TLE(引退)
• たくさんTLE生える
• 方針は合ってそうだけどなんでだろ
• つらみがたくさん生える
• 8回目TLE
• やめた
• つかれた
• 4位だ
• 5問目解こうとするけど正直解いても順位変わんない
• 時間がない
• 本選行きたかったなあ
• 終了

あとから解いたよ(簡単だった)
5問目 木DPっぽい

int N;
vector< string > node;
vector< vector< int > > edges;
int dp[1000];

int rec(int idx){
  if(dp[idx]) return dp[idx];
  if(edges[idx].empty()) return(1 + (node[idx] == "E?"));

  int64 ret = 0;

  // 選択ノード //
  if(node[idx][0] == 'R'){ /* OR */
    for(int i = 1; i < (1 << edges[idx].size()); i++){
      int64 ret1 = 1;
      for(int j = 0; j < edges[idx].size(); j++){
        if((i >> j) & 1){
          (ret1 *= rec(edges[idx][j])) %= 1000000007;
        }
      }
      ret += ret1;
    }
    if(node[idx] == "R?") ret++;
  } else if(node[idx][0] == 'A'){ /* ALT */
    for(int i = 0; i < edges[idx].size(); i++){
      (ret += rec(edges[idx][i])) %= 1000000007;
    }
    if(node[idx] == "A?") ret++;
  } else { // 物質ノード //
    ret = 1;
    for(int i = 0; i < edges[idx].size(); i++){
      (ret *= rec(edges[idx][i])) %= 1000000007;
    }
    if(node[idx] == "E?") ret++;
  }
  return(dp[idx] = ret % 1000000007);
}

int main(){
  cin >> N;
  node.resize(N);
  edges.resize(N);

  for(int i = 0; i < N; i++){
    cin >> node[i];
  }
  for(int i = 0; i < N - 1; i++){
    int a, b;
    cin >> a >> b;
    a--, b--;
    edges[a].push_back(b);
  }
  cout << rec(0) << endl;
}

8問目 メモ化じゃ解けないやこれ。DPしてにぶたんするだけ
途中でint64生えてるのとかにぶたんがちょっとおかしかったりするのは頭悪いデバッグのおかげ

typedef long long int64;
int64 M, N;
int64 w[200004], t[200004];
int64 c[15], b[15];
int64 dp[1 << 15];


int64 get_sum_w(int64 a, int64 b){ // [a,b]
  if(a == 0) return w[b];
  return(w[b] - w[a - 1]);
}
int64 get_sum_t(int64 a, int64 b){
  if(a == 0) return t[b];
  return(t[b] - t[a - 1]);
}

int64 get_donyoku(int64 idx, int64 dan){
  int64 max_weight = c[dan], max_width = b[dan];

  int64 pos = INF;

  int64 row = idx, high = M;
  while(row + 1 < high){
    int64 mid = (row + high) / 2;
    if(get_sum_w( idx, mid) <= max_weight) {
      row = mid + 1;
    } else {
      high = mid;
    }
  }

  if(get_sum_w( idx, row) > max_weight)  pos = min( pos, row);
  else if(get_sum_w( idx, row + 1) > max_weight) pos = min( pos, row + 1);
  else if(get_sum_w( idx, row + 2) > max_weight) pos = min( pos, row + 1);

  row = idx, high = M;
  while(row + 1 < high){
    int64 mid = (row + high) / 2;
    if(get_sum_t( idx, mid) > max_width) {
      high = mid;
    } else {
      row = mid + 1;
    }
  }

  if(get_sum_t( idx, row) > max_width)  pos = min( pos, row);
  else if(get_sum_t( idx, row + 1) > max_width) pos = min( pos, row + 1);
  else if(get_sum_t( idx, row + 2) > max_width) pos = min( pos, row + 1);

  if(pos == INF) return idx;
  return pos;
}

int main(){
  scanf("%d %d", &M, &N);
  w[M] = INF, t[M] = INF;
  w[M + 1] = INF, t[M + 1] = INF;
  for(int i = 0; i < M; i++){
    scanf("%d %d", &w[i], &t[i]);
    if(i != 0){
      w[i] += w[i - 1];
      t[i] += t[i - 1];
    }
  }
  for(int i = 0; i < N; i++){
    scanf("%d %d", &c[i], &b[i]);
  }
  fill_n( dp, 1 << 15, -1);
  dp[0] = 0;
  for(int i = 0; i < (1 << 15); i++){
    if(dp[i] == -1) continue;
    for(int j = 0; j < N; j++){
      if(!((i >> j) & 1)){
        dp[i|(1 << j)] = max( dp[i|(1 << j)], get_donyoku(dp[i], j));
      }
    }
  }
  cout << *max_element( dp, dp + (1 << 15)) << endl;
}

次はJOIだ
JOI頑張りましょ

CODEFESTIVAL2014 予選B

ブログの存在を忘れていた
スーパーコン本戦とかPCK予選(落ち)とか色々あったけど過去のことは忘れたな
コードフェスティバルの予選が合ったらしい(参加権ない)
予選Aは20位で1ページ目に乗ってて実力に見合わない

予選B

• 直前にキーボードの3(#)キーが壊れる
• 治らない
• なんにも準備してない
• スタート
• シャープ打てないとtweetしようとしたところで「しゃーぷ」を変換すれば出来る事が判明
• A問題FA狙うも9秒ACという人外が現れて引退
• MAXとるだけっぽい(A00:20AC)
• B問題
• 足すだけっぽい
• 書く
• ACやったね(B02:43AC)
• 順位表を確認
• D問題ACしてる人がいるからそっちを先に解こう
• Dが一番簡単という風潮??
• DP?
• 書く
• 問題誤読、なぜか増加部分列的な感じだと思ってた
• 書く
• 書けない
• 更に問題誤読
• 一瞬セグ木が頭の片隅に浮かぶけどオーダー大丈夫か？
• やめよう
• C問題読む
• 変な解法しそうだなあ
• どうせC問題
• 文字の数数えて使わないといけない数を求める
• 良い感じにやる
• 反例なんて考えられない頭だからこのまま提出
• 意外にもACしてる(C36:26AC)
• 順位逝ってしまうから保険欲しい
• 普通に数えるやつを書く(D38:59TLE部分点30)
• セグ木のやつO(nlog^2n)か
• O(10^8)くらい??
• んーー(関数電卓紛失)
• 書く
• にぶたんばぐる
• にぶたん世界一書けない
• にぶたんした後の微妙な足し算めんどい
• 番兵置こう(いらなかった)
• 提出(D63:21AC)
• 1.5sかかってる
• cinにしたらどうなるのだろう
• TLE
• 終わり(44位)

Code

A

#include<bits/stdc++.h>
using namespace std;
int main(){
  int a, b;
  cin >> a >> b;
  cout << max( a, b) << endl;
}

B

#include<bits/stdc++.h>
using namespace std;
typedef long long int64;
int main(){
  int n, k, a[100000];
  cin >> n >> k;
  int64 sum = 0;
  for(int i = 0; i < n; i++){
    cin >> a[i];
    sum += a[i];
    if(k <= sum){
      cout << i + 1 << endl;
      return(0);
    }
  }
}

C

#include<bits/stdc++.h>
using namespace std;
typedef pair< int , int > Pi;
int main(){
  string s1, s2, s3;
  cin >> s1 >> s2 >> s3;
  int cnt1[26] = {}, cnt2[26] = {}, cnt3[26] = {};
  for(int i = 0; i < 26; i++) cnt1[i] += count(s1.begin(), s1.end(), (char)('A' + i));
  for(int i = 0; i < 26; i++) cnt2[i] += count(s2.begin(), s2.end(), (char)('A' + i));
  for(int i = 0; i < 26; i++) cnt3[i] += count(s3.begin(), s3.end(), (char)('A' + i));
 
  
  int need1 = 0, need2 = 0;
  bool flag = true;
  for(int i = 0; i < 26; i++){
    if(cnt2[i] < cnt3[i]){
      need1 += cnt3[i] - cnt2[i];
      if(cnt2[i] + cnt1[i] < cnt3[i]) flag = false;
    }
  }
  for(int i = 0; i < 26; i++){
    if(cnt1[i] < cnt3[i]){
      need2 += cnt3[i] - cnt1[i];
    }
  }
  if(need1 > s1.size() / 2 || need2 > s2.size() / 2 || !flag)  cout << "NO" << endl;
  else cout << "YES" << endl;
}

D

#include<bits/stdc++.h>
using namespace std;
typedef long long int64;
typedef pair< int , int > Pi;
int h[100002];
#define MAX 400000
int n, seg[MAX * 2 - 1];
const int INF = 1 << 30;
void update( int i, int x){
  i += n - 1;
  seg[i] = x;
  while(i > 0){
    i = ( i - 1 ) / 2;
    seg[i] = max( seg[i * 2 + 1], seg[i * 2 + 2]);
  }
}
int query( int a, int b, int k = 0, int l = 0, int r = n){
  if( r <= a || b <= l ) return -1;
  if( a <= l && r <= b ) return seg[k];
  int vl = query( a, b, k * 2 + 1, l, (l + r) / 2);
  int vr = query( a, b, k * 2 + 2, (l + r) / 2, r);
  return max( vl, vr);
}
void init( int& size){
  n = 1;
  while( n < size ) n *= 2;
}
 
int main(){
  int size;
  scanf("%d", &size);
  init(size);
  h[0] = -INF;
  for(int i = 1; i <= size; i++){
    scanf("%d", &h[i]);
    update( i, h[i]);
  }
  h[size + 1] = INF;
  for(int i = 1; i <= size; i++){
    int cost = 0;
    int row = 0, high = i - 1;
    while(high - row > 0){
      int mid = (high + row + 1) >> 1;
      if(query(mid, high + 1) > h[i]){
        row = mid;
      } else {
        high = mid - 1;
      }
    }
    cost += i - high - 1;
    
    row = i + 1, high = size + 1;
    
    while(high - row > 0){
      int mid = (high + row) / 2;
      if(query( row, mid + 1) > h[i]){
        high = mid;
      } else {
        row = mid + 1;
      }
    }
    
    cost += row - i - 1;
    
    printf("%d\n", cost);
  }
}

AOJ1508 RMQ

解法

---

Treap木を本とかを大分参考にしながら実装してみた。
割と実装楽しい。

ソース

---

#include<bits/stdc++.h>
using namespace std;
const int INF = 1 << 30;
struct Treap {
  struct node{
    int value; // 値
    node *left, *right; // *左, *右:
    int priority; // 優先度
    int cnt; // 部分木のサイズ
    //  int sum; // 部分木の和
    int small; //部分木の最小値
    node( int v) : value(v), priority(rand()), cnt(1), /*sum(v),*/ small(v){
      left = right = NULL;
    }
  };
  
  node *root;
  Treap():root(NULL){}
  
  int count( node *t){ return !t ? 0 : t->cnt; }
  //int sum( node *t)  { return !t ? 0 : t->sum; }
  int mini( node *t) { return !t ? INF : t->small; }
  
  node* update( node* t) {
    t -> cnt = count( t -> left) + count( t -> right) + 1;
    // t -> sum = sum( t -> left) + sum( t -> right) + t -> value;
    t -> small = min( min( mini( t -> left), mini( t -> right)), t -> value);
    return t;
  }
  node* merge( node* l, node* r){
    if(!l || !r) return l? l : r;
    if(l -> priority > r -> priority) {
      l -> right = merge( l -> right, r);
      return update(l);
    } else {
      r -> left = merge( l, r -> left);
      return update(r);
    }
  }
  pair< node*, node* > split( node* t, int k){ // [0,k),[k,n)
    if(!t) return make_pair((node*)NULL,(node*)NULL);
    if(k <= count( t -> left)){
      pair< node*, node* > s = split( t -> left, k);
      t -> left = s.second;
      return make_pair( s.first, update(t));
    }else{
      pair< node*, node* > s = split( t -> right, k - count( t -> left) - 1);
      t -> right = s.first;
      return make_pair( update(t), s.second);
    }
  }
  
  node* insert( node* t, int k, int val){
    pair< node*, node* > s = split( t, k);
    t = merge( s.first, new node( val));
    return update(merge( t, s.second));
  }
  
  node* erase( node* t, int k){
    pair< node*, node* > s1, s2;
    s1 = split( t, k + 1);
    s2 = split( s1.first, k);
    t = merge( s2.first, s1.second);
    return update(t);
  }
  
  node* find( node* t, int k){
    int c = count(t -> left);
    if(k < c)       return find( t -> left, k);
    else if(k > c)  return find( t -> right, k - c - 1);
    else return t;
  }
  void insert( int k, int v){ root = insert( root, k, v);}
  void erase( int k) { root = erase( root, k);}
  node* find( int k) { return find( root, k); }
};
  
int main(){
  int n, q;
  Treap tree;
  
  scanf("%d %d", &n, &q);
  for(int i = 0, a ; i < n ; i++ ){
    scanf("%d", &a);
    tree.insert( i, a);
  }
  while(q--){
    int x, y, z;
    scanf("%d %d %d", &x, &y, &z);
    if(x == 0){
      z++;
      pair< Treap::node*, Treap::node* > a, b, c;
      c = tree.split( tree.root, z);     // [0,z] [z + 1,n)
      b = tree.split( c.first , z - 1);  // [0,z) [z]
      a = tree.split( b.first , y);     //  [0,y) [y,z)
  
      tree.root = tree.merge( a.first, b.second); // [0,y) + [z]
      tree.root = tree.merge( tree.root, a.second); // root + [y,z)
      tree.root = tree.merge( tree.root, c.second); // root + [z+1,n)
  
      //ふええふえぇふぇぇ(むずかしいね
    } else if(x == 1){
      z++;
 
      pair< Treap::node*, Treap::node* > p, q;
      p = tree.split( tree.root, y);
      q = tree.split( p.second, z - y);
      printf("%d\n", tree.mini(q.first));
      tree.root = tree.merge( p.first, tree.merge( q.first, q.second));
    } else {
      tree.erase(y);
      tree.insert( y, z);
    }
  }
}

AOJ2402 天の川

解法

---

星の変な入力を頑張って5辺にしてDijkstra。

ソース

---

typedef pair< double , int > Pi;
bool used[100];
double info[100][100];
int n, m, l;
L stars[100][5];
 
void add( int x, int y, int a, int r, const int z){
  G hosi(5);
  for(int i = 0 ; i < 5 ; i++ ){
    double theta = Degree_to_Radian(a + 72 * i);
    double nx = r * sin( theta ), ny = r * cos( theta );
    hosi[i] = P( x - nx, y + ny);
  }
  for(int i = 0 ; i < 5 ; i++ ){
    stars[z][i] = L( hosi[i * 2 % 5], hosi[(i + 1) * 2 % 5]);
  }
}
double dist( LLL a, LLL b){
  double ret = INF;
  for(int i = 0 ; i < a.size() ; i++ ){
    for(int j = 0 ; j < b.size() ; j++ ){
      ret = min( ret, distancion( a[i], b[i]));
    }
  }
  return ret;
}
double Dijkstra(){
  priority_queue< Pi , vector< Pi > , greater< Pi > > que;
  fill_n( used, 100, false);
  que.push( Pi( 0.0, m));
  while(!que.empty()){
    Pi p = que.top(); que.pop();
    if(p.sc == l) return p.fr;
    if(used[p.sc]++) continue;
    for(int i = 0 ; i < n ; i++ )
      que.push( Pi( info[p.sc][i] + p.fr, i));
  }
}
  
int main(){
  while(cin >> n >> m >> l, l){
    m--, l--;
    for(int i = 0 ; i < n ; i++ ){
      int x, y, a, r;
      cin >> x >> y >> a >> r;
      add( x, y, a, r, i);
    }
  
    for(int i = 0 ; i < n ; i++ ){
      for(int j = i + 1 ; j < n ; j++ ){
        double dist = INF;
        for(int a = 0 ; a < 5 ; a++ ){
          for(int b = 0 ; b < 5 ; b++ ){
            dist = min( dist, distancion( stars[i][a], stars[j][b]));
          }
        }
        info[i][j] = info[j][i] = dist;
      }
    }
    cout << fixed << setprecision(10) << Dijkstra() << endl;
  }
}

AOJ2545 ライオン

解法

---

全探する。考えられる組み合わせをすべて挙げればいい感じにできる。
できるだけライオンを檻の中に多く入れたいので、あんな感じ(以下ソース参照)に檻に入れられる最大値からループを回す。

ソース

---

#include<iostream>
using namespace std;
 
int n, x, m, l[10], r[10], s[10];
int ret[6];
 
bool rec( int now, int sum){
  if(now == n){
 
    int sum[6] = {};
    for(int i = 0 ; i < n ; i++){
      sum[i + 1] = sum[i] + ret[i];
    }
    for(int i = 0 ; i < m ; i++ ){
      if(sum[r[i]] - sum[l[i] - 1] != s[i]) return false;
    }
    for(int i = 0 ; i < n ; i++ ){
      cout << (i  ? " " : "") << ret[i];
    }
    cout << endl;
    return true;
 
  }
  for(int i = x ; i >= 0 ; i--){
    ret[now] = i;
    if(rec( now + 1, sum - i)) return true;
  }
  return false;
}
 
int main(){
  cin >> n >> x >> m;
  for(int i = 0; i < m; i++){
    cin >> l[i] >> r[i] >> s[i];
  }
  if(!rec(0,m)) cout << "-1\n";
}

AOJ1175 そして，いくつになった？

解法

---

ふぇぇって考えてるとbitDPに帰着すると思う。
前処理で円と円の交差判定が必要で,
円Oと円O'間の距離が Oの半径 + O'の半径未満だったら交差してないと判定する。
距離はsqrtとらずに整数でやると誤差らずに出来て良かった。

ソース

---

#include<iostream>
#include<algorithm>
#include<map>
#include<cmath>
#include<algorithm>
using namespace std;
typedef pair < int , int > Pt;
bool dp[1 << 24];
Pt pts[24];
int n, r[24], c[24];
int hoge[24];
const int INF = 1 << 28;
bool intersect( Pt a, Pt b, int r1, int r2){
  return pow( a.first - b.first, 2) + pow( a.second - b.second, 2) < pow( r1 + r2, 2);
}
 
int rec( int bit){
  if(dp[bit]++) return -INF;
  int ret = 0;
 
  for(int i = 0 ; i < n ; i++ ){
    if((bit >> i) & 1){
      for(int j = i + 1 ; j < n ; j++ ){
        if( (bit >> j) & 1 && c[i] == c[j] && !(bit & hoge[i]) && !(bit & hoge[j])){
          ret = max( ret, rec( bit & ~(1 << i) & ~(1 << j)) + 2);
        }
      }
    }
  }
  return ret;
}
int main()
{
  while(cin >> n, n){
    fill_n( dp, 1 << 24 , false);
    fill_n( hoge, 24 , 0);
 
    for(int i = 0 ; i < n ; i++ ){
      cin >> pts[i].first >> pts[i].second >> r[i] >> c[i];
      for(int j = 0 ; j < i ; j++ ){
        if(intersect(pts[i],pts[j],r[i],r[j])) hoge[i] |= 1 << j;
      }
    }
    cout << rec((1 << n) - 1) << endl;
  }
}

AOJ0187 Stoning Fortune

解法

---

どれか二線の交点がなかったら凶。
あったら、3つの交点を求めてヘロンの公式S=√s(s-a)(s-b)(s-c)で面積を求めてはっぴー

ソース

---

int main(){
  L ls[3];
  int x1[3], y1[3], x2[3], y2[3];
  while( cin >> x1[0] >> y1[0] >> x2[0] >> y2[0], x1[0]|y1[0]|x2[0]|y2[0] ){
    for(int i = 1 ; i < 3 ; i++ ){
      cin >> x1[i] >> y1[i] >> x2[i] >> y2[i];
    }
    for(int i = 0 ; i < 3 ; i++ ){
      ls[i] = L( P( x1[i], y1[i]), P( x2[i], y2[i]));
    }
 
    G triangle(3);
    bool flag = true;
    for(int i = 0 ; i < 3 ; i++ ){
      const int NEXT = ( i + 1 ) % 3;
      if(!intersect( ls[i], ls[NEXT])){
        flag = false;
        break;
      }else{
        triangle[i] = crosspoint( ls[i], ls[NEXT]);
      }
    }
 
    double s = (abs(triangle[0]-triangle[1])+abs(triangle[1]-triangle[2])+abs(triangle[2]-triangle[0])) / 2;
    double area = sqrt(s * ( s - abs(triangle[0] - triangle[1])) * ( s - abs(triangle[1] - triangle[2])) * ( s - abs(triangle[2] - triangle[0])));
    if(!flag || area < EPS) cout << "kyo" << endl;
    else if(area < 100000) cout << "syo-kichi" << endl;
    else if(area < 1000000) cout << "kichi" << endl;
    else if(area < 1900000) cout << "chu-kichi" << endl;
    else cout << "dai-kichi" << endl;
  }
}

AOJ0091 Blur

解法

---

BFS。左上から見ていって、滴数 < 0か垂らしても残った時に枝刈りした。
これでVolume0全完。

ソース

---

#include<bits/stdc++.h>
using namespace std;

int q, mas[10][10];
int draw[][5][5] = {
  /*Small*/
  {{ 0, 0, 1, 0, 0},
   { 0, 1, 1, 1, 0},
   { 0, 0, 1, 0, 0}},
  //*midium*/
  {{ 0, 0, 1, 1, 1},
   { 0, 0, 1, 1, 1},
   { 0, 0, 1, 1, 1}},
  /*large*/
  {{ 0, 0, 1, 0, 0},
   { 0, 1, 1, 1, 0},
   { 1, 1, 1, 1, 1},
   { 0, 1, 1, 1, 0},
   { 0, 0, 1, 0, 0}},
};

bool check( int y, int x, int w){
  for(int i = 0 ; i < 5 ; i++ ){
    for(int j = 0 ; j < 5 ; j++ ){
      if(mas[y + i][x + j - 2] - draw[w][i][j] < 0) return false;
    }
  }
  return true;
}

void paint( int y, int x, int w){
  for(int i = 0 ; i < 5 ; i++ ){
    for(int j = 0 ; j < 5 ; j++ ){
      mas[y + i][x + j - 2] -= draw[w][i][j];
    }
  }
}

void repaint( int y, int x, int w){
  for(int i = 0 ; i < 5 ; i++ ){
    for(int j = 0 ; j < 5 ; j++ ){
      mas[y + i][x + j - 2] += draw[w][i][j];
    }
  }
}

bool rec( int y, int x, int n){
  if( n < 0 ) return false;
  if( y == 10 ) return n == 0;
  if( mas[y][x] == 0 ) return rec( y + (x == 9), (x + 1) % 10, n);
  for(int i = 0 ; i < 3 ; i++ ){
    if(!check( y, x, i)) continue;
    paint( y, x, i);
    if(rec( y, x, n - 1)){
      cout << x + (i == 1) << " " << y + 1 + (i == 2) << " " << i + 1 << endl;
      return true;
    }
    repaint( y, x, i);
  }
  return false;
}

int main(){
  cin >> q;
  for(int i = 0 ; i < 10 ; i++ ){
    for(int j = 0 ; j < 10 ; j++ ){
      cin >> mas[i][j];
    }
  }
  rec( 0, 0, q);
 }