プログラミング問題をやってみた (paiza×Qiitaコラボキャンペーン、全25問)

全25問の解答例です.

Dランク

Bash縛りを設けます.

N倍の文字列 (スキルチェック通し番号44)

#!/usr/bin/ruby
puts '*'*gets.to_i

#!/bin/sh
read n
for i in `seq ${n}`; do printf '*'; done

Eメールアドレス (58)

#!/usr/bin/ruby
puts gets.chomp+'@'+gets.chomp

#!/bin/sh
read s
printf "${s}"
printf "@"
read s
echo "${s}"

足し算

#!/usr/bin/ruby
p gets.split.map(&:to_i).reduce(:+)

#!/bin/sh
read line
a=($line)
expr ${a[0]} + ${a[1]}

一番小さい値

#!/usr/bin/ruby
p $<.map(&:to_i).min

#!/bin/sh
sort -n|head -1

文字の一致

#!/usr/bin/ruby
puts gets==gets ? :OK : :NG

#!/bin/sh
read a
read b
if [ "${a}" = "${b}" ]; then
echo OK
else
echo NG
fi

Cランク

残り物の量 (73)

#!/usr/bin/ruby
m,a,b=gets.split.map(&:to_f)
p m*(100-a)*(100-b)/10000

Fizz Buzz

Ruby以外は https://qiita.com/cielavenir/items/9ab4c0731ae5a0ad3779 を御覧ください

#!/usr/bin/ruby
puts (1..gets.to_i).map{|i|
	i%15==0 ? 'Fizz Buzz' : i%3==0 ? 'Fizz' : i%5==0 ? 'Buzz' : i
}

みかんの仕分け

#!/usr/bin/ruby
n,m,*a=ARGF.read.split.map &:to_i
puts a.map{|e|
	if e<n
		n
	else
		[(e+n-1)/n*n,e/n*n].min_by{|x|(x-e).abs}
	end
}

野球の審判 (139)

#!/usr/bin/ruby
s=b=0
gets.to_i.times{
	x=gets.chomp
	puts x=='strike' ? ((s+=1)>2 ? :out! : :strike!) : ((b+=1)>3 ? :fourball! : :ball!)
}

宝くじ (108)

#!/usr/bin/ruby
b=gets.to_i
gets.to_i.times{
	n=gets.to_i
	puts n==b ? :first : n-1==b||n+1==b ? :adjacent : n%10000==b%10000 ? :second : n%1000==b%1000 ? :third : :blank
}

Bランク

名刺バインダー管理 (35)

#!/usr/bin/ruby
n,m=gets.split.map(&:to_i)
d,r=(m-1).divmod(2*n)
p 2*n*d+2*n-r

長テーブルのうなぎ屋 (12)

#!/usr/bin/ruby
n,m=gets.split.map(&:to_i)
x=Array.new(n)
m.times{
	a,b=gets.split.map(&:to_i)
	b-=1
	if a.times.none?{|i|x[(b+i)%n]}
		a.times{|i|x[(b+i)%n]=true}
	end
}
p x.count{|e|e}

みんなでしりとり (221)

#!/usr/bin/ruby
n,k,m=gets.split.map &:to_i
h={}
k.times{h[gets.chomp]=1}
g={}
r=[*1..n]
i=0
prev=nil
m.times{
	s=gets.chomp
	if !h[s]||(prev&&s[0]!=prev)||g[s]||s[-1]=='z'
		r.delete_at(i)
		prev=nil
	else
		g[s]=1
		i+=1
		prev=s[-1]
	end
	i=0 if i==r.size
}
p r.size
p *r

神経衰弱

#!/usr/bin/ruby
H,W,N=gets.split.map &:to_i
T=H.times.map{gets.split.map &:to_i}
R=[0]*N
r=0
gets.to_i.times{
	a,b,c,d=gets.split.map{|e|e.to_i-1}
	if T[a][b] == T[c][d]
		R[r]+=2
	else
		r=(r+1)%N
	end
}
p *R

3Dプリンタ (52)

#!/usr/bin/ruby
a=[]
x,y,z=gets.split.map(&:to_i)
z.times{
	_=['.']*y
	x.times{
		s=gets.chomp
		y.times{|i|_[i]='#'if s[i,1]=='#'}
	}
	gets
	a << _*''
}
puts a.reverse

Aランク

お菓子の詰め合わせ (335)

