読者です 読者をやめる 読者になる 読者になる

kyos1704活動記

適当に考えたことや調べたことを垂れ流すものです。質問等ありましたらtwitter:@kyos1704 に質問してください。

近況報告というか予定について

Facebookの方には書いたけどこっちには書いてなかったので。

院試落ちたので、学部を卒業するのを一年伸ばすことにしました。
卒業して受け直すことも考えましたが、
ICPC出られない
・単位が十分にとれてないので講義受けながら卒論書くのがだいぶつらい

ということでこうなりました。

結局バイトとかしてて時間の余裕があるかっていうと謎ですが

diffを埋められるらしい

こんなことを発言したら


こんなことになったのでできるだけ埋め返そうと思う

code festival 2014 参加記

予選

3問解けば通るだろとかたかをくくっていたら通らなさそうで慌てて4問目の部分点を取りに行った
あぶなかった

本戦

-1日目

いろいろあって精神的に死んでいたが明日からこどふぇだからがんばろうとか思っていた。
(なおこの問題は未だに解消されてないが解消手段が時間ぐらいしかないので耐えるしかなさそう)

0日目

@hotpepsi @climpet @Darsein でカレーを食べに行った。
夜遅く到着したので待たせてしまって申し訳なかった。
カレーを食べたあとclimpetさん以外の3人でお酒を飲みに行った。
ビールが最近のめるようになってきたので、黒ビールを飲んだ、おいしかった。
プログラミングの話をお酒飲みながらするのはめったにないので楽しかった。

1日目

参加したイベントは 本戦 DDR chokudaiさんのアルゴリズム擬人化トーク らいとにくトーク notさんの幾何トーク エキシビション

寝坊しかけるが開催時刻がそこまで早くなかったので助かった。
本戦は6問解くとパーカーだったのだが5問しか解けなかった。(5問勢が100人ほどだったらしいのでつらい)
明らかに6問目から難易度が上がっていると思ったのでパーカー調整だと思っていたがそういうわけでもなかったらしい。
(次回以降、賞品とかがあるなら作問陣に伝えておくと調整できて良いということをそのあとトイレ五個さんに伝えた)
問題はとても良かった。
Dは好きだけど賞品ありのコンテストで出題されるとchokudaiさんが刺されてしまいそうだと思った。
EのDP解を考えもしなかったのは弱い。(貪欲で通した)
6問目以降で手をつけたのは FとIの二問。Iが解けると思っていたがよく考えると解けない(解くのに必要なパーツを実装できない)ので勉強しないといけない。 FもTLEで死んでいた。
ということを考えるとまあ5問しか解けなかったのは実力通りなので、練習不足は悔しいがまあ仕方ないかなと思っている。

DDRはディズニーの方をやった。難易度がどれがどのぐらいかさっぱりわからないのがつらかった。

chokudaiさんトーク、ビームサーチを愛してることが伝わってきて良さだった。ぶっちゃけそれしか覚えてない。
ブルートフォースは女の子だとしたらまじめに作業を全部こなす事務員ちゃんだと思うのでよろしくお願いします。

にくとーくめっちゃたのしかった。目の下のつらみ。

幾何はまあ要するに解けるパターンを増やして身につけておいて、問題によって使い分けましょうという話だと理解した。
別に幾何以外でも同じだと思うので、練習しましょう(しよう)。

