ACM/ICPCアジア地区予選 Day3

エクスカーション，いわゆる企業見学．

平日の中央線上り，という事をすっかり忘れていたため，危うく遅刻するところだった．服装は，スーツでなくていいので楽だった．DeNA，Google，KLabを回った．詳細は略．非常に申し訳ない事に，寝不足だったため，説明中に少しうたた寝をしてしまった．16:00過ぎに解散．

□全体の感想
今年が(学校としても)初めての参加だったので，分からないことが多かったですが，楽しく過ごせたと思います．私の学校には，競技プログラミングに興味を持っている学生がほぼ居なかったので，こういう場でこういう事に興味を持つ方々と色々話せた事は有益でした．他学校ではICPCの知名度が高いため，今後，東京高専にもICPCを初めとする競技プログラミングに興味をもつ人が増えてくれればと願います．まだ，2~3回は出場できるようなので，意地でも世界大会に出たいと思います．

稚拙な文章ですが読んで下さった方には感謝．

ACM/ICPCアジア地区予選 Day2

いわゆる本選．

8:40-集合
全員集合した後，会場へ移動．後ろテーブルのicp.javaとちょこちょこ話しつつ準備を進める．体調も良く，眠眠打破も服用済み．運営トラブルのため開始が遅れた．
9:49-コンテスト開始
まずは，私がテンプレを打ち込んだ後，Aを解く．BはAndoが解法を考えた(DP)．主にそれに沿った組んだが，何か上手く行かないので，一旦ソースを印刷して，後回し．
いくつかの問題を読んでみるが，どれも難しそう…．
Andoが修正したBを提出，WA．ちょっとして更に修正し提出，AC．
Cを実装してみるが，探索方法をちょこまか変えてしまった挙句，結局組み終わらなかった．
FはDPかな?と思って組んでみたがO(QN)の解法であったので，見事にTLE．定数倍最適化をちまちまやったが通らなかった．
終了30分前に，コスト最大のエッジから消していきDFSに経路探索という方針でGを組んだが，TLE．経路探索はDijkstraだろうなと思ったが，どう拡張すればいいか思いつかなかった．
14:49-コンテスト終了
2問ACという非常に残念な結果に終わった．12Fに移動．
15:20-問題解説
多くの問題について"easy, but not too easy."とのこと．Cは探索で良かったが，一工夫必要の模様．Fは数論的性質を使う問題だったらしい．Gはおよそ↑の方針で合ってた．急にどっと疲れが出たため，解説中うたた寝をしてしまった．
16:10-Javaチャレンジ対戦
多くのチームはそこまで用意周到ではなかったと見えて(私のチームでは，シミュレータを実装し，事前に組んだAIを持って行った)，チームnyamaはどんどん勝ち進めて行き，ベスト4に入ってしまう．結局，チームImoに勝ち，3位になってしまった．1，2位が東大チームであるのに対し，3位が東京高専チームというのは若干(結構)浮いていた．
16:50-表彰式・閉会式
USAGI Codeが全問解答，化物かと思った．ちなみに，今年は(問題が難しかったためか)3問解けたら順位がついていた．
17:30-移動
近くのレストランへ移動．余り広くは無いため，身動きが厳しかった．
18:30-懇親会
食べ物は，昨日と同様主食が多く野菜が少なかった．鈴鹿高専の((^(^(^(^(^o^)^)^)^)^))とエンカウント出来た．
20:30-Sake Challenge
流れ(?)でついて来てみる．酒は強くない&明日が早いため，飲まなかった．誰が誰だか分からないため，(Twitterの)アカウント名を教えてもらうまで，フォローしていた事に気付かなかった人も．
23:20-解散
割と終電ギリギリだった．案の定，竹橋駅ユーザは私だけだった．