#!/usr/bin/ruby
n,x,*a=ARGF.read.split.map &:to_i
p x-(1 << n).times.map{|i|
	bits=0
	s=0
	n.times{|j|bits+=i[j];s+=a[j] if i[j]>0}
	[bits,s]
}.filter{|bits,s|
	s<=x
}.max[1]

じゃんけんの手の出し方

#!/usr/bin/ruby
T={'G'=>5,'C'=>0,'P'=>2}
N,M=gets.split.map &:to_i
a=[0]+[-1]*M
gets.chomp.chars{|c|
	b=3.times.map{a.dup}
	[0,2,5].each_with_index{|e,j|
		M.downto(e){|i|
			b[j][i]=[b[j][i],b[j][i-e]+(e==T[c] ? 1 : 0)].max if b[j][i-e]>=0
		}
	}
	a=b.transpose.map(&:max)
}
p a[M]

ハノイの塔

#include <cstdio>
#include <cstdlib>
#include <vector>
std::vector<std::vector<int> >v(3);
long long t;

void output(){
	for(int i=0;i<3;i++){
		if(v[i].empty())puts("-");
		else for(int j=0;j<v[i].size();j++)printf(j<v[i].size()-1?"%d ":"%d\n",v[i][j]);
	}
	exit(0);
}
void hanoi(long long n,int a,int b,int c){
	if(!n)return;
	if(t>=(1LL<<n)-1){
		int idx=v[a].size()-n;
		for(int i=0;i<n;i++){
			v[b].push_back(v[a][idx]);
			v[a].erase(v[a].begin()+idx);
		}
		t-=(1LL<<n)-1;
		if(!t)output();
	}else{
		hanoi(n-1,a,c,b);
		v[b].push_back(*v[a].rbegin());
		v[a].pop_back();
		t--;
		if(!t)output();
		hanoi(n-1,c,b,a);
	}
}
int main(){
	int n,i;scanf("%d%lld",&n,&t);
	for(i=n;i;i--)v[0].push_back(i);
	//output();
	hanoi(n,0,2,1);
}

山折り谷折り

yhpgなかったら厳しかったやつだと思います…

#!/usr/bin/env ruby
#http://qiita.com/Nabetani/items/373105e7fafd12f5e9fd
#http://nabetani.sakura.ne.jp/hena/ord18mafovafo/
T={'L'=>'RVF','J'=>'FVR','Z'=>'FmRVF','U'=>'RVFVR','S'=>'FVRmF'}
STDOUT.sync=true
while gets
    puts ('J'*$_.to_i).chars.reduce('F'){|s,e|
        s.chars.map{|c|c=='F' ? T[e] : c=='R' ? T[e].tr('FRmV','RFVm').reverse : c}*''
    }.tr('FR','').tr('Vm','01')
end

本の整理

#!/usr/bin/ruby
n,*a=`dd`.split.map{|e|e.to_i-1}
r=[]
0.upto(n){|i|r[a[i]]=i}
q=0
p 0.upto(n).count{|i|
    a[i]!=i&&(r[i],r[a[i]],a[i],a[r[a[i]]],q=r[a[i]],r[i],a[r[a[i]]],a[i])
}

Sランク

村人の友好関係 (278)

#include <vector>
#include <algorithm>
#include <map>
#include <cstdio>
using namespace std;
class union_find{
	int *parent,n;
public:
	int root(int a){return parent[a]==a?a:(parent[a]=root(parent[a]));}
	union_find(int _n){n=_n;parent=new int[n+1];for(int i=1;i<=n;i++)parent[i]=i;}
	~union_find(){delete []parent;}
	int same(int a,int b){return root(a)==root(b);}
	int unite(int a,int b){
		int x=root(a),y=root(b);//if(x==y)return 0;
		parent[x]=y;
		return 1;
	}
};
int main(){
	int n,m,q;
	scanf("%d%d%d",&n,&m,&q);
	vector<vector<long long> >relationship(n);
	for(int i=0;i<n;i++)relationship[i].resize(n);
#if 0
	for(int i=0;i<m;i++){
		int a,b;
		long long f;
		scanf("%d%d%lld",&a,&b,&f);a--;b--;
		relationship[a][b]=relationship[b][a]=f;
	}
#else
	//kruskal tree
	union_find uf(n);
	vector<pair<long long,pair<int,int>>>relationship1;
	for(int i=0;i<m;i++){
		int a,b;
		long long f;
		scanf("%d%d%lld",&a,&b,&f);
		relationship1.emplace_back(make_pair(-f,make_pair(a,b)));
	}
	sort(relationship1.begin(),relationship1.end());
	for(int i=0;i<m;i++){
		long long f=relationship1[i].first;
		int a=relationship1[i].second.first;
		int b=relationship1[i].second.second;
		if(!uf.same(a,b)){
			uf.unite(a,b);
			relationship[a-1][b-1]=relationship[b-1][a-1]=-f;
		}
	}
#endif
	vector<int>people(n);
	map<long long,int>scores;
	for(int i=0;i<q;i++){
		char o[2];
		int q;
		scanf("%s%d",o,&q);q--;
		for(int j=0;j<n;j++){
			long long v=relationship[q][j];
			if(!v)continue;
			if((o[0]=='+') ^ (!!people[j])){
				++scores[v];
			}else{
				auto it=scores.find(v);
				if(it!=scores.end()&&!--it->second)scores.erase(it);
			}
		}
		people[q]=o[0]=='+';
		printf("%lld\n",scores.empty()?0:scores.rbegin()->first);
		// for(;scores.size()>2000;)scores.erase(scores.begin());
	}
}

