異能な僕らと異常な世界 #paiza #poh

赤羽 (1) / 大塚 (2) は4択なので割愛致します

## 田端 (3)

```ruby
puts gets.to_i>gets.to_i ? :Yes : :No
```

## 四谷 (4)

N==0な入力はないっぽいです

```awk
$0=$1*100
```

## 新橋 (5)

```ruby
puts gets[0]=='a' ? :Yes : :No
```

## 高田馬場 (6)

```ruby
prepositions = %w(at by for from in of on to)
gets
puts gets.split.each_with_index.all?{|e,i|
    if !prepositions.include?(e.downcase)
        e[0] == e[0].upcase
    elsif i==0
        e == e.capitalize
    else
        e == e.downcase
    end
} ? :Yes : :No
```

## 五反田 (7)

```ruby
_,m,a,*x = `dd`.split.map &:to_i
s=0
x.each{|e|
    if e>a
        m+=s*e
        s=0
    else
        t,m=m.divmod e
        s+=t
    end
}
p s*x[-1]+m
```

## 池袋 (8)

```ruby
n,a,b = `dd`.split.map &:to_i
1.upto(n){|i|
    if i%a.lcm(b) == 0
        puts 'paizaprogramming'
    elsif i%a == 0
        puts 'paiza'
    elsif i%b == 0
        puts 'programming'
    else
        p i
    end
}
```

## 新宿 (9)

```ruby
h = {}
1.upto(gets.to_i){|i|h[gets.chomp] = i}
gets.to_i.times{p h[gets.chomp]}
```

## 秋葉原 (10)

```ruby
D=[[0,1],[1,0],[1,1],[1,2],[2,1]]
H,W=gets.split.map &:to_i
a=H.times.map{gets.chomp}
r=0
(0..H-3).each{|h|(0..W-3).each{|w|r+=1 if D.all?{|dy,dx|a[h+dy][w+dx]=='#'}}}
p r
```

## 品川 (11)