□反省
一番の反省点は，1つの問題に固執してしまった事にあります．また，最初はとりあえず全部の問題を読むという基本的な事が出来ませんでした．これは，別に各人がどうこうというよりも，3人チームでいかに効率良く作業を分担するか，ということに関する経験の不足から来たものだと思います．
来年は，3人とも違う学校にいるため，このメンバでの参加は最初で最後となりましたが，普段の授業などでは決して得られない経験になったと思います．
これからは，安定した実力を身に付け，様々なタイプの問題に対処できるようにしたいです．

ACM/ICPCアジア地区予選 Day1

というわけで，1日目．

■1日目

□12:45-集合
Ando,nyama,私todo,コーチが到着．2Fで受付開始まで待機．
□13:00-受付
適当に済ませ，会場に入る．チームのテーブルがUstreamのカメラに一番近くてビビる．ちなみに後ろのテーブルは，chokudaiさん率いるicp.java．後ろの方に飲み物とお菓子があったので適当に補充した．
□14:00-開会式
□15:00-トライアルユース
PCの使い方にとりあえずヒヨる，というかパスワードを知らなかった時点であばばばば．さらに，PC²の設定を間違って弄ったような気がしたようなしないようなで動かなかったのでスタッフさんを呼んだ．正常に起動するまで結構時間を取られた．適当にA,B,Cを出してみる．通った事が確認出来たので安心．キーボードがちょっと使いづらかった，Page Up, Page Downキーが無い & Delteキーが変な位置にあった．
□16:15-Javaチャレンジ
事前にシミュレータは組んだ(私が)．で，作ったAIを前日に印刷しておいたので，それをひたすら打ち込んだ．作ったシミュレータが実際の物と違ったため，最初は正しく動作しなかったが，コードを微調整したらちゃんと動くようになった．あとは，Andoが少し修正を加えて提出．やはり，これをその場で考えて組むのは無理だと思った．
□17:45-Javaチャレンジ終了
3Fのホールに集まる．
□18:00-ウェルカムパーティ
とりあえず，お腹が減ってたので適当に食べる．ほとんど主食の部類に入るものだった．「これナンですか?」「ナンなんでしょう」
チーム紹介は，スライドが全てpdfに変換されることを知らなかったので，アニメーションが動かなった，残念．
津山高専や広島大学，chokudaiさんとも少し話せたので良かった．
□20:00-解散
予定より30分程早まった．この後は，さくさくっと帰宅した．最寄り駅が竹橋なのが私のみだったので悲しかった…．

明日が本選…．

ACM/ICPCアジア地区予選 Day0

ブログの書き方を忘れてしまっている位にご無沙汰しておりますが，私は生きております．

明日からICPCアジア地区予選です．主に↓のようなスケジュールで行われます．

12/11(土)：Javaチャレンジ
12/12(日)：本選
12/13(月)：企業見学

Javaチャレンジは，1週間前にゲームの内容が公開されるがコーディングはその場で行う，という方式です．昨日に仲間が考えたAIで勝負します．
本選は，5時間に約10問の問題を解きます．何回かの練習の結果，4~5問は解けそうに思います．
ちなみに，今年から地元民は(委員会が用意した)ホテルに泊まることが出来ないようです，残念．

模擬地区予選や以前の地区予選の問題をここ最近何問か解きましたが，何れコードをアップします．

国内予選から約5ヶ月．ついに，というよりは，あっという間に時間は過ぎてしまい，十分な練習を行ったとは言い難いです．しかし，国内予選という公的な試合で初めて結果を残せたという事もあり，自分にとっては今年の集大成の一つなので，良い結果を残したいと思います．

ACM-ICPC JAG Summer Camp 2010

国内予選から早2ヶ月半．
この時期は毎年，OB/OG の会による夏合宿が開かれるようです．
チームnyamaは14位だった為参加できませんでした(10位以内でないとダメ)が，合宿中のコンテストには参加出来るようなので参加してきました．

問題はhttp://m-judge.maximum.vc/より閲覧出来ます．

■Day2
寝坊．13:00頃から参戦しました．

