バイオ系大学院生だけどプログラミングをしてみた

東京大学のバイオ系大学院生がプログラミングの勉強を兼ねて発信します。

AGC032 B - Balanced Neighbors

AGC032 B - Balanced Neighbors

グラフを考えて隣接してるものの和を一定にする問題。
問題は以下。

atcoder.jp

  • 考察

グラフを0から繋いで書こうとしても場合が多すぎて、Nが多くなったとき一般化できなさそう

隣接する和Sの最小値は、Nが一個だけ繋がってるときのNで、
最大値は、Nの頂点がすべてとつながっている場合で1~N-1までの和でN*(N-1)*1/2。
よって
和Sとして考えられる個数は
N<=S<=N*(N-1)*1/2
より
N*(N-3)*1/2 + 1(個)。

全探索してもいいかもしれないけど、グラフ自体の繋ぎ方が組合せ爆発を起こしそう。

グラフの繋がりは総当たり戦(隣接行列というらしい)みたいな表を作れば
考えられそう


N=3のサンプル、N=4は実験でこのようにするのが良い
f:id:coonevo:20190324025615j:plain

完全に繋いだとき(完全グラフというらしい)の和をmaxとして書いておくと、
繋がないとしたときのマイナスの値が上の方が大きくなれば良さそうだということがわかる

これをN=6でも書いてみても同じで
f:id:coonevo:20190324025615j:plain
こうなるので、これを実装してあげればいい。
Nの偶奇で表の規則性が変わるので、それに注意して実装。

コードは以下。
Submission #4678361 - AtCoder Grand Contest 032

#include <bits/stdc++.h>
using namespace std;

#define rep(i,N) for(int i=0;i<int(N);++i)
#define rep1(i,N) for(int i=1;i<int(N);++i)


typedef long long ll;
typedef vector<int> vi;
typedef set<int> seti;
typedef vector<string> vs;

const int MOD = 1e9+7;
const int INF = 1e9;

vector<int> Iv;
vector<int> Jv;
int N;
int main() {
	cin>>N;
	int X = N;
	if(N%2 == 0)X = N+1;

	int cnt =0;
	rep1(i,N+1)rep1(j,N+1){
		if(i<j)if(i+j!=X){
			cnt++;
			Iv.push_back(i);
			Jv.push_back(j);
		}
	}

	cout<<cnt<<endl;

	rep(i,cnt){
		cout<<Iv[i]<<' '<<Jv[i]<<endl;
	}
}

ABC106 C - To Infinity

ABC106 C - To Infinity

指数関数的に増えていく文字列を5000兆回増やしてその時のK番目を求める。

問題は以下。

atcoder.jp

  • 考察

冷静に考えれば指数関数的に長さが長くなっていくので'2'だったら
2^(5,000,000,000,000,000)個並びます。
Kがたかだか10^18であることを考えれば、'2'があった時点でK文字目まではそれで埋め尽くされる。

'1'は増えないので、先頭から順々にK文字目までみていったときに、
'1'以外があったらそれが答え、
K文字全部'1'だったら'1'が答えになる。


コードは以下。

Submission #4250847 - AtCoder Beginner Contest 045Submission #4420223 - AtCoder Beginner Contest 106

#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i=0;i<int(N);++i)

int main() {
	string S;
	cin>>S;
	char ans = '1';
	int K;
	cin>>K;
	rep(i,K){
		if(S[i]!='1'){
			ans = S[i];
			break;
		}
	}
	cout<<ans<<endl;
}

  • 余談

これは完全に自己満足なのですが、8月のコンテスト本番当日に書いたコード(Python)は以下でした。
Submission #3038673 - AtCoder Beginner Contest 106

S = input()
K = int(input())
s = [int(S[i:i+1]) for i in range(len(S))]
x=5000000000000000
m=0 
def fx(n):
    return n**x
y=list(map(fx, s))
for num in y:
    m=m+num
    if K <=m:
        a=num
        print(a)
        break

まあ当たり前のようにTLEなんですが、

x=5000000000000000

はウケるしそれを計算しようとしてるのも頭抱えたくなりますね。
成長を感じます(?)。

ABC045 B - 3人でカードゲームイージー / Card Game for Three (ABC Edit)

