今回、解き応えのある問題ではなかったので、多言語展開はなしです。
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*''