A 雅先生の地球侵略日誌
適当に小さい値で試してみると，log₃Nみたいな感じ．ちゃっちゃと書いて提出．

B 友だちの誘い方
どうやって解くんだろう
->[i人なら問題無い人]の人数c_iを数える
->c_i+1<=iなら，c_i人誘える
->これを全てのiに対してループしてmaxを取れば…
->提出
->TLE
->O(n²)で，n<=10⁵だからTLEになるのは当たり前じゃないか
->Segment Tree使えばいいんじゃね?
->初めてのSegment Tree
->何か速くなった
->提出
->通ったー…?
->制限時間03:00[s]，実行時間04:37[s]
->ACはしたけど，Standsには影響しませんでした…

正式にACしたのは1問だけという残念振り．

■Day3
11:00項からの参戦．

A Ennichi
落ちゲーのシミュレーションすればいいのかな
->提出
->WA
->あれ…
その後，ACしたのは随分後になってからでした．まさか落下処理を間違えていたとは…．

B Carrot Tour
グラフ問題
->とりあえず，(i,j)間コストと，i->jと来た後kに進めるかを求めよう
->とりあえず，DFS
->とりあえず，サンプル合う
->とりあえず，提出
->とりあえず，TLE

全くやり方が思い浮かびませんでした．
終了後，red.cliff.jpの診断人さんのニコ生にて
[前のノード][今のノード][ニンジンの本数]=最短距離
のDPが出ていたので，サクサクッと組んだら，ACしました．

結局，この日も1問しか解けませんでした．

■Day4
ほぼ開始時刻直後から参戦．

A Alien's Counting
うーむ，とりあえずグラフにしてみよう
->連結でない所は，全く関わり合いがないので，強連結成分分解して，それぞれ求めて掛け合わせればいいのかな?(と意味不明な供述をしており)
->それぞれの値を求められない…

結局解けませんでした…

B Kaeru Jump
単純にDFSするだけでは?
->通った

D Dungeon Wall
壁が作れそうな所に作ってBFSするだけかな?
->TLE，BFS間違ってた
->修正，AC

H Ropeway
何か問題を読み間違えまくって，最終的には難しい問題だと分かりました…

この日は2問．もう一問位解きたいものです．

ACM/ICPC国内予選 コード

汚いけどコード晒しあげ．

A

import java.util.*;
import java.lang.*;
import java.io.*;
import static java.lang.Math.*;
import static java.util.Arrays.*;

public class A{
 Scanner sc;
 PrintWriter pw, db;

 int[] dx={-1, 0, 1, 0};
 int[] dy={0, 1, 0, -1};

 void run(){
  init();
  for(;;){
   int m=sc.nextInt();
   if(m==0)
    break;
   P[] ps=new P[m];
   ps[0]=new P(0, 0);
   for(int i=1; i<m; i++){
    int n=sc.nextInt();
    int d=sc.nextInt();
    ps[i]=new P(ps[n].x+dx[d], ps[n].y+dy[d]);
   }
   int xmin=0, xmax=0;
   int ymin=0, ymax=0;
   for(P p : ps){
    xmin=min(xmin, p.x);
    xmax=max(xmax, p.x);
    ymin=min(ymin, p.y);
    ymax=max(ymax, p.y);
   }
   int w=xmax-xmin+1;
   int h=ymax-ymin+1;
   db.println(w+" "+h);
   pw.println(w+" "+h);
  }
  close();
 }

 public static void main(String[] args){
  new A().run();
 }

 void init(){
  try{
   sc=new Scanner(new FileInputStream("A"));
   pw=new PrintWriter("A.out");
   db=new PrintWriter(System.out);
  }catch(IOException e){}
 }

 void close(){
  sc.close();
  pw.close();
  db.close();
 }

 static class P{
  int x, y;

  P(int x, int y){
   this.x=x;
   this.y=y;
  }
 }

}

B

import java.util.*;
import java.lang.*;
import java.io.*;
import static java.lang.Math.*;
import static java.util.Arrays.*;