ABC045 B - 3人でカードゲームイージー / Card Game for Three (ABC Edit)

トランプみたいなやつ(雑)。

問題は以下。

atcoder.jp

  • 考察

ある人のターンを一つの関数(solve)として定義して、次のターンにいくみたいに再帰的に書いて長さが0だったら答えを出力するみたいに書いた。

最初の文字を削除するのがわからなかったが、stringではeraseというのを使って特定の位置の文字を削除できるらしいのでそれを使った。

charを数字に直したり小文字から大文字作るのはかなり普通に書けたので慣れたんじゃないかなと嬉しくなった。

想定解とかなり違うけど、こう書く人もいたのかなあ。
まだ慣れないので実装に時間がかかってしまってアレでした。
想定解も後で実装しておきます。

コードは以下。

Submission #4250847 - AtCoder Beginner Contest 045


#include <bits/stdc++.h>
using namespace std;

vector<string> S(3);
int turn_n;
char next_turn;

int solve(char turn){
	turn_n=turn-'a';
	if(S[turn_n].size()==0){
		cout<<char(turn+'A'-'a')<<endl;
		return 0;
	}
	next_turn = S[turn_n][0];
	S[turn_n].erase(S[turn_n].begin());
	solve(next_turn);
}
int main() {
	cin>>S[0]>>S[1]>>S[2];
	solve(S[0][0]);
}

ABC051 C - Digits in Multiplication

ABC051C - Digits in Multiplication

ある数を二つの因数に分解して、それらの桁数の大きい方を取ったときに、その最小値。

問題は以下。

atcoder.jp

  • 考察

ある数Nを二つの因数に分けるとき、その小さい方をAとすれば
Aは1以上√N以下の整数だけとれば十分なので、その間で探索。

桁数を取る方法は多分組み込み関数があるとは思うが、本番にググるよりも自作する方が力がつきそうなのでそうした。

コードは以下。
Submission #4245427 - AtCoder Beginner Contest 057

#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i=0;i<int(N);++i)
#define rep1(i,N) for(int i=1;i<int(N);++i)

typedef long long ll;

int cnt_digits(ll X){
	int cnt=0;
	while(X>0){
		X/=10;
		cnt++;
	}
	return cnt;
}

int main() {
	ll N;
	cin>>N;
	int ans=cnt_digits(N);
	rep1(A,1e5+1){
		if(N%A==0){
			ll B=N/A;
			int C=max(cnt_digits(A),cnt_digits(B));
			ans=min(ans,C);
		}
	}
	cout<<ans<<endl;
}

ABC051 C - Back and Forth

ABC051 C - Back and Forth

ある地点からある地点まで同じところ通らないで2往復するときにその最短経路の一つを求めろっていう問題(要約)。

問題は以下。

atcoder.jp



  • [考察]その1

スタートからゴールまでの経路を深さ優先探索(DFS)を使って列挙してその度にルートを更新していく?
また、visited行列を使って通ったか通っていないかを管理して通っていないところだけで探索をしていくイメージ。普通に計算量がエグくなりそうだし書き方もまだよくわかんねえなあって思って入力例とか見てたらそんなことしなくても簡単に一つくらいの最短経路くらい出せるなあって思って考察2へ。

  • [考察]その2

まあ少し書いてみればわかるんですが同じ経路通らないで2往復ってそんなにパターンなくて、はい。公式の解説みれば簡単にわかると思うのでリンクだけ。

https://img.atcoder.jp/abc051/editorial.pdf



コードは以下。Submission #4244495 - AtCoder Beginner Contest 051

#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i=0;i<int(N);++i)

int main() {
	int sx,sy,tx,ty,dx,dy;
	cin>>sx>>sy>>tx>>ty;
	string ans="";
	dx=abs(tx-sx);
	dy=abs(ty-sy);

	//root1
	rep(i,dy)ans+='U';
	rep(i,dx)ans+='R';

	//root2
	rep(i,dy)ans+='D';
	rep(i,dx)ans+='L';

	//root3
	ans+='L';
	rep(i,dy+1)ans+='U';
	rep(i,dx+1)ans+='R';
	ans+='D';

	//root4
	ans+='R';
	rep(i,dy+1)ans+='D';
	rep(i,dx+1)ans+='L';
	ans+='U';

	cout<<ans<<endl;
}

