初恋プログラミング研究会　〜海に行こうよ〜

4/20に公開されました

## 出会いは桜の下で

選択問題のため省略いたします

## 帰り道に交わした約束

どういうことかわからんのだが、コード例にある`i > S.length`を`i >= S.length`に変えてほしいのかな?
でも普通はこうよな?

```rb
s=gets.chomp*2
$><<s[s.index('SUNSET')+6,3]
```

## 海に広がる特別な想い

…ここでこんな問題ってどういうこと…
まあ配列使えますかって話なのかな…

```rb
A=0,1;(2..gets.to_i).map{A<<A[-2]+A[-1]};p A[-1]
```

## 2月14日に貰える何か

本記事の本題。

なんですが。なんだろう、すんげー見覚えあるんだけど。

[コードレビューBINGOの8番目](https://qiita.com/cielavenir/items/f3444d01e624065189b7#8)ね。[^1]

んで、今回もビットで行きたいんだけど、今回は状態が2つあるので、パターン辞書を1ビットで持つか2ビットで持つかで結構変わる。2ビットのほうが実装は楽だけど辞書が大きくなるのでバイト数が縮みにくくなる。なお2ビットの場合でも50ビットすなわち`1<<53`未満なので、double型に誤差なく収めることはできる。

C++/Perl/Rustが2ビット、他は1ビットの実装です。

### Perl

strtollが使えなかったためstrtolを使っていて、LP64環境専用です(macOS/Linuxは可、Windowsは不可)

### C#

C#の基数変換は任意の基数が指定できないため、パターン辞書を1ビットで持つ方法しか通りません。

### JavaScript

ビットシフトを行うと32ビットに固定されるのでこれも1ビットで持つ方法しか通りません。

## 答案

ランキングがPython/C#/C++/Ruby/JavaScript/Perl/Java/PHPの順番なのでそれに習います。

ランキング対象外なんだけどコードレビューBINGOの関係でRustも載せとく。

```py
import re
B=[17043521,1118480]+sum(([31<<i*5,1082401<<i]for i in range(5)),[])
A=open(0).read().replace("\n","")
print(next((x for x in'OX'if any(int(re.sub('.',lambda z:'%d'%(z[0]==x),A),2)&b==b for b in B)),'D'))
```

```csharp
using System;
using System.Collections.Generic;
using System.Linq;
class K{public static void Main(){
List<int> b=new List<int>{17043521,1118480};
for(int i=0;i<5;i++){b.Add(31<<i*5);b.Add(1082401<<i);}
string A=Console.In.ReadToEnd().Replace("\n","").Replace('.','0');
int r=2;
for(int i=0;i<2;i++)if(b.Any(e=>(Convert.ToInt32(A.Replace('O',(char)(49-i)).Replace('X',(char)(48+i)),2)&e)==e))r=i;
Console.WriteLine("OXD"[r]);
}}
```

```cpp
#import<iostream>
#import<string>
#import<vector>
#import<algorithm>
#import<regex>
using namespace std;
int main(){
vector<long long>v={281543712968705LL,1103823438080LL};
for(int i=0;i<5;i++){v.insert(v.end(),{341LL<<i*10,1100586419201LL<<i*2});}
istreambuf_iterator<char>B(cin),E;
string s(B,E);s=regex_replace(s,regex("\n"),"");
transform(s.begin(),s.end(),s.begin(),[](char c){return c=='.'?'0':c=='O'?'1':'2';});
long long a=stoll(s,nullptr,4);
int r=2;
for(int i=0;i<2;i++)if(any_of(v.begin(),v.end(),[&](long long e){return((a>>i)&e)==e;}))r=i;
cout<<"OXD"[r]<<endl;}
```

```rb
B=[17043521,1118480]+(0..4).flat_map{[31<<_1*5,1082401<<_1]}
A=ARGF.read
puts [?O,?X].find{|e|B.any?{|b|A.gsub(/./m){_1=="\n"?"":e==_1 ??1:?0}.to_i(2)&b==b}}||'D'
```

```js
B=[17043521,1118480]
for(i=0;i<5;i++)B.push(31<<i*5,1082401<<i)
A=require('fs').readFileSync(0)+''
r='D'
for(x of'OX')if(B.some(b=>(parseInt(A.replaceAll(/./sg,e=>e=='\n'?'':+(e==x)),2)&b)==b))r=x
console.log(r)
```

```perl
use POSIX;
@b=(281543712968705,1103823438080);
for($i=0;$i<5;$i++){push(@b,341<<$i*10,1100586419201<<$i*2);}
local$/;$a=POSIX::strtol(<>=~tr/.OX\n/012/dr,4);
$r=2;
for($i=0;$i<2;$i++){$r=$i if(grep{(($a>>$i)&$_)==$_}@b);}
print substr('OXD',$r,1);
```

```java
import java.util.*;
interface Main{static void main(String[]z){
ArrayList<Long> b=new ArrayList<>(Arrays.asList(new Long[]{17043521L,1118480L}));
for(int i=0;i<5;i++){b.add(31L<<i*5);b.add(1082401L<<i);}
Scanner x=new Scanner(System.in).useDelimiter("\\Z");
String a=x.next().replace("\n","").replace(".","0");
int r=2;
for(int i=0;i<2;i++){int j=i;if(b.stream().anyMatch(e->(Long.valueOf(a.replace('O',(char)(49-j)).replace('X',(char)(48+j)),2)&e)==e))r=j;}
System.out.println("OXD".charAt(r));
}}
```

```php
<?php
$b=[17043521,1118480];
for($i=0;$i<5;$i++)array_push($b,31<<$i*5,1082401<<$i);
$a=stream_get_contents(STDIN);
$r="D";
foreach(["O","X"]as$x)if(array_filter($b,fn($e)=>(intval(preg_replace_callback("/./s",fn($z)=>$z[0]=="\n"?"":+($z[0]==$x),$a),2)&$e)==$e))$r=$x;
echo $r;
```

```rust
use std::io::Read;
fn s()->String{let mut x=String::new();std::io::stdin().read_to_string(&mut x).ok();return x;}
fn main(){
let mut b:Vec<i64>=vec![281543712968705,1103823438080];
for i in 0..5{b.push(341<<i*10);b.push(1100586419201<<i*2);}
let x=s().replace("\n","").replace(".","0").replace("O","1").replace("X","2");
let a=i64::from_str_radix(&x,4).unwrap();
let mut r=2;
for i in 0..2{if b.iter().any(|&e|((a>>i)&e)==e){r=i;}}
println!("{}","OXD".chars().nth(r).unwrap());
}
```

[^1]: このためにコードレビューBINGOでは採点対象外なんだけどPerlの答案も書く必要があった。