public class B{
 Scanner sc;
 PrintWriter pw, db;

 int w, h;
 int[][] right, down;

 void run(){
  init();
  for(;;){
   w=sc.nextInt();
   h=sc.nextInt();
   if(w==0&&h==0)
    break;
   right=new int[h][w-1];
   down=new int[h-1][w];
   for(int k=0; k<h-1; k++){
    for(int i=0; i<w-1; i++)
     right[k][i]=sc.nextInt();
    for(int i=0; i<w; i++)
     down[k][i]=sc.nextInt();
   }
   for(int i=0; i<w-1; i++)
    right[h-1][i]=sc.nextInt();
   bfs();
  }
  close();
 }

 void bfs(){
  int[][] map=new int[h][w];
  LinkedList<P> q=new LinkedList<P>();
  P s=new P(0, 0);
  map[0][0]=1;
  q.addLast(s);
  while(!q.isEmpty()){
   P p=q.removeFirst();
   int x=p.x, y=p.y;
   int d=map[p.y][p.x];

   // up
   int nx=x;
   int ny=y-1;
   if(ny>=0&&down[y-1][x]==0&&map[ny][nx]==0){
    map[ny][nx]=d+1;
    q.addLast(new P(nx, ny));
   }

   // down
   nx=x;
   ny=y+1;
   if(ny<h&&down[y][x]==0&&map[ny][nx]==0){
    map[ny][nx]=d+1;
    q.addLast(new P(nx, ny));
   }

   // left
   nx=x-1;
   ny=y;
   if(nx>=0&&right[y][x-1]==0&&map[ny][nx]==0){
    map[ny][nx]=d+1;
    q.addLast(new P(nx, ny));
   }

   // right
   nx=x+1;
   ny=y;
   if(nx<w&&right[y][x]==0&&map[ny][nx]==0){
    map[ny][nx]=d+1;
    q.addLast(new P(nx, ny));
   }
  }
  db.println(map[h-1][w-1]);
  pw.println(map[h-1][w-1]);
 }

 public static void main(String[] args){
  new B().run();
 }

 void init(){
  try{
   sc=new Scanner(new FileInputStream("B"));
   pw=new PrintWriter("B.out");
   db=new PrintWriter(System.out);
  }catch(IOException e){}
 }

 void close(){
  sc.close();
  pw.close();
  db.close();
 }

 static class P{
  int x, y;

  P(int x, int y){
   this.x=x;
   this.y=y;
  }
 }

}

C

import java.util.*;
import java.lang.*;
import java.io.*;
import static java.lang.Math.*;
import static java.util.Arrays.*;

public class C{
 Scanner sc;
 PrintWriter pw, db;

 LinkedList<Integer> list1, list2;
 int[] dp1;

 static final int INF=1>>28;

 void run(){
  init();
  f();
  for(;;){
   int n=sc.nextInt();
   if(n==0)
    break;
   int a1=dp1[n];
   int a2=cal(n);
   db.println(a1+" "+a2);
   pw.println(a1+" "+a2);
  }
  close();
 }

 void f(){
  int n=1000000;

  list1=new LinkedList<Integer>();
  list2=new LinkedList<Integer>();
  for(int i=1;; i++){
   int t=i*(i+1)*(i+2)/6;
   if(t>n)
    break;
   list1.add(t);
   if(t%2==1)
    list2.add(t);
  }

  // 予め計算しておく
  dp1=new int[n+1];
  Arrays.fill(dp1, INF);
  dp1[0]=0;
  for(int j=1; j<=5; j++){
   for(int i=0; i<n; i++){
    if(dp1[i]!=j-1)
     continue;
    for(int k : list1){
     if(i+k<=n)
      dp1[i+k]=min(dp1[i+k], j);
    }
   }
  }
 }