ABC112 C - Pyramid

ABC112 C - Pyramid

ピラミッドの最高点を決める問題。
問題は以下。

atcoder.jp


〜考え方〜
グリッドの問題をやった後だったからか、制約含めて見てみて「座標を全探索する」という発想が素直に浮かんできた。まあ本番解いてるし(ACしてないけど)他の人の感想からなんとなく予想はついてたけど、実装までスムーズにいけたので少し成長を感じられて嬉しかった。

最初提出していたコードでは、少し実装が複雑になってしまったが、解説をチラ見して、

中心座標をあらかじめ決めるとその高さが一意に定まるので、それを使って他の情報と計算が一致するかどうかを考える

という考え方の方が説明のmaxをうまく使えて素直なのでそちらに直したら一個だけあったWAが取れた。
一応最後に自分の実装も最後にちらっと載せておくのでなぜ通らないのか考えていただける方がいたらお願いしたいです笑


コードは以下。
Submission #4240237 - AtCoder Beginner Contest 112

#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i=0;i<int(N);++i)


int main() {
	int N,ansX,ansY,ansH,xt,yt,ht,Ht;
	cin>>N;
	vector<int> x(N),y(N),h(N);
	rep(i,N){
		cin>>x[i]>>y[i]>>h[i];
		if(h[i]!=0){
			xt=x[i],yt=y[i],ht=h[i];
		}
	}
	rep(X,101)rep(Y,101){
		Ht = ht+abs(xt-X)+abs(yt-Y);
		int cnt = 0;
		rep(i,N){
			if(h[i]==max(0,Ht-abs(X-x[i])-abs(Y-y[i]))){
				cnt++;
			}
		}
		if(cnt==N){
		ansX=X,ansY=Y,ansH=Ht;
		break;		
		}
	}
	cout<<ansX<<' '<<ansY<<' '<<ansH<<endl;
}

↓~失敗の実装~

Submission #4240187 - AtCoder Beginner Contest 112

#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i=0;i<int(N);++i)


int main() {
	int N,ansX,ansY,ansH,xt,yt,ht,H1,Ht;
	cin>>N;
	vector<int> x(N),y(N),h(N);
	rep(i,N){
		cin>>x[i]>>y[i]>>h[i];
		if(h[i]!=0){
			xt=x[i],yt=y[i],ht=h[i];
		}
	}
	rep(X,101)rep(Y,101){
		Ht = ht+abs(xt-X)+abs(yt-Y);
		int cnt = 0;
		rep(i,N){
			if(h[i]==0)cnt++;
			else{
				H1=h[i]+abs(x[i]-X)+abs(y[i]-Y);
				if(H1==Ht)cnt++;
			}
		}
		if(cnt==N){
			ansX=X,ansY=Y,ansH=Ht;
			break;
		}
	}
	cout<<ansX<<' '<<ansY<<' '<<ansH<<endl;
}

CODE FESTIVAL 2016 Final (Parallel) A - Where's Snuke?(char型のお勉強)

CODE FESTIVAL 2016 Final (Parallel) A - Where's Snuke?

文字列の検索の問題。
問題は以下。

atcoder.jp



〜考え方〜
入力はstringの二次元配列で受ける。
二重ループでsnukeを探し、そこの列番号をアルファベット大文字で出力し、行を数字で。

列のアルファベットはchar型の文字コードを考えて、
’A'からj文字だけずれてると考えればいける。
気をつけるのは、int + charは intになるのでそれをさらにcharに戻すこと。

char(j+'A')

行は0indexであることに注意してi+1。

char型がだんだんわかってきた。
コードは以下。
Submission #4242959 - CODE FESTIVAL 2016 Final (Parallel)

#include <bits/stdc++.h>
using namespace std;

int main() {

	int H,W;
	cin>>H>>W;
	string S[H][W];
	rep(i,H)rep(j,W)
	cin>>S[i][j];

	rep(i,H)rep(j,W){
		if(S[i][j]=="snuke"){
			cout<<char(j+'A')<<i+1<<endl;
			return 0;
		}
	}
}