KUPC2014-京都オンサイト
オンサイトがせっかく近くで開催されたので、遊びに行ってきた。
コンテスト開始まで
早起きして9時頃に京都に着き、最近読んだ「聖なる怠け者の冒険」の舞台になった三条をうろうろ
特にすることもなくなったので11時ごろに三条を出て、ヨガをする人々などを横目に出町柳まで鴨川沿いを北上する
お昼ごはんに生協でささみチーズカツを食べる。うまい。
時計台の下に行くとみんなが集まっており、会場へ引率してもらう
コンテスト開始
- A
ソートして引き算して絶対値とるだけ。
- B
はじめてのリアクティブな問題。1以上1000以下の任意の暗号が決められており、数字を出力すると、暗号がその数で割り切れるかどうかを返してくれる。これを200回以下繰り返して暗号が何か判別する問題だった。ミスしてたりデバッグ用出力消してなくてWAもらいまくってあまりよくなかった
- C
長さの違うふたつの数列をごにょごにょして仲良し度合いを図る問題。
2つの文字列長のGCDをごにょごにょするらしいので近いうちにときなおしたい。
問題文に京子先輩と結衣先輩が出てきた。
結果はAとBだけ解けて２完+Jの部分点でした。
まとめ
コンテストは惨敗だったけれど、いろんな話を聞けてよかった。
オンサイトにいくとやる気が出る気がするのでとてもとても良かった。
TCO Algorithm Round 2B easy 解き直し
easy落ちなので解き直したgreedy解
ネスト深すぎィ!
考え方
'?'が出現した場合、'?'以外の文字にあたるまで出現行を下に辿って行く。
- 初めにあたったのが'+'だった場合、'?'が出現した行ですでにlampを点灯させていれば'?'を'+'に置き換える。
- 初めにあたったのが'-'だった場合、'?'が出現した行ですでにlampを消灯させていれば'?'を'-'に置き換える。
以下の図の場合1レベル目の手本と一致させるなら、少なくとも1文字目を点灯させる必要がある。
1レベル目の2文字目である'?'から下に辿って行くと'+'があり、1レベル目の2文字目を'+'に変更しても新たにコストはかからないので'+'に変更しておく。
よって1レベル目終了後のlampの状態は"++-"となる。
※紙に実際に解いていて気付いた、greedyの証明は略。
#include <string> #include <vector> using namespace std; typedef long long ll; class SwitchingGame{ public: string now=""; ll len; ll sum=0; bool checkSame(string s){ for(int i=0;i<len;i++){ if(s[i]==now[i] || s[i]=='?'){} else{ return false; } } return true; } int timeToWin(vector <string> states){ len=states[0].size(); for(int i=0;i<len;i++)now+='-'; for(int i=0;i<states.size();i++){ sum++; //cout<<i<<" "<<now<<endl; if( checkSame(states[i]) ){} else{ bool up=false,down=false; for(int j=0;j<len;j++){ if(states[i][j]=='+' && now[j]=='-'){ up=true; //cout<<"will up"<<i<<j<<states[i]<<now<<endl; now[j]='+'; } else if(states[i][j]=='-' && now[j]=='+'){ down=true; //cout<<"will down"<<i<<j<<states[i]<<now<<endl; now[j]='-'; } } if(up){ sum++; //cout<<"use up"<<endl; for(int j=0;j<len;j++){ if(states[i][j]=='?'){ for(int k=i+1;k<states.size();k++){ if(states[k][j]!='?'){ if(states[k][j]=='+'){ now[j]='+'; break; } else break; } } } } } if(down){ sum++; //cout<<"use down"<<endl; for(int j=0;j<len;j++){ if(states[i][j]=='?'){ for(int k=i+1;k<states.size();k++){ if(states[k][j]!='?'){ if(states[k][j]=='-'){ now[j]='-'; break; } else break; } } } } } } } return sum; } };
SRM621 div2 反省会
easyもmediumも問題文読めたし、方針も立った。
「お、これ2完じゃね」とか言ってたら0完太陽生えたので、今のうちに解き直しておきます。
easy
問題
50文字以下の文字列を、50個以下含む配列stringListが与えられる。
これらの並び順が
- 昇順の辞書順(例:"car" < "carriage" < "cats" < "doggies")にソートされていれば「"lexicographically"」
- 昇順の文字列長順(例:"car" < "cats" < "doggies" < "carriage")にソートされていれば「"lengths"」
- 両方にあてはまれば「"both"」
- どちらにもあてはまらなければ「"none"」
を返す。
解き方
o(n)で比較するだけ
「コピーとって、ソートしたものと元配列を比べる」みたいな人のほうが多かった
なお「"lengths"」を「"lentghs"」と記述したため落ちた模様
#include <string> #include <vector> using namespace std; typedef long long ll; class TwoWaysSorting{ public: bool checkDic(vector<string> a){ for(int i=0;i<a.size()-1;i++){ if(a[i]>a[i+1])return false; } return true; } bool checkLen(vector<string> a){ for(int i=0;i<a.size()-1;i++){ string x=a[i],y=a[i+1]; if(x.size()>y.size())return false; } return true; } string sortingMethod(vector <string> stringList){ bool a=checkDic(stringList); bool b=checkLen(stringList); if(a && b)return "both"; else if(a && !b)return "lexicographically"; else if(!a && b)return "lengths"; else if(!a && !b)return "none"; return "none"; } };
medium
問題
10^6 以下の非負整数を20個以下含んだ配列Sが与えられる。
この配列に含まれる整数を組み合わせて作ることが出来ない、最小の値を出力する。(例: S={1,2,3} とすると、出力は 7)
解き方
要素数が20個ほどなのでdfsで全列挙しておき、出現していない値を下から探した
なお全列挙の結果保存用配列のサイズを (10^6 + 1) しかとっておらず、次の日に (20*10^6 + 1)に変えたら通った。
よくよく見直すとちゃんとセグフォってたし、どう考えても気づくべきだった。
#include <vector> using namespace std; class NumbersChallenge{ public: vector<int> str; bool num[2000001]; bool dfs(int i,int sum){ num[sum]=true; if(i==str.size()){return false;} if(dfs(i+1,sum)){return true;} if(dfs(i+1,sum+str[i])){return true;} return false; } int MinNumber(vector <int> S){ str=S; bool trash=dfs(0,0); //返り値ｓは再起時のみ利用 for(int i=0;100001;i++){ if(num[i]==0)return i; } return 0; } };
おまけ
midiumをDPで解いている人も多かったのでDPでも解いてみた
#include<vector> using namespace std; bool dp[2000001]={}; class NumbersChallenge{ public: int MinNumber(vector<int> S){ dp[0]=true; for(int i=S.size()-1;i>=0;i--){ for(int j=2000000;j>=0;j--){ //値の2重使用対策 if(j-S[i] >=0 && dp[j-S[i]]){ dp[j]=true; } } } for(int i=0;i<2000001;i++){ if(dp[i]==false)return i; } return 0; } };
まとめ
- 雑魚のくせに早解きしようとするからミスる、確認はしっかりしよう。
- 返す文字列など、指定されているもののtypoは致命傷(トラウマだし次から全部コピペしようかな...)。
- 値の制約、必要な配列のサイズをよく考えてからコードを書き始めよう。
- 本を参考にしないとdfsすらまともに書けないのそろそろなんとかする。
TCO14 Algo 1C hardを解いてみた
昨日の記事、TCO14 Algo 1C - やざてんのいろいろの追記です。
hardの感想で「わかりませんでした。」 とか言ってたら、わざわざ解法を教えて下さった方がいたので解きました。
解法
移動した回数(N)に対する期待値を試しに N=0～6 まで計算してみると、「1, 2, 2.5, 3, 3.75, 4.0625, 4.375」となり、それぞれの値を求める式は x(N)=x(N-1)+gapとなる。
また、このgapは1から始まり、Nが2で割り切れる値になる度に「gap*=(N-1)/N」で更新される。
これをN回繰り返し計算すれば良い。
using namespace std; class RedPaint{ public: double expectedCells(int N){ double ans[501]={1},gap=1; for(int i=1;i<=N;i++){ if(i%2==0)gap *= ( (double)(i-1)/(double)i ); ans[i]=ans[i-1]+gap; } return ans[N]; } };
- 実はうまいアルゴリズムが思いつかなかったので、自分でもN=0～4まで調べていた。増加量が「1, 1, 0.5, 0.5 0.375」となっていたので、なにか漸化式っぽいものが立てられそうだな～と思ったが思いつかず諦めていた。
- コメントを頂いた方も言っていたが、いまいち証明ができない解法を使うのはモヤモヤするので、dp解法もいずれ解いておきたい。
TCO14 Algo 1C
参加しました。
結果は、easyとmedを解いて632点の720位
easy
アルファベットからなる文字列が与えられる。
文字列を先頭から見て、1度目の出現ではないアルファベットを削除して出力する。(banana -> ban)
やるだけ。
1度目の出現であれば空文字列に順次追加していき、2度め以降の出現であればスルーする。
medium
FizzBuzzをしたとき、整数A～整数Bまでに出現するFizz数とBuzz数とFizzBuzz数を出力する。
NまでのFizz数 = N/3 - N/15
NまでのBuzz数 = N/5 - N/15
NまでのFizzBuzz数 = N/15
を計算する。
あとは、A～BまでのFizz数 = (BまでのFizz数) - (A-1までのFizz数) で求めるだけ、他の2つも同様。
hard
足元に色を塗りながら移動するロボットが、1次元直線上を左右にN手移動する。(Nは整数)
このとき、ロボットが塗るマスの数の期待値(?)を求める。
普通に試すと最大2^500なのでどう考えても間に合わない。
現在地、塗った数、残り移動数 とかがわかれば状態が一意に決まるんじゃないかなーとか思う、がわからなかった。おわり。
レートが893まで回復したので、次くらいにはYazatenからYazatenになれそう。
750位くらいまでRound2にいけるっぽいと聞いたので、ちょっと期待しながら寝る。おやすみなさい。
batファイルを利用してMinecraftのログやバックアップを取る
目的
Minecraftのマルチプレイで、「ワールドデータを巻き戻したい！」と思うことが時々起こる
巻き戻すためのバックアップをとるには「world」のディレクトリをコピペすればよい。
が、手作業でやるのはめんどくさい
なので鯖を立てる度に自動でコピペ、ログ生成されるようにする
アプローチ
C言語から「system()」関数とか使ってコマンドラインいじれば良いかな？と思ったものの
- わざわざそのためだけにコード書くのはアレ
- ググったらbatファイルで簡単に出来そう
とのことでbatファイルをちょろっとお勉強することに
バックアップの方法
- 「backup.bat」という名前のファイルを作成し、以下のように記述する。
- 事前に「back」という名前のフォルダを、上記の「backup.bat」と同じ場所に作成しておく。
- そうすれば「backup.bat」からサーバーを起動した場合、「年-月-日--時-分-秒」の形*1でワールドデータを「back」フォルダの中に保存し、かつ「list.log」というファイルにバックアップをとった日付&時刻を記すことができる
set name=%date:/=-%--%time::=-% :変数nameに日付と時刻のデータを入れる cp -rp world back/%name% :backフォルダにワールドデータをコピーする echo %date%--%time% backed up.>>back/list.log :logファイルにバックアップをとった日付と時刻を書き込む minecraft_server.1.7.5.jar :サーバーを起動する
※「minecraft_server.1.7.5.jar」の1.7.5部分は、バージョンによって書き換える
覚えたこと
setコマンド
「set str=いろは」とすると、変数strに文字列"いろは"が格納されるっぽい
echoコマンド
「echo Hello >> sample.txt」とすると、sample.txtに"Hello"と追加書き込みされる
「>>」を「>」に変えると上書きになる
おまけ
こんな風に記述したbatファイルをスタートアップにおいておけば、パソコンを起動した日付のログがとれて楽しそう
set name=%date%--%time% booted. echo %name% >> ../date-time.log
さいごに
鯖立てる度にバックアップとるので、ワールドのデータサイズによってはかなり容量を使います。ちょくちょく消しましょう。
*1:2014年4月2日の12時34分56秒の場合 : 2014-04-02--12-34-56.00