 int cal(int n){
  int[] dp=new int[n+1];
  Arrays.fill(dp, INF);
  dp[0]=0;
  for(int j=1;; j++){
   for(int i=0; i<n; i++){
    if(dp[i]!=j-1)
     continue;
    for(int k : list2){
     if(i+k==n)
      return j;
     if(i+k<n)
      dp[i+k]=min(dp[i+k], j);
    }
   }
  }
 }

 public static void main(String[] args){
  new C().run();
 }

 void init(){
  try{
   sc=new Scanner(new FileInputStream("C"));
   pw=new PrintWriter("C.out");
   db=new PrintWriter(System.out);
  }catch(IOException e){}
 }

 void close(){
  sc.close();
  pw.close();
  db.close();
 }

}

D

import java.util.*;
import java.lang.*;
import java.io.*;
import static java.lang.Math.*;
import static java.util.Arrays.*;

public class D{
 Scanner sc;
 PrintWriter pw, db;

 static final int INF=1<<28;
 static final double EPS=1e-6;

 int w, h;
 int[][] field;

 int n;
 B[] bs;
 B root;

 boolean stable;

 boolean[][] visited;

 void run(){
  init();
  for(;;){
   w=sc.nextInt();
   h=sc.nextInt();
   sc.nextLine();
   if(w==0&&h==0)
    break;
   field=new int[h][w];
   for(int j=0; j<h; j++){
    String s=sc.nextLine();
    for(int i=0; i<w; i++){
     char c=s.charAt(i);
     if(c=='.')
      field[j][i]=-1;
     else
      field[j][i]=Integer.parseInt(""+c);
    }
   }
   identify();
   bs=new B[n];
   for(int i=0; i<n; i++)
    bs[i]=new B();
   genG();
   genTree();
   stable=true;
   dfs(root);
   db.println(stable?"STABLE":"UNSTABLE");
   pw.println(stable?"STABLE":"UNSTABLE");
  }
  close();
 }

 // id付け
 void identify(){
  n=0;
  visited=new boolean[h][w];
  for(int j=0; j<h; j++){
   for(int i=0; i<w; i++){
    if(!visited[j][i]&&field[j][i]!=-1){
     search(i, j, field[j][i]);
     n++;
    }
   }
  }
 }

 void search(int x, int y, int i){
  if(x<0||x>=w||y<0||y>=h)
   return;
  if(visited[y][x])
   return;
  if(field[y][x]!=i)
   return;
  visited[y][x]=true;
  search(x-1, y, i);
  search(x+1, y, i);
  search(x, y-1, i);
  search(x, y+1, i);
  field[y][x]=n;
 }

 // 重心の生成
 void genG(){
  LinkedList<Double>[] lists=new LinkedList[n];
  for(int i=0; i<n; i++)
   lists[i]=new LinkedList<Double>();

  for(int j=0; j<h; j++)
   for(int i=0; i<w; i++)
    if(field[j][i]!=-1)
     lists[field[j][i]].add(i+0.5);
  for(int i=0; i<n; i++){
   double sumx=0;
   for(double x : lists[i])
    sumx+=x;
   bs[i].g=sumx/4;
  }
 }

 // 木の生成，接地面のx座標の計算，根の決定
 void genTree(){
  for(int j=0; j<h-1; j++){
   for(int i=0; i<w; i++){
    int f1=field[j][i];
    int f2=field[j+1][i];
    if(f1==-1||f2==-1||f1==f2)
     continue;
    B b1=bs[f1];
    B b2=bs[f2];
    b1.left=min(b1.left, i);
    b1.right=max(b1.right, i+1);
    if(!b2.children.contains(b1))
     b2.children.add(b1);
   }
  }
  root=null;
  for(int i=0; i<w; i++){
   int id=field[h-1][i];
   if(field[h-1][i]!=-1){
    root=bs[id];
    root.left=min(root.left, i);
    root.right=max(root.right, i+1);
   }
  }
 }

