paiza POH joshibato #_poh

今回、解き応えのある問題ではなかったので、多言語展開はなしです。

A (rio)

普通のシミュレーション。結果以外は小数計算であることに注意。

paizapoh6a.rb

# !/usr/bin/ruby
x=y=0.0
gets.to_i.times{
	t,s=gets.split.map(&:to_i)
	if t==1
		x+=s
	elsif t==2
		y+=s
	else
		x,y=x-s*x/(x+y),y-s*y/(x+y)
	end
}
p (100*y/(x+y)).to_i

B (kirishima)

問題文からするとシミュレーションで解くべきな気がするけど、私は満足できないので、 ダイクストラ で解いた。

paizapoh6b.cpp

# include <queue>
# include <cstdio>
# define INF 99999999
using namespace std;

typedef int Weight;
struct Edge {
  int src, dst;
  Weight weight;
  Edge(int src, int dst, Weight weight) :
    src(src), dst(dst), weight(weight) { }
};
bool operator < (const Edge &e, const Edge &f) {
  return e.weight != f.weight ? e.weight > f.weight : // !!INVERSE!!
    e.src != f.src ? e.src < f.src : e.dst < f.dst;
}
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

void shortestPath(const Graph &g, int s,
    vector<Weight> &dist, vector<int> &prev) {
  int n = g.size();
  dist.assign(n, INF); dist[s] = 0;
  prev.assign(n, -1);
  priority_queue<Edge> Q; // "e < f" <=> "e.weight > f.weight"
  for (Q.push(Edge(-2, s, 0)); !Q.empty(); ) {
    Edge e = Q.top(); Q.pop();
    if (prev[e.dst] != -1) continue;
    prev[e.dst] = e.src;
    for(auto &f:g[e.dst]) {
      if (dist[f.dst] > e.weight+f.weight) {
        dist[f.dst] = e.weight+f.weight;
        Q.push(Edge(f.src, f.dst, e.weight+f.weight));
      }
    }
  }
}

int main(){
	int N,Q;
	scanf("%d",&N);
	vector<int>v(N);
	for(int i=0;i<N;i++)scanf("%d",&v[i]);
	Graph g(N);
	for(int i=0;i<N;i++){
		int nxt=i+v[i];
		if(nxt==i||nxt<0||nxt>=N)continue;
		g[nxt].push_back(Edge(nxt,i,1));
	}
	vector<Weight> dist;
	vector<int> prev;
	shortestPath(g,N-1,dist,prev);
	for(scanf("%d",&Q);Q--;){
		int x;
		scanf("%d",&x);
		puts(x<0||x>=N||dist[x]==INF?"No":"Yes");
	}
}

C (tsubame)

簡単すぎませんか。これ、もしかして、つばめがDランク、リオがCランク、霧島がBランク相当の問題だったんだろうか。

paizapoh6c.rb

# !/usr/bin/ruby
n=gets.to_i
p n+n/10+n%10

D (matsue-ruby)

私は松江に行く予定はありませんが…
キーを昇順で取っておけば速く解けるのではないかと。
計算量はならしでO(LN)だと思われます。
最大0.09秒なので、Ruby 2.0環境では最速ではないかと？

paizapoh6d.rb

# !/usr/bin/ruby
h=Hash.new{|h,k|h[k]=[]}
gets.to_i.times{
	s=gets.strip
	h[[s,s.reverse].min]<< s
}
min_self_palindrome=nil
result1=[]
result2=[]
a=h.sort
a.each{|k,v|
	v.sort!
	i=0
	while i<v.size/2 && (v[i]!=v[v.size-i-1]||v[i]==v[i].reverse)
		result1<< v[i]
		result2<< v[v.size-i-1]
		i+=1
	end
	if i<=v.size-i-1 && v[i]==v[i].reverse
		min_self_palindrome=(min_self_palindrome&&[v[i],min_self_palindrome].min)||v[i]
	end
}
puts result1.join+(min_self_palindrome||'')+result2.reverse.join

最終コード

10/7になりました。提出期間は10/6までなので、最終コードを公開します。Ruby(空白コメント等除いて268)です。
テストケースの穴は使っていないはず。

paizapoh6d_final.rb

# !/usr/bin/ruby
# y => min_self_palindrome

h=Hash.new{|h,k|h[k]=[]}
gets;$<.sort.each{|e|s=e.chop;h[[s,s.reverse].min]<< s}
y=nil;r=[];u=[]
h.each{|k,v|l=v.size-1;i=0
(r<<v[i];u<<v[l-i];i+=1)while i<-~l/2&&v[i]==v[l-i].reverse
y=(y&&[v[i],y].min)||v[i]if i<=l-i&&v[i]==v[i].reverse}
$><<r*''+(y||'')+u.reverse*''