Codeforces Round #177 (Div. 1)
受験終わって初回virtual。3完。辛い。
A. k種類の小文字アルファベットから成るちょうど長さnの文字列であって、隣り合う文字が全て異なるものの内、辞書順最小のものは何か。
流石にaから始まるのが辞書順最小で、次は隣り合う文字は異なってないといけないからbで、次はaでと考えると、ababab...となる。後は末尾にk-2種類の文字、それも辞書順最小なので当然'c' ~ 'c'+k-3を登場させると良いけど、ちょっと実装がだるい。k=1とかに気をつける
B. σはS={1,..., n}のS→Sな写像であって、「∀t(1 <= t <= k)について∃x(x∈N)が存在して、σ^x(t)=1」∧「∀t(k < t <= n)についてσ^x(t)=1を満たすxが存在しない」を満たす。σは何通りあるか。
こういった写像はdirected pseudoforestと対応するので、自明に1個のdirected pseudotreeと、{k+1, .. , n}→{k+1, .., n]の任意の写像1つの数え上げ。後者は自明に(n-k)^(n-k)。いちおうdirected pseudotreeと書いたけど、実はこの場合は有向辺と無向辺が一対一に対応して数え上げられるので、pseudotreeでいいはず。なんかpseudotreeといえば、閉路の各頂点に、0個以上の木がくっついてる形をしているわけだけれども、道しかくっついていないという嘘想定を何故かしてしまって死んだ。この良く分からん勘違い、春合宿でもやってしまったけどマジで意味が分からん。
結局やることとしては、σ^x(1)=1となるxが存在するわけだから、pseudotreeの閉路上に頂点1は存在する。後は、どうにでも出来ると思うけど、例えば閉路がt個の頂点から構成されるとすると、閉路上にある頂点は残りt-1個に関しては自由なので(n-1)C(t-1)通り。そしてt-1個の並びは自由なので(t-1)!通り。
後は木をこの閉路につけるわけだけど、ここで、一般に、無向グラフにおいて、十分に大きいnについて、n個の互いに非連結な成分C1 ~ Cnをn-1本の辺で連結にする時、異なる連結のさせ方は(π[i=1..n]Ci) × {(Σ[1..n] |Ci|)^(n-2)}通りある。これは∀iで|Ci|=1のとき、cayleyの公式と一致する。
以上から答えは、(n-k)^(n-k) × [Σ[t=1..k-1]{(t-1)! × (k-1)C(t-1) × t × k^(t-k-1)} + (k-1)!] となる(t == kのとき、t-k-1 = -1なことに注意する)。
C. 0~nの順列P0~Pnについて美しさを Σ[i=0..n] (i⊕Pi)で定義する(⊕はXOR)。可能な美しさの最大値と最大値を与える順列1つを出力せよ。
等式 A⊕B = A+B - ((A&B) << 1)を用いると(ここで&はAND)、Σ[i=0..n] (i⊕Pi) ≦ Σ(i+Pi) = n(n+1)であって、上界がn(n+1)であることが分かる。
貪欲に順列を構成すると、上界を達成することが出来ることを示す。
まず
- 2進数でnがk桁で表されるとすると、k桁で表される全ての整数tについて、t⊕x = 2^k-1となるようなxがただ1つ存在する。これはt&x = 0となるようなxがk-1桁以下で表される整数にただ1つ存在することによる。
- t1⊕x1 = 2^k-1, t2⊕x2 = 2^k-1の時、t1≠t2 ⇒ x1≠x2である
- 上記の条件でt⊕x = 2^k-1となる時、A&B = 0 ⇔ A+B = A⊕Bを考えるとt+x = t⊕x = 2^k-1である。
ここで、n以下でかつk桁で表される全ての整数の集合、すなわち、”離散な"閉区間(面倒くさいのでこう呼ぶ)S = [2^(k-1), n]に対して、T = {x | t∈S, t⊕x = 2^k-1}とすれば、t+x = t⊕xより、Tは離散な閉区間[2^k-1-n, 2^(k-1)-1]であり、S∩T=∅かつS∪T = [2^k-n-1, n]であるから、これらを全て消費すると、離散な閉区間[0, 2^k-n-2]が残るので、残った離散な閉区間に対して、同じ問題を再帰的に解いていくと良い。
こうして構成された順列は、全ての項について、i⊕Pi = i+Piが成り立っているので、上の考察からこれは上界を与えている。
なんか実装力が衰えすぎていたのと、この考察中々にややこしいのでめちゃくちゃなバグが発生しまくった。反省。
自分向けメモ： 貪欲の下界上界を先に意識するパターン忘れない。一回やったら流石にcombinatoricsは解けて...
四則演算するテスト
前書いたスタックを使って
前々から気になってた逆ポーランド記法に変換して処理する四則演算器書いた。
infix2postfix.h
#include <stdio.h>
#include <stdlib.h>
#include "stack.h"
enum Priority {NIL, LOW, MIDDLE, HIGH,};
static void check_argument(char **string, stack *st)
{
make_stack(for_string);
char *tmp;
tmp = (char *)malloc(sizeof(char));
if(tmp == NULL){
break_stack(*st);
return;
}
*tmp = ' ';
push_stack(st, tmp);
while(1){
tmp = (char *)malloc(sizeof(char));
if(tmp == NULL){
break_stack(*st);
return;
}
if(**string == '.' || **string == '_' || **string == '@' || ('A' <= **string && **string <= 'Z') || ('a' <= **string && **string <= 'z')){
*tmp = **string;
push_stack(&for_string, tmp);
++(*string);
}else if(**string == '('){
}else{
while(top_stack(&for_string) != NULL){
push_stack(st,top_stack(&for_string));
pop_stack(&for_string);
}
--(*string);
return;
}
}
}
static int check_constant(char **string, stack *st)
{
make_stack(for_string);
char *tmp;
tmp = (char *)malloc(sizeof(char));
if(tmp == NULL){
break_stack(*st);
return;
}
*tmp = ' ';
push_stack(st, tmp);
while(1){
tmp = (char *)malloc(sizeof(char));
if(tmp == NULL){
break_stack(*st);
return;
}
if('0' <= **string && **string <= '9'){
*tmp = **string;
push_stack(&for_string, tmp);
++(*string);
}else{
while(top_stack(&for_string) != NULL){
push_stack(st,top_stack(&for_string));
pop_stack(&for_string);
}
--(*string);
return;
}
}
}
static int ret_prio(char str)
{
enum Priority;
if(str == '(' || str == ')')return NIL;
if(str == '+' || str == '-')return LOW;
if(str == '*' || str == '/' || str == '%')return MIDDLE;
if( ('a' <= str && str <= 'z') || ('A' <= str && str <= 'Z') || str == ' ' || str == '_' || str == '@' || str == '.' || ('0' <= str && str <= '9'))return HIGH;
return -1;
}
char *convert(char *formula,char for_convert[])
{
int i = 0;
make_stack(st);
while(*formula != '\0'){
char *tmp;
while(*formula == ' ') ++formula;
if(*formula == '('){
tmp = (char *)malloc(sizeof(char));
*tmp = *formula;
push_stack(&st, (void *)tmp);
}else if(*formula == ')'){
while(*(char *)top_stack(&st) != '('){
if(top_stack(&st) != NULL){
*(for_convert+i) = *(char*)top_stack(&st);
++i;
free(top_stack(&st));
pop_stack(&st);
}else{
puts("error");
break_stack(st);
return NULL;
}
}
pop_stack(&st);
}else if( ('a' <= *formula && *formula <= 'z') || ('A' <= *formula && *formula <= 'Z') || *formula == '_' || *formula == '@' || *formula == '.'){
check_argument(&formula, &st);
}else if('0' <= *formula && *formula <= '9'){
check_constant(&formula, &st);
}else if(*formula == '+' || *formula == '-' || *formula == '*' || *formula == '/' || *formula == '%'){
while(top_stack(&st) != NULL && ret_prio(*formula) <= ret_prio(*(char *)top_stack(&st))){
*(for_convert+i) = *(char*)top_stack(&st);
++i;
free(top_stack(&st));
pop_stack(&st);
}
tmp = (char *)malloc(sizeof(char));
if(tmp == NULL){
break_stack(st);
return NULL;
}
*tmp = ' ';
push_stack(&st, (void *)tmp);
tmp = (char *)malloc(sizeof(char));
if(tmp == NULL){
break_stack(st);
return NULL;
}
*tmp = *formula;
push_stack(&st, (void *)tmp);
}else{
break_stack(st);
return NULL;
}
++formula;
}
while(top_stack(&st) != NULL){
if(*(char*)top_stack(&st) == '('){
int m;
puts("error");
break_stack(st);
for(m=0;m!=i;++m){
*(for_convert+m)='\0';
}
return NULL;
}
*(for_convert+i) = *(char*)top_stack(&st);
++i;
free(top_stack(&st));
pop_stack(&st);
}
break_stack(st);
return 0;
}
eval4rules.h
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <setjmp.h>
#include "stack.h"
double evaluation(char *formula,jmp_buf for_error){
make_stack(st);
double Ret;
char p[20]="";
while(*formula != '\0'){
const char *var_for_atoi;
if('0' <= *formula && *formula <= '9'){
double *num = (double*)malloc(sizeof(double));
if(num == NULL){
break_stack(st);
longjmp(for_error,-2);
}
while('0' <= *formula && *formula <= '9'){
char chr[2] = "";
chr[0] = *formula;
strcat(p,chr);
++formula;
}
var_for_atoi = p;
*num = atof(var_for_atoi);
push_stack(&st,num);
strcpy(p,"");
}else if(*formula == '+' || *formula == '-' || *formula == '*' || *formula == '/'){
double *num = (double*)malloc(sizeof(double));
if(num == NULL){
break_stack(st);
longjmp(for_error,-2);
}
double a,b;
if(top_stack(&st) == NULL){
break_stack(st);
longjmp(for_error,-1);
}else{
a = *(double*)top_stack(&st);
free(top_stack(&st));
pop_stack(&st);
}
if(top_stack(&st) == NULL){
break_stack(st);
longjmp(for_error,-1);
}else{
b = *(double*)top_stack(&st);
free(top_stack(&st));
pop_stack(&st);
}
switch(*formula){
case '+':
*num = a+b;
break;
case '-':
*num = b-a;
break;
case '*':
*num = a*b;
break;
case '/':
*num = b/a;
break;
}
push_stack(&st,num);
++formula;
}else if(*formula != ' '){
break_stack(st);
longjmp(for_error,-1);
}
++formula;
}
if(top_stack(&st) == NULL){
break_stack(st);
longjmp(for_error,-1);
}
Ret = *(double*)top_stack(&st);
free(top_stack(&st));
pop_stack(&st);
break_stack(st);
return Ret;
}
main.c
#include <stdio.h>
#include <setjmp.h>
#include "infix2postfix.h"
#include "eval4rules.h"
int main()
{
int i;
double n;
char formula[300];
char Result[10000] = "";
jmp_buf env;
i = setjmp(env);
if(i == 0){
scanf("%s",formula);
convert(formula,Result);
n = evaluation(Result,env);
printf("n:%f\n",n);
return 0;
}else if(i == -1){
puts("SyntaxError");
return -1;
}else if(i == -2){
puts("Stack memory limits");
return -1;
}
}
テストなので字句解析とかすっ飛ばしてるけど今ちゃんと書いてるので。
あと、エラー処理適当かなと。
stack,queueの実装
出来上がったと思うので一応うｐ
stack
#define make_stack(x); stack x;x.last=NULL;
#define make_stack_p(x); stack *(x)=(stack*)malloc(sizeof(stack));(x)->last=NULL;
#define break_stack(x); while(top_stack(&x)!=0x00000000){pop_stack(&x);}
#define break_stack_p(x); while(top_stack(x)!=0x00000000){pop_stack(x);}free(x);
struct _Stack{
void *content;
struct _Stack *front;
};
typedef struct{
struct _Stack *last;
}stack;
void *top_stack(stack *st){
if(st->last == NULL){
return (void*)0x00000000;
}
return st->last->content;
}
int push_stack(stack *st, void *variable){
struct _Stack *tmp;
tmp = (struct _Stack*)malloc(sizeof(struct _Stack));
if(tmp == NULL)return -1;
if(st->last == NULL){
tmp->front = NULL;
}else{
tmp->front = st->last;
}
tmp->content = variable;
st->last = tmp;
return 0;
}
void *pop_stack(stack *st){
if(st->last == NULL)return NULL;
if(st->last->front == NULL){
st->last = NULL;
}else{
struct _Stack *tmp = st->last;
st->last = st->last->front;
free(tmp);
}
return NULL;
}
queue
#define make_queue(x) queue x;x.first=NULL
#define make_queue_p(x) queue *(x)=(queue*)malloc(sizeof(queue));(x)->first=NULL
#define break_queue(x) while(top_queue(&x)!=0x00000000){pop_queue(&x);}
#define break_queue_p(x) while(top_queue(x)!=0x00000000){pop_queue(x);}free(x);
struct _Queue{
void *content;
struct _Queue *next;
};
typedef struct{
struct _Queue *first;
struct _Queue *last;
}queue;
void *top_queue(queue *que){
if(que->first == NULL)return 0x00000000;
return que->first->content;
}
int push_queue(queue *que, void *variable){
struct _Queue *tmp;
tmp = (struct _Queue*)malloc(sizeof(struct _Queue));
if(tmp == NULL)return -1;
tmp->content = variable;
if(que->first == NULL)que->first = tmp;
que->last = tmp;
return 0;
}
void *pop_queue(queue *que){
if(que->first == NULL)return NULL;
if(que->first->next == NULL){
que->first = NULL;
que->last = NULL;
}else{
struct _Queue *tmp = que->first;
que->first = que->first->next;
free((void*)tmp);
}
return NULL;
}
scanf
後輩の質問を受けた。
中1は基本的にC言語かJavaの勉強をしていて、AOJ解けって言ってた。
「AOJのVolume5の501がわかりません」
要は、文字列を変換するリストと、文字列が与えられるので変換後の文字列を出力しろと(nの上限決まってなかったりで疑問なんだが)。
んで、その中1はちゃんと自分の書いたソース載せてたのでちょっと書き加えた。
#include <stdio.h>
int main()
{
int n,m,i,j;
char a[1000],b[1000];
while(1){
scanf("%d",&n);
if(n == 0)return 0;
for(i = 0;i < n;i++){
scanf(" %c %c", &a[i], &b[i]);
}
scanf("%d", &m);
for(i = 0;i < m;i++){
char c;
scanf(" %c",&c);
for(j = 0;j < n;j++){
if(c == a[j]){
c = b[j];
break;
}
}
printf("%c",c);
}
puts("");
}
}
ハマったのがscanf。
はじめ、
scanf("%d", &n);
scanf("%c",&c[i]);
という風にしていたんだけれども、
アウトプットミスってるし
入力待ちがどうも想定してるインプットより少ないのでおかしいと思った。
出力よく見てると改行されてるので、scanf("%c\n",&c[i])にした。
すると、アウトプットは正しくなったが、逆にインプットを多く求められた。
結構ハマったあげく、調べてみるとこういうふうにあった。
http://www.pc.uec.ac.jp/sp/hshrkw/edu/program/b1/Ex2-1b.htm
初歩的なことなんだけど忘れてるとハマる。
結局、scanf(" %c",&c[i])にすることでうまく動いた。
気をつけよう(戒め)
stackの実装(続き)
とりあえず実装出来ました。
やっちゃいけないことしてる感があるのと、これでもまだ不完全なのが…（というか、なんで俺はＣ++使わない縛りをしているんだ？
#define make_stack(x) stack x;x.last=NULL
#define make_stack_p(x) stack *x=(stack*)malloc(sizeof(stack));x->last=NULL
struct _Stack{
void *content;
struct _Stack *front;
};
typedef struct{
struct _Stack *last;
}stack;
void *top(stack *st){
if(st->last == NULL){
return (void*)0x0;
}
return st->last->content;
}
int push(stack *st, void *variable){
struct _Stack *tmp;
tmp = (struct _Stack*)malloc(sizeof(struct _Stack));
if(tmp == NULL)return -1;
if(st->last == NULL){
tmp->front = NULL;
}else{
tmp->front = st->last;
}
tmp->content = variable;
st->last = tmp;
return 0;
}
void *pop(stack *st){
if(st->last == NULL)return NULL;
if(st->last->front == NULL){
st->last = NULL;
}else{
struct _Stack *tmp = st->last;
st->last = st->last->front;
free(tmp);
}
return NULL;
}
ええ、はい。そうです。defineです。
make_stackで宣言してもらうことでメンバ変数の初期化もこなしました。
しかし、これだと（もしかしたらあるんかな）定義していないダブルポインタ以上は扱えないという事に…
よろしくないので、どうにかしたいですね。