 void dfs(B rt){
  if(!stable)
   return;
  if(rt==null)
   return;
  double mass=0;
  double mg=0;
  for(B b : rt.children){
   dfs(b);
   mass+=b.mass;
   mg+=b.mass*b.g;
  }
  // マージ
  rt.g=(mg+rt.mass*rt.g)/(mass+rt.mass);
  rt.mass+=mass;

  if(rt.g>rt.left+EPS&&rt.g+EPS<rt.right)
   ;
  else
   stable=false;
 }

 class B{
  LinkedList<B> children;
  double left, right;
  double g;
  double mass;

  B(){
   children=new LinkedList<B>();
   left=INF;
   right=-INF;
   mass=1;
  }
 }

 public static void main(String[] args){
  new D().run();
 }

 void init(){
  try{
   sc=new Scanner(new FileInputStream("D"));
   pw=new PrintWriter("D.out");
   db=new PrintWriter(System.out);
  }catch(IOException e){}
 }

 void close(){
  sc.close();
  pw.close();
  db.close();
 }

}

ACM/ICPC国内予選

ACM/ICPC国内予選 7/2 16:31~19:31

そして約1週間後，国内予選本番が始まりました．

問題と順位表はこちらから．

■チーム紹介
・大学名
Tokyo National College of Technology
・チーム名
nyama
・メンバ
todo
nyama
ando

■当日の流れ(時間はおおよそ合ってる)
16:31~
問題を印刷後，todoがテンプレを打ち込む．その間nyamaとandoが問題解析．

16:35~
2人の問題解析の結果を聞いてtodoがAを実装．若干ひよったためandoに助太刀してもらう．実装後は一発でAC．

17:00~
todoがBを実装．基本的にはただのBFSだが，壁であるかどうかの判定が怪しかった．更にこの時点で完全にtodoがひよってしまい，BFSを冷静に書く事が出来なかった．どうにか組んだもののWA．デバッグしても原因がわからなかったので，Cに移る．

17:30~
Cを解く，問題解析はすでに終わっていて，DPで解けるということが判明していたので，ある程度サクサクと組む．サンプルが通ったため，入力ファイルを落として試してみた所，挙動がおかしい．出力が非常に重い．andoより，関数呼び出し毎にnewするのではなく最初にだけnewすれば無駄に時間がかからない，と助言してもらい修正．AC．

17:55~
Bのデバッグに復帰．冷静に考えた結果，LinkedListをQueueとして使うはずなのに，pushとpopを用いていた．恥ずかしい．addLastとremoveFirstに修正後AC．

18:05~
ここまで来て実装担当のtodoが完全に疲れてしまったので，andoにEの実装を受け渡す．その間，todoとnyamaでDの実装について考える．木構造を作りDFSのように再帰的に重心を更新していけば判定が出来るという所までは分かった．

19:00~
Eのバグがとれずandoダウン．回復したtodoがDの実装を開始する．脳内コーディングは70%以上完了していた&神が降臨したため，尋常ではないスピードでコーディング．重心の更新式の間違いをandoに指摘してもらいつつ実装完了．が，挙動がおかしい．再帰呼び出しの際にxとyを逆にしてしまったのが原因であったが，暫く気付かなかった．その後色々早とちりを修正したらサンプルが通った．入力1はACしたが，焦っていた為入力2に対し入力1の出力を提出してしまいWA．この時点で残り10分を切っていたが，一旦心を落ち着けた後，入力2，3に対してAC．4問正解したのでStandingsを見てほっと一息．残り5分を切っていたのでこれ以上は何もしなかった．

19:31
終了．

■結果
○○○○×××
順位 - 14/288
大学別順位 - 7/68

模擬予選と同じ順位．アジア地区予選進出決定．