エキシビションはとてもすごかった。
climpetさんはまあ同じチームだったりしたこともあるのでコーディング見たこともあるので、@semiexp さんのをメインで見ることにしていた。
感想:タイピング早すぎ 必要なパーツにめどつけるの早すぎ 早すぎ(大事なことなので三回言いました
自分がやってることが超高速になったらこうなるんかなってイメージ通りではあったのだけどあのスピードを実現できる気がしないのでやばいなあと思っている。
最後のバグをきっちりとってACしていくのガチプロ
climpetさんがわーいわーいとタイプしていたのが良かった

だれだコンテスト中にBMSやってるやつは

1日目終了後

ゲーセン勢でゲーセンに行った。みんな音ゲーしていた。
私はsound voltexを二回 DDRを一回 load of vermilionというカードゲームを4回した。
load of vermilion楽しいので布教したいのだけど日常的に思考を取られるゲームなのでつらい。
DDRは体力増強のために続けていいなと思った(引っ越しをして近くにDDRがおいてあるゲーセンが存在する環境になるのでやれる)。

2日目

前日ゲーセンで夜更かししてしまったので朝プロ寝坊不可避と思っていたが普通に間に合った。
朝プロのほうが本戦よりハードだった。
med一問目からガチ問題だしやばいのでは・・・・(結果をみたらつらそうな人が存在したのでやばそう)
一問しか解けなかった C解きたかった・・・(Bは実力不足で解けなかったので見なかったことにしよう)

トークセッション色々聞きに行きました。ブッキングしまくって辛かった。
秋葉さんにサインをもらえたので嬉しかった(ついでにちょっとおしゃべりしたのも嬉しかった)
サイン用のペンをお貸ししたので、このペンはおそらく使うと解法が湧いてくるアーティファクトになったに違いない(妄想)

チーム対抗リレーは楽しかった。Komakiさんがガチプロだった(と思っていた 追記参照)
(最後の問題の回答をみんなで遊んでたらいつの間にかほぼ証明されていた)

追記


だれも自分が解いたと主張できない状態になっていそう

Fのループをつまらせたので申し訳ない気持ちになったが全完できたので罪を背負わずにすんだ。

表彰で参加してないイベントの様子とかがわかったのがだいぶ良かった。
書道家を無駄に使いすぎである!!!(批判しているわけではない)

2日目終了後

@climpet @konjo_p @Dersein で空港まで移動した。
時間結構ぎりぎりになって申し訳なかった(私があり本を忘れたせい)
北海道と九州という北と南から参加できるイベントでとてもいいなあと思った。

福岡についてからゲーセンに寄ってload of vermilionをしたら リーグがあがった。


まとめた感想

楽しかったです!!!来年もよろしくお願いします!!!!
ちなみに本戦87位 あさぷろmed31位 リレー7位でした

ICPC 2014 Domestic の進捗記録 と感想

Aは爆速で解けた(観戦してた人曰く19位だったらしい)

nikollsonさんがB、ちょっと手間取っている様子(1WA)

Cが方針が立たない、幾何でごり押すか、x座標を適当に列挙してy座標の比較でどうにかなるかで揉める

Dが圧倒的に簡単なのでDに移動 AC

Cを幾何方針でごり押していくことに決定、しかし重い

nikollsonさんがEを解いてくれていた
Eが軽いので実装 WA
初期化忘れなのでEもう一回提出 WA

CがやばいのでCを見ている

E全探索していいのではってなったので変更
間に合いそうだから実行してほっとく

なんか終わったので出したらAC

Cわかんねえ 交差している点を出しているあたりがバグっている

ライブラリ間違ってるのでは

終了

感想

Cが幾何とかいう方針間違いがつらかった。
ライブラリ普通にバグっていた気がしたのであとで調査しないといけない。
あとE全探索で余裕だということに気がつくのが遅すぎである
つらすぎ

ICPC 2014 Domestic

A

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

int x,y,s;

bool input(){
  cin>>x>>y>>s;
  if(x==0&&y==0)return false;
  return true;
}

int pre(int a){
  for(int i=s+100;i>=0;i--){
    if(i*(x+100)/100 == a){
      return i;
    }
  }
  return 0;
}

int solve2(int a,int b){
  a = pre(a);
  b = pre(b);
  if(a==0)return 0;
  if(b==0)return 0;
  return a*(y+100)/100 + b*(y+100)/100;
}

int solve(){
  int tmp = 0;
  for(int i=0;i<s;i++){
    tmp = max(tmp,solve2(i,s-i));
  }
  return tmp;
}

int main(){
  while(input()){
    cout<<solve()<<endl;
  }

}

B
nikollsonさんが通してくれました

C
終わったあと書いたコード(正しい保証はない)
追記::climpetさんがdiffとってくれました 大丈夫っぽいそうです

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

const double EPS = 1e-8;
int n,r;

struct S{
  double l,r,h;
};
vector<S> in;
vector<double> check;
void init(){
  in.clear();
  check.clear();
}
void setCheck(double x){
  check.push_back(x+2*EPS);
  check.push_back(x-2*EPS);
}
bool input(){
  cin>>r>>n;
  if(r==0)return false;
  setCheck(0);
  for(int i=0;i<n;i++){
    double l,r,h;
    cin>>l>>r>>h;
    in.push_back(S{l,r,h});
    setCheck(l);
    setCheck(r);
  }
  return true;
}

double y(double x,double t){
  if(abs(x)>r)return -1;
  return t + sqrt(r*r - x*x) - r;
}

bool checkXjudge(double x,double y){
  if(y<0)return true;
  for(int i=0;i<in.size();i++){
    if(in[i].l<x && x< in[i].r){
      if(y<=in[i].h)return true;
    }
  }
  return false;
}

bool judge(double t){
  for(int i=0;i<check.size();i++){
    if(!checkXjudge(check[i],y(check[i],t))){
      return false;
    }
  }
  return true;
}

double solve(double lt,double rt,int nn){
  if(nn==0)return lt;
  double v = (lt + rt)/2;
  if(judge(v)){
    return solve(v,rt,nn-1);
  }else{
    return solve(lt,v,nn-1);
  }
}


int main(){
  while(init(),input()){
    cout<<fixed<<setprecision(10)<<solve(0,100,100)<<endl;
    cerr<<fixed<<setprecision(10)<<solve(0,100,100)<<endl;
  }
}

D

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

string s;

bool input(){
  cin>>s;
  return s!="#";
}

vector<string> ans;


string conv(string s,int n){
  for(int i=0;i<s.size();i++){
    if(n & (1<<i)){
      if(s[i] == 'z')return "#";
      s[i] = s[i]+1;
    }
  }
  return s;
}


bool judge(string s,string pre){
  for(int i=1;i<26;i++){
    for(int j=0;j<pre.size();j++){
      if(pre[j]=='a'+i){
        pre[j] = 'a'+i-1;
        break;
      }
    }
  }
  return s == pre;
}

void solve(){
  ans.clear();
  for(int i=0;i<(1<<s.size());i++){
    string tmp = conv(s,i);
    if(tmp=="#")continue;
    if(judge(s,tmp)){
      ans.push_back(tmp);
    }
  }
}

void print(){
  cout<<ans.size()<<endl;
  cerr<<ans.size()<<endl;
  sort(ans.begin(),ans.end());
  if(ans.size()<10){
    for(auto i:ans){
      cout<<i<<endl;
    }
    return ;
  }
  for(int i=0;i<5;i++){
    cout<<ans[i]<<endl;
  }
  for(int i=5;i>=1;i--){
    cout<<ans[ans.size()-i]<<endl;
  }
}

int main(){
  while(input()){
    solve();
    print();
  }
}

E

#include<bits/stdc++.h>
using namespace std;
struct S{
  long long to,cost;
};

vector<long long> p;
vector<long long> d;

vector<vector<S>> edge;
vector<long long> use;
void init(){
  p.clear();
  d.clear();
  edge.clear();
  use.clear();
}


bool input(){
  long long n;
  cin>>n;
  if(n==0)return false;
  for(long long i=0;i<n-1;i++){
    long long tmp;
    cin>>tmp;
    p.push_back(tmp);
  }
  for(long long i=0;i<n-1;i++){
    long long tmp;
    cin>>tmp;
    d.push_back(tmp);
  }
  return true;
}



void make_edge(){
  edge.clear();
  edge.resize(p.size()+1);
  for(long long i=0;i<p.size();i++){
    long long c = i+1;
    long long to = p[i]-1;
    edge[c].push_back(S{to,d[i]});
    edge[to].push_back(S{c,d[i]});
  }
}


long long hoge(long long start){
  stack<S> st;
  st.push(S{start,0});
  vector<long long> use1(use.size(),-1);
  while(!st.empty()){
    S now = st.top();st.pop();
    if(use1[now.to]>=0)continue;
    use1[now.to] = now.cost;
    for(long long i=0;i<edge[now.to].size();i++){
      if(use[edge[now.to][i].to]){
        st.push(S{edge[now.to][i].to,now.cost + edge[now.to][i].cost});
      }
    }
  }
  long long ans = 0;
  long long cost = 0;
  for(long long i=0;i<use1.size();i++){
    if(cost<use1[i]){
      cost = use1[i];
      ans = i;
    }
  }
  return ans;
}

long long make_cost(long long start,long long end){
  stack<S> st;
  long long l;
  st.push(S{start,0});
  vector<long long> use1(use.size(),-1);
  while(!st.empty()){
    S now = st.top();st.pop();
    if(use1[now.to]>=0)continue;
    use1[now.to] = now.cost;
    for(long long i=0;i<edge[now.to].size();i++){
      if(use[edge[now.to][i].to]){
        st.push(S{edge[now.to][i].to,now.cost + edge[now.to][i].cost});
      }
    }
  }
  return use1[end];
}


long long make_use(){
  use.clear();
  use.resize(edge.size());
  for(long long i=0;i<edge.size();i++){
    use[i] = (edge[i].size()>1);
  }
  long long res = 0;
  for(long long i=0;i<edge.size();i++){
    for(long long j=0;j<edge[i].size();j++){
      if(use[i] && use[edge[i][j].to]){
        res += edge[i][j].cost;
      }
    }
  }
  long long c = 0;
  for(long long i=0;i<use.size();i++){
    for(long long j=0;j<use.size();j++){
      if(use[i]&&use[j]){
        c = max(c,make_cost(i,j));
      }
    }
  }
  res -= c;
  return res;
}


long long solve(){
  long long ans = 0;
  for(long long i=0;i<d.size();i++){
    ans +=d[i];
  }
  long long tmp = make_use();
  ans += tmp;
  return ans;
}


int main(){
  while(init(),input()){
    make_edge();
    long long tmp = solve();
    cout<<tmp<<endl;
    cerr<<tmp<<endl;

  }
}

AOJ 1184: Generic Poker

問題文
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1184

evimaさんのコードを見ながら解いたので完全に理解しているか怪しいが、おそらく日本語の解説が存在しないので書く。
というかもう一回やりたいのでその時用のメモ

間違ってる可能性が高いので間違ってたら教えて下さい

基本的なアイディア

すべてのパターンの手札を生成して、パターンに合致しているならば加算していく。
最後にすべてのパターン数で割ってやれば確率が出る。

手札のパターン生成について

手札はsortedなので、以下の様なコードにすることができる。

vector<int> hands;
void gen(int n){
	if(n==L){
		if(check())ans += count();
		return;
	}
	for(int i=hands[n-1];i<M;i++){
		hands[n]=i;
		gen(n+1);
	}
}

当然だがこれでは時間がかかりすぎるので、いくつか工夫をしてやる必要がある。

数字は高々7種類までしか使われないので、そこをどうにか減らしたい。

問題設定上、ランクの間に間隔がある時はいくつ離れていても問題ないことが読み取れるので、
sortedな手札の場合、隣り合うカードは
①同じ
②一個違い
③間隔がある
の3通りと考えて良い。

そうすると

vector<int> hands;
void gen(int n){
	if(n==L){
		if(check())ans += count();
		return;
	}
	hands[n] = hands[n-1];
	gen(n+1);
	hands[n] = hands[n-1]+1;
	gen(n+1);
	hands[n] = hands[n-1]+2;
	gen(n+1);
}

で十分だということがわかる。

パターンマッチ

上記の生成によって、パターンマッチには十分な情報を持つ手札が生成できている。
例えば手札は

1 1 2 4 4

のようになっている

①a b cの数字が決まっているとすると
それぞれのランクのカードが最低限何枚必要かがわかる(*はあまりを適当に割り振れば良いので無視できる)
最低限必要な枚数がわかっていればそれ以上手札にあるかチェックすれば良い。

②a b cの数字の決定の仕方
手札が決まっているということは、a b c は(もし+が存在すれば)必ず存在するので、
a b cが手札のどの札かというのを適当に仮定してやると、数字が決まる。
この時別に同じ札を選んじゃったりしてても、①の方法でチェックして大丈夫なら、マッチしていることは明らかなので良い。

マッチしたパターンの加算

パターンはもちろん本当はもっと数が多いのを減らしているので、パターンマッチが成功した時はちゃんと計算して足さないといけない。

N=3 M=10
1 1 2 4 4

の時のパターンの数を数える。

まず、それぞれの数について
1→3C2
2→3C1
4→3C2
なので、3C2 * 3C1 * 3C2

あとは生成パターンにおける数がどのランクになるかの計算をする。
間隔が開いているのは2-4の間なので、この手札にあるランクをMの数字の列から取り出すのは
f:id:kyos1704:20140523003420p:plain
上の2つの枠が、矢印のどこに入るかを求めれば良い。
2つの枠は順番は変わってはいけないので、[矢印の数]C[上の枠の数]のようなことをすれば求まる
( 今回は(7+1)C(2) )
あとはそれぞれについて全部かけてやればよい。

仮想マシンをubuntu上に作る

http://d.hatena.ne.jp/MIZUNO/20101118/1290092497
ubuntu-vm-builder