電脳少女プログラミング2088

今回久々にマラソンマッチがない回のようで…。

## 1. (C) ネオン街のクラブ

【お断り】本記事は、投稿キャンペーンを見る前から執筆開始されたため、ネオン街のクラブは対象としない旨を見る前に記載されておりました(編集履歴からは削除できないため)。

```rb
#!/usr/bin/ruby
gets;p gets.chomp.chars.uniq.size
```

うわーこれ気づいたけど後の祭りじゃねえか…。(28bytes)

```rb
p`tail +2`.chars.uniq.size-1
```

てかさらに27bytesが出てるみたいですね?あーそうかsed 1dでしたか草草草

```rb
p`sed 1d`.chars.uniq.size-1
```

## 2. (C) 二人が通った教室

```sql
SELECT id, talk FROM memory ORDER BY id ASC LIMIT 10;
```

## 3. (C) 廃マンションの一室

は？普通に厳しいのだが…

https://github.com/cielavenir/procon/blob/master/aizu/tyama_aizu0306.rb を流用。

```rb
#!/usr/bin/ruby
class Integer
	def to_tern
		q=(self+1)/3
		r=(self+1)%3
		(q!=0 ? q.to_tern : "")+"201"[r]
	end
end
puts gets.to_i.to_tern
```

ちなみに https://github.com/cielavenir/procon/blob/master/aizu/tyama_aizu0306.c もありますが、C(++)は負数の除算が0側に丸められるためそのまま流用とはいかないようです。[^1]

## 4. (B) 打ち捨てられた図書館

```sql
SELECT memory.id, memory.talk, battle.result FROM log
  INNER JOIN memory ON memory.id = log.memory_id
  INNER JOIN battle ON battle.id = log.battle_id
  WHERE '2085-08-01' <= log.created_at AND log.created_at <= '2087-10-20';
```

## 5. (E) 街外れの戦場跡

4択のため省略いたします

## 6. (D) ネオン街の裏路地

```rb
#!/usr/bin/ruby
gets;p$<.map(&:to_i).max
```

## 7. (B) 一番通りの繁華街

```rb
#!/usr/bin/ruby
n=gets.to_i
m=n.times.map{gets.chomp}
r=0
(0..n-2).each{|y1|(0..n-2).each{|x1|(y1+1..n-1).each{|y2|
    # (x1+1..n-1).each{|x2|
    # next if x2-x1 != y2-y1  # oops, square not rectangle
    x2 = y2-y1+x1
    next if x2>=n
    r+=1 if m[y1][x1] == '.' && m[y1][x2] == '.' && m[y2][x1] == '.' && m[y2][x2] == '.'
    # }
}}}
p r
```

## 8. (S) 思い出の屋上

### 新

なんでこう、全部のマス目に対して条件調べないといけないとか思ってたんだろうか…。

なお、この解法であれば、与制約条件だと、二分探索しなくても一応TLEにならないようです、それでも既存の縄張りが極端に偏っている場合は3倍ほど時間がかかるようですが…。

```rb
#!/usr/bin/ruby
#coding:utf-8
H,W,N=gets.split.map &:to_i
A=N.times.map{gets.split.map &:to_i}
p (0..H+W).bsearch{|i|(1..H).all?{|h|(1..W).all?{|w|A.any?{|r,c,s|(r-h).abs+(c-w).abs<=s+i}}}}-1
#p (0..1/0.0).find{|i|(1..H).all?{|h|(1..W).all?{|w|A.any?{|r,c,s|(r-h).abs+(c-w).abs<=s+i}}}}-1
#自分の大きさをiとし、0...H/0...Wのすべてで重なる(`(r-h).abs+(c-w).abs<=s+i`)場合失敗、その-1が成功の最大
```

ところで二分探索版はこの入力(与制約よりも大きい)も余裕で耐えれるみたいです。

```
1000 1000 1
1 1 0
```

### 旧

下手に全探索かけると容易にTLEしてしまう…。

[250124追記] てかこれ嘘解法だわ…。この入力でTLEになる(手元で16.5秒、なおRubyのTLは16.0秒[^2])。

```
200 200 1
1 1 0
```

こっちはまあ間に合うが。

```
200 200 4
1 1 0
1 200 0
200 1 0
200 200 0
```

