paiza POH moshijo #もし女


- クエストクリアできない場合は品質上げをちゃんとやったほうがいいかも？
- だいたい`進捗->進捗->品質->品質->進捗->回復->...`でいけそう。

## 御影百合絵

```rb:2.rb
#!/usr/bin/ruby
puts (s=gets)=~/help/ ? :SOS : s
```

## 春日みちる

```rb:3.rb
#!/usr/bin/ruby
p $<.reduce(0){|s,e|s+e.to_i}
```

## 園田冴絵

- 超久々にsend使った。

```rb:4.rb
#!/usr/bin/ruby
a,b,c=gets.split
p a.to_i.send(c.to_sym,b.to_i)
```

## 芦屋川雛乃

```rb:5.rb
#!/usr/bin/ruby
a=gets.split.map(&:to_i)
if gets.chomp=='decode'
	b=[]
	10.times{|i|b[a[i]]=i}
	a=b
end
puts gets.chomp.chars.map{|e|a[e.to_i]}*''
```

## 水無瀬朋

```rb:6.rb
#!/usr/bin/ruby
n=gets.to_i
a=gets.split.map(&:to_i)
b=gets.split.map(&:to_i)
b.each{|e|
	puts a.map{|f|e+f}*' '
}
```

## 桂乃梨子

```rb:7.rb
#!/usr/bin/ruby
q=gets.to_i.times.map{
	gets.split.map(&:to_i)
}
gets.to_i.times{
	c,a=gets.split.map(&:to_i)
	d=a/q[c-1][1]
	p a*q[c-1][0]-d*q[c-1][2]
}
```

## 六村リオ

```rb:8.rb
#!/usr/bin/ruby
a=gets.split.join('/')[1..-1].split('/')
st=[]
a.each{|e|
	if e=='.'
	elsif e=='..'
		st.pop
	else
		st<<e
	end
}
puts '/'+st*'/'

__END__
a,b=gets.split;puts File.expand_path b,a
#でも通る。ただし下は不可。原因不明。
#puts File.expand_path gets.split.join('/') # this is not OK
```

## 緑川つばめ

- 計算量はO(S)です。7桁が最大らしいけど、10万桁でも大丈夫な解法。

```rb:9.rb
#!/usr/bin/ruby
a=('0'+gets.chomp).chars.map(&:to_i)
r=a.size-1
carry=0
(a.size-1).downto(0){|i|
	if a[i]<9
		a[i]+=carry
		carry=0
	end
	if a[i]>=5
		r=i-1
		carry=1
	end
}
puts (a.join[0..r]+'0'*(a.size-r-1)).sub(/^0/,'')
```

## 霧島京子

- ランキング問題のため、非公開とさせていただきますm(_ _)m
- 170428: 普通の解法だとランキング外になるようになったので、公開しました。

```cpp:10.cpp
#include <iostream>
#include <string>
#include <queue>
#include <algorithm>
#define INF 999999999
using namespace std;
#define between(a,n,b) ((a)<=(n)&&(n)<=(b))
 
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 H,W,N,maxc=0;
	cin>>H>>W>>N;
	vector<string>v(H);
	for(int i=0;i<H;i++){
		cin>>v[i];
	}
	Graph g(H*W);
	for(int i=0;i<H;i++)for(int j=0;j<W;j++){
		if(v[i][j]=='#')continue;
		int x=i*W+j,y;
		if(i<H-1 && v[i+1][j]!='#'){
			int cs=between('A',v[i][j],'Z') ? 100 : between('a',v[i][j],'z') ? 0 : 1;
			int cd=between('A',v[i+1][j],'Z') ? 100 : between('a',v[i+1][j],'z') ? 0 : 1;
			y=(i+1)*W+j;
			g[x].push_back(Edge(x,y,cd));
			g[y].push_back(Edge(y,x,cs));
		}
		if(j<W-1 && v[i][j+1]!='#'){
			int cs=between('A',v[i][j],'Z') ? 100 : between('a',v[i][j],'z') ? 0 : 1;
			int cd=between('A',v[i][j+1],'Z') ? 100 : between('a',v[i][j+1],'z') ? 0 : 1;
			y=i*W+j+1;
			g[x].push_back(Edge(x,y,cd));
			g[y].push_back(Edge(y,x,cs));
		}
	}
	{
		int sx,sy,gx,gy;
		cin>>sx>>sy>>gx>>gy;
		vector<Weight> dist;
		vector<int> prev;
		shortestPath(g,(sy-1)*W+sx-1,dist,prev);
		int k=(gy-1)*W+gx-1;
		int c=dist[k];
		vector<char>v;
		for(;prev[k]>=0;k=prev[k]){
			if(k-prev[k]==W)v.push_back('D');
			if(k-prev[k]==-W)v.push_back('U');
			if(k-prev[k]==1)v.push_back('R');
			if(k-prev[k]==-1)v.push_back('L');
		}
		reverse(v.begin(),v.end());
		for(auto &e:v)cout<<e<<endl;
		//cout<<c<<endl;
	}
}
```