うん…? `N<=200000`? なんですと?
[エンジニアでも恋がしたい!](https://paiza.jp/poh/enkoi) 3問目…あれ、あれってBランク相当でしたっけ、Aだった気がするんですが、気のせいだったかな…

~~それとも私が昔AtCoderと比べるとpaizaのランクは保証されるものが何とか言ったせいで変更になったのかな…~~

```cpp
#pragma GCC optimize("O3")
#pragma GCC target("avx")

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
using namespace std;
struct SAComp{
	const int h,*g;
	SAComp(const int h, const int* g) : h(h), g(g) {}
	bool operator()(const int a, const int b){
		return a == b ? false : g[a] != g[b] ? g[a] < g[b] : g[a+h] < g[b+h];
	}
};
vector<int> buildSA(const string &t){
	int n=t.size();
	int g[n],b[n];
	vector<int>suff(n);
	for(int i=0;i<n;i++)suff[i]=i,g[i]=t[i];
	b[0]=b[n-1]=0;
	sort(suff.begin(),suff.end(),SAComp(0,g));
	for(int h=1;b[n-1]!=n-1;h<<=1){
		SAComp comp(h,g);
		sort(suff.begin(),suff.end(),comp);
		for(int i=0;i<n-1;i++)b[i+1]=b[i]+comp(suff[i],suff[i+1]);
		for(int i=0;i<n;i++)g[suff[i]]=b[i];
	}
	return suff;
}
int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);

	string s,q;
	cin>>s>>s;
	q=s;
	s+=s;
	s+='$';
	int n=s.size();
	vector<int>suff=buildSA(s);
	vector<pair<char,int>>sorted(n);
	for(int i=0;i<n;i++)sorted[i]={s[(suff[i]-1+n)%n],i};
	sort(sorted.begin(),sorted.end());

	{
		int start=0,stop=n,idx=q.size()-1;
		for(;idx>=0;idx--){
			pair<char,int> ql={q[idx],start},qr={q[idx],stop};
			start=lower_bound(sorted.begin(),sorted.end(),ql)-sorted.begin();
			stop=lower_bound(sorted.begin(),sorted.end(),qr)-sorted.begin();
			if(start==stop)break;
		}
		/*if(idx<0)*/{
			vector<int>v;
			for(;start<stop;start++)v.push_back(suff[start]);
			sort(v.begin(),v.end());
			printf("%d\n",v[1]);
		}
	}
}
```

## 東京 (12)

```ruby
D=[[0,-1],[0,1],[-1,0],[1,0]]
H,W=gets.split.map &:to_i
a=H.times.map{gets.chomp}
a << '#'*W
x,y=gets.split.map{|e|e.to_i-1}
a[y][x]='.'
q=[[H,0]]
visited={q[0]=>1}
while !q.empty?
  cy,cx=q.shift
  D.each{|dy,dx|
    ny=cy+dy
    nx=cx+dx
    next if ny<0||H<ny
    next if nx<0||W<=nx
    if a[ny][nx]=='#' && !visited[[ny,nx]]
      visited[[ny,nx]] = 1
      q << [ny,nx]
    end
  }
end
H.times{|h|W.times{|w|a[h][w]='.' if !visited.include?([h,w])}}
a.pop
a.each{|e|puts e}
```

## 渋谷 (13)

まずは無を出力するところから行きましょうか…

```bash
read
dd
```

## 御茶ノ水 (14)

ふええ…CSSわからないよぅ…

```css
.container{
  position: relative;
  width: 468px;
  height: 200px;
  background: transparent url(https://ppg.paiza.jp/html_css/inou_html_css_1/bg.png) no-repeat 0 0;
  background-size: cover;
}
.logo {
  width:60px;
  height:60px;
  position: absolute;
  background: #444444;
  border-radius: 50%;
  z-index: 1;
}
.logo:nth-of-type(1){
  top: 70px;
  left: 47px;
}
.logo:nth-of-type(2){
  top: 70px;
  left: 203px;
}
.logo:nth-of-type(3){
  top: 70px;
  left: 359px;
}
.container::before {
  display: block;
  content:"";
  background: transparent url(https://ppg.paiza.jp/html_css/inou_html_css_1/laurel-wreath_D.png) no-repeat 0 0;
  background-size: cover;
  width:468px;
  height:200px;
  position: absolute;
  z-index: 2;
}
```

## 上野 (15)

```css
.container{
  position: relative;
  width: 468px;
  height: 200px;
  background: transparent url(https://ppg.paiza.jp/html_css/inou_html_css_2/bg.png) no-repeat 0 0;
  background-size: cover;
}
.logo {
  width:60px;
  height:60px;
  position: absolute;
  border-radius: 50%;
  z-index: 1;
}
.logo:nth-of-type(1){
  top: 70px;
  left: 71px;
  background: #444444;
}
.logo:nth-of-type(2){
  top: 70px;
  left: 203px;
  background: #7E5A04;
}
.logo:nth-of-type(3){
  top: 70px;
  left: 335px;
  background: #532E02;
}
.container::before {
  display: block;
  content:"";
  background: transparent url(https://ppg.paiza.jp/html_css/inou_html_css_2/laurel-wreath_C.png) no-repeat 0 0;
  background-size: cover;
  width:468px;
  height:200px;
  position: absolute;
  z-index: 2;
}
```

----

## 230622追記

渋谷 (13)ですが、[4/12に2位を取った](https://twitter.com/cielavenir/status/1645834700051873793)あと、順位が下がるかと思ったのですが下がらず。おそらくソースを貼ることは叶わないので、概要のみ残します。

方針は以下のとおりです:

1. 点群に対し凸包を算出し、その中の1点を選ぶ、この点をクラスタとする
2. 点群からクラスタの中心に最も近い点を選び、現在のクラスタと合わせての最小包含円を求める
3. もし最小包含円の半径が閾値以下なら最小包含円の中心をクラスタの中心とし、閾値を超えるまで繰り返す
4. (閾値を超えたら、クラスタを点群から削除し1に戻る)

- 凸包はSpaghetti Source https://web.archive.org/web/20190324130301/http://www.prefield.com/algorithm/geometry/convex_hull.html
- 最小包含円は@stakemura氏がCodeIQ Magazineに寄稿した「キュラゲの最小包含円を求めよう」問題の解説記事にあったアルゴリズムを使っています(実装は https://atcoder.jp/contests/abc151/submissions/40534581 )
   - 私の古い答案のやつは3点が同一直線上にあると正しい包含円を算出しない問題があったため、近似解版を使っていますが、(誤差が心配ですが)うまいこと通るようです。