島探し (6)

※本問はSランク相当の中で最も多言語への移植が楽です(あとは察してください)

import java.util.*;
import java.util.AbstractMap.SimpleEntry;
class Main{
	static int[][] T;
	static int n,m;
	static void fill(int _x,int _y){
		List<SimpleEntry<Integer,Integer>> q=new LinkedList<>();
		q.add(new SimpleEntry<Integer,Integer>(_x,_y));
		for(;!q.isEmpty();){
			SimpleEntry<Integer,Integer> p=q.get(0);q.remove(0);
			int x=p.getKey(),y=p.getValue();
			if(0<=x&&x<n&&0<=y&&y<m&&T[y][x]!=0){
				T[y][x]=0;
				q.add(new SimpleEntry<Integer,Integer>(x-1,y));
				q.add(new SimpleEntry<Integer,Integer>(x+1,y));
				q.add(new SimpleEntry<Integer,Integer>(x,y-1));
				q.add(new SimpleEntry<Integer,Integer>(x,y+1));
			}
		}
	}
	public static void main(String[]z){
		Scanner cin=new Scanner(System.in);
		n=cin.nextInt();
		m=cin.nextInt();
		T=new int[m][n];
		int i,j,r=0;
		for(i=0;i<m;i++){
			for(j=0;j<n;j++)T[i][j]=cin.nextInt();
		}
		for(i=0;i<m;i++)for(j=0;j<n;j++)if(T[i][j]!=0){r++;fill(j,i);}
		System.out.println(r);
	}
}

mod7占い

#!/usr/bin/ruby
a=Hash.new(0)
gets.to_i.times{a[gets.to_i%7]+=1}
r=0
0.step(6){|i|
	(i+1).step(6){|j|
		(j+1).step(6){|k|
			r+=a[i]*a[j]*a[k] if (i+j+k)%7==0
		}
	}
}
0.step(6){|i|
	(i+1).step(6){|j|
		r+=a[i]*(a[j]*(a[j]-1)/2) if (i+j*2)%7==0
		r+=(a[i]*(a[i]-1)/2)*a[j] if (i*2+j)%7==0
	}
}
0.step(6){|i|
	r+=a[i]*(a[i]-1)*(a[i]-2)/6 if (i*3)%7==0
}
p r

文字列収集

#!/usr/bin/ruby
require 'backports' if RUBY_VERSION<'2.0'
n,m=gets.split.map &:to_i
a=n.times.map{
    x,y=gets.split
    y=y.to_i
    [x,y]
}.sort
s=[0]
a.map!{|x,y|
    s << s[-1]+y
    x
}
m.times{
    x=gets.chomp
    idx1=(0...n).bsearch{|i|x<=a[i]}||n
    idx2=(0...n).bsearch{|i|x<=a[i]&&!a[i].start_with?(x)}||n
    p s[idx2]-s[idx1]
}

十億連勝

#!/usr/bin/ruby
$memo={}
def dfs(depth,passing,current_streak)
	if depth==N
		return passing
	end
	$memo[[depth,passing,current_streak]]||=->{
	r=0
	if current_streak+A[depth]<=X
		#全勝してさしつかえない
		r=dfs(depth+1,passing==1||current_streak+A[depth]==X ? 1 : 0,current_streak+A[depth])
	else
		#わざと負ける
		r=dfs(depth+1,1,0)
	end
	#途中で負ける
	(r+[X-current_streak,A[depth]].min*dfs(depth+1,passing,0))%10**9
	}.()
end
N,X,*A=`dd`.split.map &:to_i
p dfs 0,0,0