SRM689(div2) - chigichan24のお気持ち表明

こんにちは．chigichan24です．

昨晩SRM689(div2)に参加しました．

今年は受験なのでプログラミングは控えています(事実)

3月の時点でプログラミング禁をしようと思っていたのですが，やっぱりどうしてもおさえきれないこの気持ちって感じで，やりたい
欲が爆発しそうになってました．

その時に，@imishinist
twitter.com
先輩が鶴の一声を掛けてくださったのです．

氏「我慢しすぎるのよくなさそう．競技って2時間くらいで終わるわけだし，そこで発散するべき．(要約)」

私「わっかるぅ～～～～～～～～～～～～～」

ということでそれ以来ちょくちょく参加しました．

やっぱり勉強の辛さを発散するべきだなーって参加するたびに思います．

今回の結果はhardだけ通ると言う感じでした()
勉強の辛さは発散されても，全完逃したという辛さが蓄積されてしまう形になってしまいました．

まあ，競技はやってて楽しいので，この辛さは勉強に比べれば些細なものなんですけどね．．．

今回参加して思ったことは，

・コーディング力(正確には自分が書きたいコードを書く力)が落ちている．
・testでは落ちないようないやらしいバグを埋め込んでしまう．
・英語は全く引っかかることなく読める．

こんな感じです．
上の2つに関しては結果的に，hardはそれなりに大きなケースがtestにあったので，助かりましたが，他が全滅してしまいました．

しかし，英語が読めるようになっているというのは完全に成長だと実感しました．

自分は英語がかなり苦手みたいなので，成長を自分で感じることはほとんどありませんでした．しかし，自分の好きな競技プログラミングから成長を感じることができたのは大きな収穫です(おれじゅー先輩あたりに煽られて死にそう)．

まだまだ，受験のためにやらなきゃいけないことが山のようにありますが，たまには競技で汗を流していきたいです．

ヘッダくん

#include <bits/stdc++.h>
using namespace std;
const int dx[]={1,0,-1,0,1,-1,-1,1};
const int dy[]={0,1,0,-1,1,1,-1,-1};
const int INF = 1<<30;
const double EPS = 1e-8;
#define PB push_back
#define mk make_pair
#define fr first
#define sc second
#define reps(i,j,k) for(int i = (j); i < (k); ++i)
#define rep(i,j) reps(i,0,j)
#define MOD 1000000007
#define lengthof(x) (sizeof(x) / sizeof(*(x)))
#define LINF 1e18
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;

250

O(大文字のオー)を0(数字のぜろ)に，
I(大文字のアイ),l(小文字のエル)を1(数字のいち)に変換して一致するか見るだけ．

自作関数をなぜクラス外に書いているのかは謎．

vector <string> vs;
bool check(int idx,string &str){
	rep(i,vs.size()){
		if(i == idx)continue;
		if(str == vs[i]){
			return true;
		}
	}
	return false;
}
class SimilarUserDetection{
public:
	string haveSimilar(vector <string> handles){
		int len = handles.size();
		vs = handles;
		rep(i,len){
			rep(j,handles[i].size()){
				if(check(i,handles[i])){
					return "Similar handles found";
				}
				if(handles[i][j] == 'O'){
					handles[i][j] = '0';
					vs = handles;
					if(check(i,handles[i])){
						return "Similar handles found";
					}
				}

				if(handles[i][j] == 'l'){
					handles[i][j] = '1';
					vs = handles;
					if(check(i,handles[i])){
						return "Similar handles found";
					}
				}

				if(handles[i][j] == 'I'){
					handles[i][j] = '1';
					vs = handles;
					if(check(i,handles[i])){
						return "Similar handles found";
					}
				}
			}
		}
		return "Similar handles not found";
	}
};

500

適当にforを回して，?の位置に来る候補の数を見る．
なんでかわからないけど，long long の数1つで状態を管理しようとしている．

set <ll> memo;
class NonDeterministicSubstring{
public:
	long long ways(string A, string B){
        if(A.size() < B.size()){
            return 0;
        }
        rep(i,A.size()-B.size()+1){
            bool flg = false;
            string str="";
            rep(j,B.size()){
                if(B[j] != '?' && A[i+j] != B[j]){
                    flg = true;
                    break;
                }
                str += A[i+j];
            }
            if(flg){
                continue;
            }
            ll ret = 0LL;
            rep(j,str.size()){
                if(str[j] == '1'){
                    ret += 1LL<<j;
                }
            }
            if(memo.find(ret) == memo.end()){
                memo.insert(ret);
            }
        }
        return memo.size();
    }
};

1000

文字列A,Bが与えられる．
Aは並べ替えてオッケーで，

条件として，
A[i] == B[i]になってはいけない．
A[i] == A[i+1]になってはいけない．
の2つを満たすように並べ替えた時の通り数を求める問題．

制約で 1 ≦ |A|=|B| ≦ 15 だったので，並べ替える過程であとどの文字が使えるか(どの文字を既に使ったのか)を運べるなーと思いました．なので，

dp(現在のindex,index-1で使った文字情報,残り使える文字)

という感じの3次元DPしました．index=0の時だけ少し例外な処理をしますが，他はだいたい適当にポーイってやるだけです．
残り使える文字がvectorだったのと制約がゆるかったことから，mapで運びました．(これ制約がきつかったら普通に面倒だな)

自作関数をなぜクラス外に書いているのかは謎．

typedef pair<int,vi> subp;
typedef pair<int,pair<int,vi> > p;
map<p,int> memo;
string forbid;
vector<int>res;
int solve(int depth,int bef,vi &res){
	if(depth == forbid.size()){
		return 1;
	}
	if(memo[p(depth,subp(bef,res))]){
		return memo[p(depth,subp(bef,res))];
	}
	int ret = 0;
	rep(i,26){
		if(res[i] > 0 && forbid[depth] != i+'a'){
			if(depth != 0){
				if(bef == i){
					continue;
				}
			}
			res[i]--;
			ret = (ret + solve(depth+1,i,res)) % MOD;
			res[i]++;
		}
	}
	memo[p(depth,subp(bef,res))] = ret;
	return ret;

}
class ColorfulGardenHard{
public:
	int count(string garden, string _forbid){
		rep(i,26){
			res.PB(0);
		}
		forbid = _forbid;
		rep(i,garden.size()){
			res[garden[i]-'a']++;
		}
		return solve(0,0,res)%MOD;
	}
};

まとめ

・勉強をしよう().