これが東京高専の本気(ｷﾘﾘﾘｯ

■感想
模擬予選と同じ順位でほっとしています．もし，本番での順位がもっと低かったら模擬予選での順位はマグレだったという事になるからです．
今回は，実装担当のtodoの調子が中々上がらず，序盤では随分とヘマをしてしまいました．仮に1人でやっていたら，せいぜい2問程度しか解けなかったと思われます．また，全体的に俄か仕込みで臨みましたが，実装をtodo，問題の解析をnyamaとandoと役割を(序盤では)完全に分離したのが功を奏しました．加えて，実装中は(主に)andoにチェックしてもらったのがバグ抑制に繋がりました．単独で実装すると，どうしてもちょっとしたミスが出てきてしまい，そこに気付かずにハマる，というパターンが多いためです．これらはチーム戦特有の作戦だと感じました．また，最後の勝因はラスト30分の追い込みでした．はっきり言って残り30分でDを実装できるとは思いませんでした．もしかしたら，標準的な人間の域を脱することがそろそろ出来るかもしれません．気のせいかもしれませんが．
チームのメンバーにとっても，東京高専全体にとっても，ICPCへの参加は初でしたが，恥ずかしくはない成績だと思います．

…でも，これはあくまで国内予選．

アジア地区予選ではまた別次元ですので，あと5ヶ月でそのレベルまで到達しなければなりません．
各人課題が見えたので，本格的にトレーニングを開始する…ということで…．

ACM/ICPC模擬国内予選

ACM/ICPC模擬国内予選 6/27 14:30~17:30

ACM-ICPC OB/OGの会では，毎年ACM-ICPC 国内予選の練習会を開催しています．ということで参加してきました．

チームの詳細は以下．
・大学名
Tokyo National College of Technology(東京高専)
・チーム名
nyama
・メンバ
todo
nyama
ando(都合により模擬予選は不参加)

■Problem A 連続する整数の和
入力される数値が小さいため，単純な2重ループで通す．
ちなみに，実装担当はtodo．

■Problem B ムーンライト牧場
todoがProblem Aを解いている間，問題をnyamaに読んでもらい，収入効率の計算式を作ってもらう．計算式が間違っていたため，一度WAを食らった．計算式を直したら問題なくAC．
式が分数だったため，分数の比較にした方がいいかなと思ったが，実数の(愚直な)比較のまま通ってしまった．
本当は，整数a，b，c，dに対し，
a/b<c/d
を判定するためには，
ad<bc
と書いたほうが良い．
あるいは，実数a，bに対し，
a<b
を判定するには，
(a-b)<EPS

この時点で上位のチームは4問提出していたので焦る．

■Problem C 差分パルス符号変調
二乗誤差を最小にする問題．ここで早くも息詰まる．2人で考えたが解法が思いつかないので一旦パスして他の問題にあたった．
その後，やっと[y_i][入力信号]のDPで解けばいいことに気付きサクッと実装．ほぼ一発で通った．

■Problem D Mr. リトー郵便局
最短移動時間を求める問題．全く解法が浮かばなかった．
解法はワーシャルフロイド法とのこと．

■Problem E 不死の宝石
問題内容は簡単．しかし，棒をどのように置けば良いかさっぱり検討がつかない．解法を話し合う内，nyamaの「2つの円の接線」という言葉でPOJにあった類似問題を思い出す．まず，2つの円に対し(今回は)高々16種類の接線を考えればよい．また，n個の円から2つの円を選び出すパターンはnC2通り，つまりO(n²)．そして，ある接線について，いくつの円が条件を満たしているかを調べるのはO(n)．ということで，せいぜいO(n³)．ここまでで脳内コーディングが終了したので後は実装するだけ．一度WAを食らったが，円が1つしか無い時の例外処理が間違っていて，入力がずれていた所為だった．時間がもう残り少ないのと，計算誤差が不安だったが，修正後は一発で通った．

■Problem F 閘門式運河: 上下に動く水面
実装ゲーっぽかったけど，そこまで解く時間が無かった．

■Problem G 魔法島物語2
二分法で解けるんじゃね?と思ったが，多角形(?)の内部に集落があるかの判定が難しかったのと，すでに時間が無かったので敢え無く終了．

■結果
○○○×○××
14/158

予想以上の結果に驚き．これが東京高専の本気(ｷﾘｯ