```rb
#!/usr/bin/ruby
#coding:utf-8
def chk(h,w)
    h<0||H<=h || w<0||W<=w || !M[h][w]
end
def get_points(h,w,d)
    # サイズdの縁のマス目を取得
    return [[h,w]] if d==0
    r=[]
    y=h+d
    x=w
    d.times{r.push([y,x]);y-=1;x+=1}
    d.times{r.push([y,x]);y-=1;x-=1}
    d.times{r.push([y,x]);y+=1;x-=1}
    d.times{r.push([y,x]);y+=1;x+=1}
    r
end
def solve(h,w,x)
    # 探索失敗した最小-1 == 探索成功した最大
    (x+1..1/0.0).find{|d|
        get_points(h,w,d).any?{|r,c|!chk(r,c)}
    }-1
end
H,W,N=gets.split.map &:to_i
# マス目
M=H.times.map{[false]*W}
N.times{
    h,w,s=gets.split.map &:to_i
    h-=1
    w-=1
    (0..s).each{|d|
        # マス目を埋める
        get_points(h,w,d).each{|r,c|0<=r&&r<H && 0<=c&&c<W && M[r][c]=true}
    }
}
r=-1
H.times{|h|
    # 行が変わったら最小サイズに戻す
    x=-1
    # その行での最大サイズより小さいサイズは探索しない
    # ただし列を変えるときに1減らす
    W.times{|w|r=[r,x=solve(h,w,[x-1,-1].max)].max}
}
p r
```

## 9. (C) 会員制ジム

```sql
SELECT memory.id, memory.talk FROM memory
  INNER JOIN category ON category.id = memory.category_id
  WHERE memory.importance >= 3 AND category.name = '悲しみ';
```

## 10. (C) 自然の残る公園

```rb
#!/usr/bin/ruby
n,a,b=gets.split.map &:to_i
p (1..n).min_by{
    x,y=gets.split.map &:to_i
    Math.hypot(x-a,y-b)
}
```

## 11. (A) 新都心のハイウェイ

```rb
#!/usr/bin/ruby
H,W=gets.split.map &:to_i
ay=ax=by=bx=nil
M=H.times.map{|y|
    s=gets.chomp.chars
    x=s.index('A')
    if x;ay=y;ax=x;end
    x=s.index('B')
    if x;by=y;bx=x;end
    s
}
[[-1,0],[0,-1],[1,0],[0,1]].each{|dy,dx|
    ny=by;nx=bx
    while 0<=ny&&ny<H && 0<=nx&&nx<W && M[ny][nx]!='#'
        M[ny][nx]='B';ny+=dy;nx+=dx
    end
}
m={[ay,ax]=>0}
q=[[ay,ax]]
while !q.empty?
    y,x=q.shift
    if M[y][x]=='B'
        p m[[y,x]];exit
    end
    [[-1,0],[0,-1],[1,0],[0,1]].each{|dy,dx|
        ny=y+dy;nx=x+dx
        if 0<=ny&&ny<H && 0<=nx&&nx<W && M[ny][nx]!='#' && !m[[ny,nx]]
            m[[ny,nx]]=m[[y,x]]+1;q.push([ny,nx])
        end
    }
end
p -1
```

## 12. (D) カジノ

```rb
#!/usr/bin/ruby
p [1,5,10].zip($<.map &:to_i).map{|x,y|x*y}.sum
```

## 13. (D) 郊外のスラム街

```rb
#!/usr/bin/ruby
p gets.to_i/2+100
```

## 14. (A) 巨大コーポの最上階

2025/1/22 深夜に問題文が修正されたようです。

それでも問題がわかりにくいですが…

戦争で死んだ親友はレベッカですがその死をいたんでいるのはアラン(別人)、 **つまりlog.person_idでJOINされたpersonは重要度5でないので直接のWHERE抽出はできません。**

**「エンジニア騎士とクエリの魔女」のElementCompatibilityテーブルはメインクエリにJOINされないのですが、今回のpersonテーブルはメインクエリにJOINされるため混乱しやすくなっています。** 注意です。

```sql
SELECT memory.id, memory.talk, person.name, battle.created_at FROM log
  JOIN memory ON memory.id = log.memory_id
  JOIN battle ON battle.person_id = log.person_id
  JOIN person ON person.id = log.person_id
  WHERE battle.created_at IN (SELECT deleted_at FROM person WHERE importance = 5);
```

## 15. (D) データセンター

```sql
SELECT id, name FROM person;
```

## 16. (B) ギャングのアジト

```rb
#!/usr/bin/ruby
puts (1..gets.to_i).all?{s=gets.chomp;s==s.reverse} ? :Yes : :No
```

[^1]: paizaの解説記事って基本Pythonだから気づいていないだけという可能性はあるが。
[^2]: https://paiza.jp/guide/language