立命館合宿一日目！ （ rupc 2013 Day1 ）
今日は
まーす（@__math）さん
___じょにえる（@___Johniel）さん
とチームを組みました
チーム名:_____kyos
チームらしい動きをしたのは初めてのことで
とても楽しかったです。
（じょにえるさんにほとんど手伝ってもらってましたが・・・）
～～～～流れ～～～
私がまずA問題、まーすさんがB、じょにえるさんがCを読む
A問題がぱっと解法がわからなかったので、
PCをまーすさんにパスして、
じょにえるさんとAをうごうごする
まーすさんがBバグってるっぽいので
一回交代してAをどうにかする
バグ→交代→バグ→交代→AC(A)→AC（B）
この時点で約50分経過
この時点でヤバい人たちがCに手を付けてない感じがしたので
CをパスしてDEを先に解くことに
Dをまーすさん
Eを私とじょにえるさんでうごうご
Eは（私は半分ぐらいしか理解してない）コードを
じょにえるさんに言われるままにうごうご書いていく
なんか通った
Dをまーすさんがうごうごしている間に
他の問題を読んで方針が立つかを考える
Gがなんとかなりそう・・・？
この時点でDが通るか通らないかで残り時間が30分
Dを通すことに集中して
あまりでGをやることに
最後バグってしまって、コード印刷してみてみる事にしたら
印刷したコードが届く前に原因がわかる
つぶしてAC
Gをうごうごするが間に合わず
で 4完でした
～～～～～～～～～～～
～～～反省～～～～～
一番どうにかすべきなのはインデックスが0-baseか1-baseなのか
統一したほうが良いということ
今まで適当だったけど0-baseに変えよう
あとじょにえるさんがさすがというか
チームでの動きになれてらっしゃった
うちではチームで動けてないので
そういう練習というか
チームでうごうごする機会が必要だなぁと思った
あとリーダブルコードよんでバグ取りやすいコード書こう・・・・
あと終わった後の懇親会で思ったこと
いろんなデータ構造やら
アルゴリズムやら
コピペにしたって自分で理解した分と
自分で頑張って実装して
再利用できそうな分
ライブラリにして整理するって作業をしておくと
自分が何ができて何ができないのかよくわかっていい気がした
ライブラリ見ないとわからないのか
ライブラリから削除しても空で書けるのかとか
結構重要な気がする
（そもそもライブラリ今無いけど）
Ubuntu を USB に突っ込んでみる
http://shiroichi.sakura.ne.jp/2012/11/20121104ubuntu/
ここを参考に
家とか外とかで作業する環境がよく変わるので
これでどうにかできないかなと思ってる
どうにかなるのかしら・・・・
まあどちらにせよlinuxさんには触りたいので
お勉強かな
PS
何回かやり直したけど起動しない
またこんどやってみる
SRM 572 - med - 500
問題
文字をずらして
目的の文字列に変形する
変形にはコストがかかるので
そのコストの最小値を求める
不可能なときは-1を返す
変換規則
char++ or char--
'a-z'の範囲内で移動
文字列中の同じ文字が一度に移動する
#include <string>
#include <vector>
#include<deque>
#include<stack>
#include<queue>
#include<cmath>
#include<utility>
#include<iostream>
using namespace std;
class NextOrPrev {
public:
bool J(string s, string g){
int size=s.size();
for(int i=0;i<size;i++){
for(int j=0;j<size;j++){
if(i!=j && (( (s[i]<s[j]&&g[i]<g[j])||(s[i]>s[j]&&g[i]>g[j]) ) == false ) ){
cout<<i<<" "<<j<<endl;
return false;
}
}
}
return true;
}
int ANS(int nextCost, int prevCost, string start, string goal){
int ans=0;
for(int i=0;i<start.size();i++){
while(start[i]!=goal[i]){
if(start[i]<goal[i]){
start[i]++;
ans+=nextCost;
}else if(start[i]>goal[i]){
start[i]--;
ans+=prevCost;
}
}
}
return ans;
}
int getMinimum(int nextCost, int prevCost, string s, string g) {
if(J(s,g)){
return ANS(nextCost,prevCost,s,g);
}else{
return -1;
}
}
};
解法
この変換規則において変換可能なときは
変形時に同じ文字が出現しなければよい
s[i]→s[j]
g[i]→g[j]
の→が両方一致するとき可能
可能じゃない時を弾きたいのでfalse
あとはできることがわかっているので
一個ずつ足してやれば良い
SRM 572 - easy - 250
問題
与えられた数字を全てかけた時に
正 負 0
のどれになるかを返す
#include <string>
#include <vector>
#include<deque>
#include<stack>
#include<queue>
#include<cmath>
#include<utility>
#include<iostream>
using namespace std;
class EasyHomework {
public:
string determineSign(vector <int> A) {
int neg=0;
int size=A.size();
for(int i=0;i<size;i++){
if(A[i]==0){
neg=-1;
break;
}else if(A[i]<0){
neg++;
}
}
cout<<neg<<endl;
if(neg==-1){
return "ZERO";
}else if(neg%2==0){
return "POSITIVE";
}else{
return "NEGATIVE";
}
}
};
解法
負の要素を数えて偶数かどうかを調べる
途中に０があったら０
SRM 572 の感想
通ったの easy 242.4 のみ
rating 709->724
上がったけど良くない
easyは簡単だったけどmedは通すべきだった
地力が上がってない状態でratingが上がっても
維持できないので地力を上げたい
SRM 571 - easy - 250
読んでない
通った
#include<iostream>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<cmath>
#include<cstdio>
#include<map>
#include<set>
#include<algorithm>
using namespace std;
class FoxAndGame {
public:
int countStars(vector <string> result) {
int ans=0;
int sizei=result.size(),sizej;
for(int i=0;i<sizei;i++){
sizej=result[i].size();
for(int j=0;j<sizej;j++){
if(result[i][j]=='o'){
ans++;
}
}
}
return ans;
}
};
'o'を数えるだけ
SRM570 - div2 - hard - 1000
組み合わせの数を求める問題
A社はケーブル持ってて
B社はケーブル持ってないので
B社がなんとかなる組み合わせ（ケーブルがつながってる組み合わせ）
の数を数える
#include<iostream>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<cmath>
#include<cstdio>
using namespace std;
class CentaurCompanyDiv2{
private:
bool conect[60][60];
long long dp[60];
int N;
bool vis[60];
vector<int> sort;
public:
long long dfs(int x){
vis[x]=1;
if(dp[x]!=-1){
return dp[x];
}
long long res=1;
for(int i=0;i<N;i++){
if(vis[i]==0 && conect[x][i]==1){
res*=(dfs(i)+1);
if(res==0){
cout<<"hogehoge"<<x<<i<<endl;
}
}
}
if(res==0){
cout<<"hogee"<<endl;
}
dp[x]=res;
cout<<x<<" "<<dp[x]<<endl;
return res;
}
long long count(vector <int> a, vector <int> b){
long long ans=1;
for(int i=0;i<60;i++){
dp[i]=-1;
for(int j=0;j<60;j++){
conect[i][j]=0;
}
}
N=a.size()+1;
for(int i=0;i<N-1;i++){
conect[a[i]-1][b[i]-1]=1;
conect[b[i]-1][a[i]-1]=1;
}
for(int i=0;i<N;i++){
vis[i]=0;
}
dfs(0);
for(int i=0;i<N;i++){
ans+=dp[i];
}
return ans;
}
};
ケーブル接続が木になっている
（木:ループがないグラフ）
各ノード毎にdpを行う
木dpってのになるっぽい
各ノード以下の木でできる組み合わせの数を保持させる
（枝の長さ＊枝の長さ）＊枝の長さ・・・・
みたいな感じ
深さ優先探索しながらDPして
dpで保持した値を全部足す＋［B社がなにも持ってないパターンの1］
が答え
