#include<stdio.h>
#include<string.h>
char text[20];
int len,ans=0;
char cpy[20];
void saiki(int deep,int nowP){
if(deep==len){
//左右対称なら奇数になるはず
char c1,c2;
bool out=false;
cpy[nowP]='\0';
if(nowP%2==1&&nowP>2){
for(int i=0;i<nowP/2;i++){
c1=cpy[i];
c2=cpy[nowP-i-1];
if(c1=='i'&&c2!='i')out=true;
if(c1=='w'&&c2!='w')out=true;
if(c1=='('&&c2!=')')out=true;
if(c1==')'&&c2!='(')out=true;
if(c1=='{'&&c2!='}')out=true;
if(c1=='}'&&c2!='{')out=true;
if(c1=='['&&c2!=']')out=true;
if(c1==']'&&c2!='[')out=true;
if(out==true)return;
}
if(strstr(cpy,"iwi")==NULL)return;
ans=ans>nowP?ans:nowP;
}
}else{
cpy[nowP]=text[deep];//この文字を使う
saiki(deep+1,nowP+1);
saiki(deep+1,nowP);
}
}
int main(){
scanf("%s",text);
len=strlen(text);
saiki(0,0);
printf("%d\n",ans);
}
2262 Stopping Problem
ジョークなので何とも言えない言語ですが一応サイズ制限をなくせばチューリング完全らしいです。
まあ一応理論上はそうなんでしょうね。
過去に同じ状態を通ってないかメモしながら幅優先探索するだけです。
#include<stdio.h>
#include<set>
#include<queue>
int dxs[]={1,0,-1,0};
int dys[]={0,-1,0,1};//右、上、左、下の順
int r,c;
struct cur{
int x,y,arrow;//位置と向き
int num;//メモリの状態
bool operator<(const cur& c)const{
if(x!=c.x)return x<c.x;
if(y!=c.y)return y<c.y;
if(arrow!=c.arrow)return arrow<c.arrow;
return num<c.num;
}
cur move(int arrow){
cur re;
re.x=(x+dxs[arrow]+c)%c;
re.y=(y+dys[arrow]+r)%r;
re.arrow=arrow;
re.num=num;
return re;
}
};
int main(){
scanf("%d %d",&r,&c);
char map[22][22];
int x,y;
for(int i=0;i<r;i++){
scanf("%s",map[i]);
}
cur c1,nextC;
c1.x=c1.y=c1.num=c1.arrow=0;
std::set<cur> memo;
std::queue<cur> Q;
memo.insert(c1);
Q.push(c1);
bool stop=false;
while(Q.empty()==false){
c1=Q.front();
Q.pop();
x=c1.x;
y=c1.y;
char com=map[y][x];
if(com=='@'){
stop=true;//停止
break;
}
if(com=='?'){
//4方向全て試す
for(int i=0;i<4;i++){
nextC=c1.move(i);
if(memo.find(nextC)==memo.end()){
memo.insert(nextC);
Q.push(nextC);
}
}
continue;
}
if(com=='<'){
nextC=c1.move(2);//左
}else if(com=='>'){
nextC=c1.move(0);//右
}else if(com=='^'){
nextC=c1.move(1);//上
}else if(com=='v'){
nextC=c1.move(3);//下
}else if(com=='_'){
if(c1.num==0)nextC=c1.move(0);//0なら右
else nextC=c1.move(2);
}else if(com=='|'){
if(c1.num==0)nextC=c1.move(3);//0なら下
else nextC=c1.move(1);
}else if(com=='.'){
nextC=c1.move(c1.arrow);//そのまま
}else if('0'<=com&&com<='9'){
nextC=c1.move(c1.arrow);
nextC.num=com-'0';
}else if(com=='+'){
nextC=c1.move(c1.arrow);
nextC.num=(c1.num+1)%16;
}else if(com=='-'){
nextC=c1.move(c1.arrow);
nextC.num=(c1.num-1+16)%16;
}
if(memo.find(nextC)==memo.end()){
memo.insert(nextC);
Q.push(nextC);
}
}
printf("%s\n",stop?"YES":"NO");
}
2263 The First Acceptance
解法
とりあえず範囲が広いのでstd::mapを使って動的計画法を使ってみましたがなんか違う感じです。
皆メモリ使用量低で解いてますね。
私のコードはメモリを多めに使ってます。
#include<stdio.h>
#include<map>
#include<vector>
#include<algorithm>
struct S{
int a,b;
bool operator<(const S& s)const{
return b<s.b;
}
};
int main(){
int n,a,b,ans=0;
std::map<int,int> memo,nextMemo;
memo[0]=0;
scanf("%d",&n);
S s;
std::vector<S> vec;
for(int i=0;i<n;i++){
scanf("%d %d",&s.a,&s.b);
vec.push_back(s);
}
std::sort(vec.begin(),vec.end());
for(int i=0;i<vec.size();i++){
a=vec[i].a;
b=vec[i].b;
for(std::map<int,int>::iterator it=memo.begin();it!=memo.end();it++){
int t=(*it).first+a;
int t2=(*it).second+1;
int t3;
if(t>b)break;
if(memo.find(t)==memo.end()){
if(nextMemo.find(t)==nextMemo.end()||nextMemo[t]<t2)nextMemo[t]=t2;
t3=t2>nextMemo[t]?t2:nextMemo[t];
}else if(memo[t]<t2){
memo[t]=t2;
t3=t2;
}else{
t3=memo[t];
}
if(ans<t3)ans=t3;
}
memo.insert(nextMemo.begin(),nextMemo.end());
nextMemo.clear();
}
printf("%d\n",ans);
}
2264 Spanning Trees
解法
グラフを描いてみても時間をかけたら答えが見つかりそうな気もしつつ少しめんどくさかったので1分ほど他人のコードを知ら見してしまった。
ソースに解説はなかったので多分だけど用は正多角形としてグラフを描いたとき対角線を一番外側、一本内側、2本内側、、、ｎ/2本内側、、、1本内側、外側という順に結んでいく。
これを一点分回転すると重ならないグラフがｎ/２本描けるということらしい。
原理が分かるとなるほどな問題。
#include <cstdio>
using namespace std;
int n, k;
void solve(){
for(int st=0; st<k; st++){
int L=(n+st-1)%n;
int R=st;
for(int i=0;i<n-1;i++){
if(i%2==0){
printf("%d %d\n",R+1,L+1);
R=(R+1)%n;
}else{
printf("%d %d\n",L+1,R+1);
L=(L+n-1)%n;
}
}
printf("\n");
}
}
int main(){
scanf("%d %d",&n,&k);
if(k > n/2){
printf("-1\n");
}else{
solve();
}
}
最終更新：2013年01月23日 18:56
