常連

回答者

前にした質問と似ていますが、条件としては[2 2 2 3 3 4 5]のように数字群があり、それらの数字は重複しているものもあります。グループ１とグループ２に分けて、合計値の差が必ずしもゼロになるわけではないことが注意です。

まだ途中のコードで、前と同様にコンビネーション関数を使って解こうと考えたのですが、かなり非効率な方法だなとおもいましたが、一応書いてみたコードが下記のものにになります。


### 該当のソースコード

```
import itertools
min_diff = float('inf')
num = int(input())

lis =  [2 2 2 3 3 4 5]　   ##その他　数字群が様々あるが、、、
lis = [int(x) for x in lis ]
lis = sorted(lis)

group1=[]
group2=[]


for i in range(1,num):
    group1=[]   
    group2=[]
    lis2 = lis.copy()
    
    for c1 in itertools.combinations(lis2, i):
        c1 = list(c1)
        
        group1=[x for x in c1]
        print(sum(group1))
        for j in range(len(c1)):
          
            lis2.remove(c1[j])# ここでremoveの関数にはエラーが起こるが、、、
    
    group2=lis2
    diff =abs(sum(group1)-sum(group2))
    if diff ==0:
        break 
    
    elif  diff< min_diff:
        min_diff = diff
    else:
        continue
print(min_diff)
```

### 試したこと

他にも平均値を求めソートを使い、グループ１、グループ２に、小さい数字順に交互に入れていき、
平均値を超えた場合、余りをもう片方に入れて、合計値が大きいグループから小さいグループに、一番小さい数字を入れていくwhile文を作成したのですが、この最適化問題？では最小値が前回と同様になったらwhileを抜けると考えると、最小値が同じ数字（今回なら２）だと、ずっと交換し続けることになるので、うまく作成できませんでした。おそらくもっと効率のいい考え方があるのではと思うので、ご教授いただけたと思います。


### 補足情報（FW/ツールのバージョンなど）

ここにより詳細な情報を記載してください。


数字群を二つのグループに分けて、それぞれの合計値の差が最小になるアルゴリズムを知りたい。

①全てのRedexに下線を引く
②自由変数を⚪︎する
③各束縛変数から対応する束縛変数へ矢印を書く

上記3点を下記ラムダ計算にて反映したいです。

1. (λz.((λx.yx)x))((vλz.λw.v)zw)
2. x(λx.x)((λy.(λx.x)y)x)

自分なりの回答は下記です。もしどなたか見ていただけるようでしたら、回答が合っているか教えていただきたいです。

1.①全てのRedexに下線を引く
　　計3つRedexがあります
　1) λz.((λx.yx)x))((vλz.λw.v)zw
　2) (λx.yx)x
　3) (vλz.λw.v)zw

　②自由変数に⚪︎をする
　計2つ自由変数があります。
　1)(λx.yx)x)内のy
　2)(vλz.λw.v)内の最初のv


　③各束縛変数から対応する束縛変数へ矢印を書く
![イメージ説明](https://ddjkaamml8q8x.cloudfront.net/questions/2024-08-03/16b6b0d4-5cce-44b4-b82d-d439081fda3b.png)

2.①全てのRedexに下線を引く
　　計3つRedexがあります
　1) x(λx.x)((λy.(λx.x)y)x)
　2) (λy.(λx.x)y)x)
　3) (λx.x)y)

　②自由変数に⚪︎をする
　　計2つ自由変数があります。
　1)一番最初のx
　2)最後のx

　③各束縛変数から対応する束縛変数へ矢印を書く
![イメージ説明](https://ddjkaamml8q8x.cloudfront.net/questions/2024-08-03/d4debedb-dad6-419f-ab4d-e6855ad51151.png)

画像が見えづらくすみません。
自由変数を選択する問題が特に自信がありません。

どうぞよろしくお願いいたします。


ラムダ計算に関する質問〜Redex, 自由変数、束縛変数〜

横M-1×縦N-1の表があり、左上から0,1,2とマス目番号が振られています。
※M,Nは適当に与えられます。
はじめにv(マス目番号)にコマが置かれます。
コマは下の写真のパターンで移動できます。1回の着手で移動できるマスを1マス選んでコマを進めます。ただし,コマは盤の外に出ることはできません。

![コマの移動パターン](https://ddjkaamml8q8x.cloudfront.net/questions/2024-06-21/beca8ed8-e590-416c-a608-c967ba5b784a.png)

この時、vに置かれたコマの最大移動回数を再帰的に求める関数fを作成しました。
v2xy,xy2vはそれぞれ横位置x,縦位置yをマス目番号に戻す、それの逆を行う関数
enum_movesはマス目番号を与えてそこから移動できるマス目番号をリストにして返す関数
となっています。
関数fの中でmemoという変数を使用していますが、これは同じマス目に来た時に計算を再び行わないで済むように作りました。

聞きたいことは
①関数f内で再起を使用しているがmemoの中身が再帰された時にどのように作用しているのかが分からない
②関数fを改善できるとするならどうするべきか
です。

関数fが再帰的に関数を呼び出し移動回数を呼び出された度に追加し最大移動回数を求めている。memoを使って同じマス目に来た時に繰り返し処理をしなくてもいいようにしている。という表面上の動作の理解はしています。しかし実際にmemo値をどのように参照しているのか、元を言えば実際に値を入れて計算した時どのような順序でこの関数が動いているのかが分かってません。
教えていただけたら幸いです。


```python
def v2xy(M, v):
    y = v // M
    x = v % M
    return x, y

def xy2v(M, x, y):
    return y * M + x

def enum_moves(M, N, v):
    x, y = v2xy(M, v)
    moves = []

    # 左に2マス進み上に1マス (x - 2, y - 1)
    if x - 2 >= 0 and y - 1 >= 0:
        moves.append(xy2v(M, x - 2, y - 1))
    
    # 左に2マス進み下に1マス (x - 2, y + 1)
    if x - 2 >= 0 and y + 1 < N:
        moves.append(xy2v(M, x - 2, y + 1))
    
    # 上に2マス進み右に1マス (x + 1, y - 2)
    if x + 1 < M and y - 2 >= 0:
        moves.append(xy2v(M, x + 1, y - 2))
    
    # 上に2マス進み左に1マス (x - 1, y - 2)
    if x - 1 >= 0 and y - 2 >= 0:
        moves.append(xy2v(M, x - 1, y - 2))

    return moves

def f(M, N, v, memo=None):
    if memo is None:
        memo = {}
    
    if v in memo:
        return memo[v]
    
    moves = enum_moves(M, N, v)
    
    if not moves:
        memo[v] = 0
        return 0
    
    max_moves = 0
    for move in moves:
        max_moves = max(max_moves, f(M, N, move, memo))
    
    memo[v] = max_moves + 1
    return memo[v]




M = 10
N = 8
v =23
moves = enum_moves(M, N, v)
print(f"{v} から1回の着手で移動可能なマス目番号: {moves}")
max_moves = f(M, N, v)
print(f"{v} からこれ以上移動できなくなるまでの最大着手回数: {max_moves}")
```


python 表上で移動するコマの最大移動可能回数を求める

質問に対しての回答は

1. 答えそのものの提示
1. 答えを考えるためのルート提示

の2つに分かれると思うのですが、皆さんはどちらが多いですか？

どストレートに言ってBA獲得狙いなら前者が圧倒的に優位だとは思うのですが、それだと質問者のスキル育成だとかの側面で劣るよなぁ…と思うことが多々ありまして。
実際、質問を見ていると他サイトコピペ(一部だけ)して使えません・動きませんといったものもありますしね…

答えが簡単に手に入ることで、考えることをしなくならないか心配なときがあります。

teratailでの回答について

### 実現したいこと

Noneではない引数1つから成る関数`Callable[[P], R]`があります。
この関数を拡張し、引数がNoneのときはNoneを返し、
Noneでない場合は元々の戻り値を返すようにしたいです。

### 前提

Python3.12を使用しています。

以下の関数を例に考えます。

```python
def twice(text: str) -> str:
    """文字列を2回繰り返す"""
    return text * 2
```

この関数を拡張し、以下のように文字列とNoneの両方を扱えるようにしたいです。

```python
from random import random
may_be_none: str | None = 'text' if random() < 0.5 else None

o1 = twice('text')  # o1がstrと型推論される
o2 = twice(None)  # o2はNoneであると型推論される
o3 = twice(may_be_none)  # o3はstr | Noneであると型推論される
```

具体的に言うと、以下の3つの条件を満たしたいです。

- [ ] 型推論が効く
    - 引数が`P`のとき、戻り値は`R`と型推論される (上記`o1`のケース)
    - 引数が`None`のとき、戻り値は`None`と型推論される (上記`o2`のケース)
    - 引数が`P | None`のとき、戻り値は`R | None`と型推論される (上記`o3`のケース, 上記2つを満たせば自動的に満たすはず)
- [ ] vscodeでマウスオーバーすると、docstringが表示される (拡張機能側の問題？)
    - 実行時の__doc__に値が残っているかどうかではなく、エディタ上で見られるかどうか
- [ ] 他の関数にも流用しやすい
    - 定型文をあちこちに書かないで済むようにしたい

### 発生している問題

上記3つの条件を同時に満たすことができません。
以下は試したことを順に書き連ねているため、**@wrapsでdocstringを維持するように (失敗)** まで読み飛ばしてください。

### 試したこと

#### 型を`Callable[[P|None], R|None]`に変える

型ヒントを書き換え、関数内でNoneチェックをするようにしたものです。
引数に関係なく戻り値の型が`str | None`と推論されてしまいます。

- [ ] 型推論が効く
- [x] docstringが表示される
- [ ] 流用しやすい

```python
def twice(text: str | None) -> str | None:
    """文字列を2回繰り返す"""
    return text * 2 if text is not None else None

o1 = twice('text')  # str | None
o2 = twice(None)  # str | None
o3 = twice(may_be_none)  # str | None
```

#### overloadで`P`と`None`を分ける

型推論の挙動としては理想です。
ですが同様の関数すべてにoverloadをつけるのはちょっと面倒に感じます。

- [x] 型推論が効く
- [x] docstringが表示される
- [ ] 流用しやすい

```python
from typing import overload

@overload
def twice(text: str) -> str: ...

@overload
def twice(text: None) -> None: ...

def twice(text: str | None) -> str | None:
    """文字列を2回繰り返す"""
    return text * 2 if text is not None else None

o1 = twice('text')  # str
o2 = twice(None)  # None
o3 = twice(may_be_none)  # str | None
```

#### decoratorにして流用しやすく

decoratorとすることで、関数を書き直すことなくNoneに対応できました。
しかし、wrappedによってdocstringが表示されなくなってしまいました。

- [x] 型推論が効く
- [ ] docstringが表示される
- [x] 流用しやすい

```python
from typing import Callable, overload

def none_safe[P, R](function: Callable[[P], R]):
    @overload
    def wrapped(arg: P) -> R: ...

    @overload
    def wrapped(arg: None) -> None: ...

    def wrapped(arg: P | None) -> R | None:
        return function(arg) if arg is not None else None

    return wrapped

@none_safe
def twice(text: str) -> str:
    """文字列を2回繰り返す"""
    return text * 2

o1 = twice('text')  # str
o2 = twice(None)  # None
o3 = twice(may_be_none)  # str | None
```

#### `@wraps`でdocstringを維持するように (失敗)

docstringを維持するように`@wraps`を付けたものです。

`@wraps`をすべての/3つ目だけのwrapped関数に付けたり、`@overload`と`@wraps`の順序を入れ替えたりしましたが、
overloadが正常に機能しなくなったり、docstringが表示されなかったりと、期待した動作にはなりませんでした。

- [ ] 型推論が効く
- [x] docstringが表示される
- [x] 流用しやすい

```python
from typing import Callable, overload
from functools import wraps

def none_safe[P, R](function: Callable[[P], R]):
    @overload
    @wraps(function)
    def wrapped(arg: P) -> R: ...

    @overload
    @wraps(function)
    def wrapped(arg: None) -> None: ...

    # @wraps(function)
    def wrapped(arg: P | None) -> R | None:
        return function(arg) if arg is not None else None

    return wrapped

@none_safe
def twice(text: str) -> str:
    """文字列を2回繰り返す"""
    return text * 2

o1 = twice('text')  # str | None
o2 = twice(None)  # str | None
o3 = twice(may_be_none)  # str | None
```

### 環境

* Python 3.12
* vscode 1.87.2
* 拡張機能
    * Python v2024.2.1
    * Pylance v2024.3.1
    * Python Debugger v2024.2.0

Noneに対応していない関数を拡張し、Noneを渡すとNoneが返るようにしたい

下図表中の「並び替える対象」にあるようなデータ（以下、"製品"）
を特定の規則で並べる時の**全ての並び順**を出力したいです。
![イメージ説明](https://ddjkaamml8q8x.cloudfront.net/questions/2022-11-15/492bd431-a793-4c22-98f7-dffa5175a552.jpeg)
並び替えの規則は「条件」のテーブルに示した様に
各製品同士を前後に並べることが可能か不可能か定義されています。
（表の1行目で言うとAの次にBを並べるのは１＝可能）


現在VBAでテスト的に作成したプログラムでは

**①1つ目の製品を選ぶ
②次に並べることが可能な製品を選ぶ
③②を繰り返す
④次に並べることができる製品が無く、行き詰った場合は１つ前の製品に戻り、
　行き詰まった製品を除外して②を再実行
⑤全製品が並びきれたら完了
⑥次のパターンへ…（繰り返し）**

という方式で、並び替えパターンの出力には成功しています。

しかし、この方式では
並べることができる全ルートを試行して並び切るかどうか検証するため、
製品数が大体10以上になると計算量が増え、
使用できるレベルではなくなってしまいます。
(実際の使用時は製品数20~30になります）

上記のような並び替えをより効率的に並び替えるための良い考え方やアイデアがあれば
教えて頂きたいです。

現在はVBAでテストしていますが、
他のツールでの実現可能性があれば試してみたいと考えています。

よろしくお願いいたします。

複数個の対象を特定の規則によって効率よく並び替える方法

### 実現したいこと
Pythonで数字の組み合わせを取得するコードを作りたいのですが、うまくできず困っています
- 1~20までの数字を5つのリストに分ける動作を6回行う
　(例)[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 16], [17, 18, 19, 20]のように分ける

【条件】
　　①過去に同じリストに入ったことのある数字は同じリストに入れられない
　　　例えば[1,2,3,4]のように入った場合は、1は以降の振り分けで2,3,4と同じリストには入れられない([1,2,5,6]などはNG)
　　②数字は毎回1~20まで使い切った組み合わせにする


### 該当のソースコード

```ここに言語名を入力
import random
import itertools

# 6回の繰り返し
saved_number = {}  # 過去の組み合わせを保存
result_dict = {num: [] for num in range(1, 21)}  # 数字ごとのリストが一緒になった数字を記録
numbers = list(range(1, 21))  # 1から20までの数字のリストを作成

for _ in range(6):  # 6回行う
    sections = [[] for _ in range(5)]  # 5つに分ける
    numbers = list(range(1, 21))  # 1から20までの数字のリストを作成
    for num in numbers:  # 数字の取り出し
        for num_list in sections:  # 区画リスト
            saved_num = result_dict[num]  # 過去に一緒になった数字
            if any(element in num_list for element in saved_num) or len(num_list) > 3:  # 過去に同じリストに入ったまたは区画が4個以上の場合は処理しない
                continue
            else:
                num_list.append(num)
                break
    saved_number[f"{_}回目"] = sections  # 回数ごとの分け方を保存

    # 各数字をキーにして、同じリスト内に出現した他の数字をリストにまとめる
    for key, value in saved_number.items():
        for sublist in value:
            for num in sublist:
                if num not in result_dict:
                    result_dict[num] = []

                other_numbers = set(sublist) - {num}
                result_dict[num].extend(other_numbers)
    # 各回の結果を表示
    print(f"回: {_ + 1}")
    for i, section in enumerate(sections, 1):
        print(f"区画{i}: {section}")

```
このコードだと、出力が
回: 1
区画1: [1, 2, 3, 4]
区画2: [5, 6, 7, 8]
区画3: [9, 10, 11, 12]
区画4: [13, 14, 15, 16]
区画5: [17, 18, 19, 20]
回: 2
区画1: [1, 5, 9, 13]
区画2: [2, 6, 10, 14]
区画3: [3, 7, 11, 15]
区画4: [4, 8, 12, 16]
区画5: [17]
回: 3
区画1: [1, 6, 11, 16]
区画2: [2, 5, 12, 15]
区画3: [3, 8, 9, 14]
区画4: [4, 7, 10, 13]
区画5: [17]
回: 4
区画1: [1, 7, 12, 14]
区画2: [2, 8, 11, 13]
区画3: [3, 5, 10, 16]
区画4: [4, 6, 9, 15]
区画5: [17]
回: 5
区画1: [1, 8, 10, 15]
区画2: [2, 7, 9, 16]
区画3: [3, 6, 12, 13]
区画4: [4, 5, 11, 14]
区画5: [17]
回: 6
区画1: [1, 17]
区画2: [2, 18]
区画3: [3, 19]
区画4: [4, 20]
区画5: [5]
となり二回目以降1~20を使い切れていない問題が発生しています。
最初のリストからどんどん埋めていっているので最後の数字になるにつれ入れる場所がなくなってしまっています・・・
### 試したこと

1~20のなかから4つ組み合わせを取ってくる方法(itertools)も試してみたのですがうまくいかず



数字の組み合わせを取得する

### 実現したいこと

ここに実現したいことを箇条書きで書いてください。
- [ ] 辺の長さが1から100のランダムな長方形が約1000個あるリストがあります。
- [ ] （9割程度は高さが30以下です。高さと横幅は異なり、イレギュラーはありますが、高さは横幅の概ね0.5～1.5倍程度です。）
- [ ] 横幅が約4000のスペースに上から左詰めで長方形を配置します。
- [ ] すべての長方形は重ねて配置してできません。
- [ ] スペースの横幅をはみ出る場合には改行し、下に作成する次の行に配置します。
- [ ] 行の高さは30です。
- [ ] 長方形の高さが行の高さをはみ出る場合には、上の行に配置済みの長方形を右にずらして配置しなおします。
- [ ] 長方形を配置しなおした結果、スペースの横幅をはみ出す場合には改行位置を変更します。
![イメージ説明](https://ddjkaamml8q8x.cloudfront.net/questions/2023-12-10/ef7d4ee0-4492-4586-bc53-f0e729b1f33d.png)
### 前提

python
長方形のリストはpandas DataFrameに入っています。
DataFrameのままでもリストにしてもらっても構いません。

### 試したこと

いろいろ試していますが、上にはみ出す長方形がなかなかうまく配置できません。
長方形の下部をベースに上部の行番号と位置が決まりますが、上部を挿入することで下部の位置が変わります。
再度下部の位置を変更することで、行からはみ出すケースがあり、その場合下部の位置が次の行になるため、
再度上部の位置を変更する必要が発生します。
上部の位置を変更すると下部の位置が変わり、という感じで最適な位置が決まらないです。

サンプルを実装できる方がいると大変ありがたいですが、
こうすればよい、というアルゴリズムの提示だけでも助かりますので、
ご教示ください。


長方形をきれいに並べたい

# 質問
Pythonでは、`x.y`と書いた場合、`x`のオブジェクトツリーを探索し、属性`y`を探すと書籍で学びました。（見つからない場合は「`AttributeError`となる」とありました。）

その際、以下のコードにおいてクラス`A`が備える変数`num`はインスタンス`x`から参照できるのに対し、同じくクラスAが備える`__base__`が参照できない理由が分からず困っています。

```Python
class A():
    num = 500 

x = A()
print(hasattr(A,"num")) #⇒ True
print(hasattr(x,"num")) #⇒ True

print(hasattr(A,"__base__")) #⇒ True
print(hasattr(x,"__base__")) #⇒ False(numと同じくクラスが備えているはずなのにFalseの理由が分からず…)

print(x.num) #⇒ 500
print(x.__base__) #AttributeError: 'A' object has no attribute '__base__'(numと同じくクラスが__base__を備えているはずなのにエラー)
```

# 調べたこと

この事象と関係あるかは分かりませんが、調べていたところ公式ドキュメントに
> 属性アクセスのデフォルトの振る舞いは、オブジェクトの辞書の属性の取得、設定、削除です。例えば a.x は、まず a.__dict__['x']、それから type(a).__dict__['x']、さらに type(a) のメソッド探索順序に従ったさらなる探索へと連鎖します。
> [デスクリプタ HowTo ガイド](https://docs.python.org/ja/3/howto/descriptor.html#definition-and-introduction)
とありました。
そこで、今回は`x.__base__`で`AttributeError`が発生したため、試しに以下の書き方をしてみました。
```Python
class A():
    num = 500 

x = A()
print(A.__base__) #⇒ <class 'object'> 
print(type(x).__base__) #⇒ <class 'object'>
print(type(x).__dict__['__base__']) #⇒ KeyError: '__base__'
```
`type(x).__dict__['__base__']`はエラーとなりました。
たしかに`type(x).__dict__`の中を覗くと`__base__`は存在しません。
```Python
class A():
    num = 500 

x = A()
print(type(x).__dict__.keys()) #⇒ dict_keys(['__module__', 'num', '__dict__', '__weakref__', '__doc__'])
```

これは、以下の理解でよいのでしょうか。
・`x`は`__base__`を備えていないため、クラスオブジェクト及びクラスが継承するオブジェクトが`__base__`を備えていないか探索していく
・探索では、オブジェクトの`__dict__`の中を探していく
・今回、クラス`A`は`__base__`を備えているが、それは`__dict__`の中には存在しないため、見つからなかったことになる。
・クラス`A`は、クラス`Object`を継承しているため、`Object`の`__dict__`の中にも`__base__`があるか探すが、存在せず見つからなかったことになる。
・クラス`Object`の`__dict__`まで探して見つからなかったので、これ以上探索先は無い（※）ため、`AttributeError`で終了する。
（※）`x`が`__getattr__`を備えている場合はそれを呼び出す。

単純すぎる理解と承知の上ですが、この程度しか思いつかず申し訳ありません。
初歩的な質問で大変恐縮ですが、冒頭のコードで`x.__base__`が`AttributeError`になってしまう理由を教えていただけますと幸いです。
よろしくお願いいたします。

Pythonにおいてクラスが持つ属性をインスタンスから呼び出せない理由

### 前提

再帰を使ったDFSはスタックに書き換えることができるそうですが、再帰の戻り値を使ったDFSをスタックによるDFSへの書き換え方がわかりません。

```C++
// 適当な例です
struct node
{
	int value;
	node *left;
	node *right;
};

int dfs( node *n )
{
	if( n == nullptr )
		return INT_MIN;

	int left_value = dfs( n->left );
	int right_value = dfs( n->left );
	
	return max( n->value, max( left_value, right_value ));
}
```
例えばこのようなグラフ探索のコードがあるとします。左右の子ノードを探索し、自身の値を含めた3つの中で最大の値を呼び出し元に返すことを意識しています。

これをスタック変数を使って書き換えると次のようになると思ったのですが

```C++
int main()
{
    struct node
    {
    	int value;
    	node *left;
    	node *right;
    };
    
    stack<node> s;
    node n;
    s.push(n);
    
    while( !s.empty() )
    {
    	n = s.top();
    	s.pop();
    	
    	if( n == nullptr )
    		continue; // 次の状態をスタックに積まずにループを周回する
    	
		s.push(n->left);
		s.push(n->right);
    }
}
```

この2つは動作が同じではないように思います。

再帰を使ったものは、A -> B -> Cという順で呼び出した場合にA -> B -> C -> B -> Aという順で遷移します。Bで再帰関数を呼び出した際にBの動作は一旦停止し、Cが終わってからBの続きをします。ですからBでCの結果を利用することができます。

しかしスタック変数の場合はループの中でスタックに積みますが、実際にノードを探索するのは次のループでスタックからpopしたときです。BでCをスタックに積みますが、Bが終わって次のループの冒頭でCがスタックからポップされます。ですから、BでCの結果を利用することはできないように思います。

これは例ですので、単に全ノードで一番大きな値が欲しいだけなら、どこかスコープの外で変数を宣言し、そこに格納すればいいのですが、細部で異なります。

DFSの場合は困ったら再帰でいいのですが、スタック変数とループの場合はスタックをキューに変更すれば、BFSに直せる点でメリットがあると考えています。

### 実現したいこと

再帰を使ったDFSを、スタック変数とループを使った等価なDFSに書き換えたい。

例えば

https://leetcode.com/problems/binary-tree-maximum-path-sum/

この問題を再帰を使わないで解きたい。


### 補足情報（FW/ツールのバージョンなど）

よろしくお願いします。

スタック変数を使った深さ優先探索と、再帰の違いについて

Javaの初心者です。

Javaの初心者向け(PaizaスキルチェックのC～Bレベル程度)
クイズ問題集を探しています。

Paizaスキルチェックは一回しか挑戦できないため、
できれば他の問題集でアルゴリズムを組むことに慣れておきたいです。
書籍でもサイトでも構いませんが、言語は日本語か英語しか読めません。

心当たりのある方は、ご回答をいただきたく存じます。

Javaの初心者向け問題集(Paiza以外)はありませんか？

paizaの練習問題やスキルチェックの問題を解いているのですが、模範解答がないためスキルアップできません。
頑張って考えても分からない場合など、解決策がなく挫折しそうになります。
問題を解く形式は楽しいのでpaiza以外の、問題集形式で模範解答があるようなサイトや本などを教えてください。

paizaのスキルチェックの解答が分かりません

### 実現したいこと

AtcoderでACにするためにどこを変えなければならないか知りたいです。

### 前提

AtcoderのRegular Contest 115のCを解いている。

### 発生している問題・エラーメッセージ

いくつかのテストケースでWAになっている

### 該当のソースコード

```Python
N = int(input())
prime = []
used = [0]
prime_dict = dict()

for i in range(1,N+1):
  for x in prime:
    if i%x!=0:
      print(prime_dict[x], end=" ")
      break
  else:
    used.append(used[-1]+1)
    prime.append(i)
    prime_dict[i] = used[-1]
    print(used[-1], end=" ")
```

### 試したこと

特になし

### 補足情報（FW/ツールのバージョンなど）

Atcoderの問題のリンク:https://atcoder.jp/contests/arc115/tasks/arc115_c

Atcoderの問題

```PHP
// 部分和問題
$arr =[1,2,4,7];
$k=13;
$n=4;

function depth($arr, $k,$n,$sum=0, $i=0){
    if($i == $n) {
        return $sum == $k;
    };
    // 再帰A
    if(depth($arr, $k,$n, $sum, $i+1)){ return true; }
    // 再帰B
    if(depth($arr, $k,$n, $sum+$arr[$i], $i+1)){ return true; }
    
    return false;
    
}

var_dump(depth($arr, $k,$n,0,0));
```

上記のような関数があった時、再帰A,Bがどのような順序で呼ばれ、処理が終了するのか理解できません。
理解の助けとなる、サンプルやアイディアがあればご教授願います。

※再帰処理の特性として下記は多少なりとも理解しています。
・FILO(スタック)
・終了条件を定義する

部分和問題の再帰処理について

### 実現したいこと

MINGW64で作ったC++プログラムで正しく日本語を扱いたい

### 前提

- MSYS2-MINGW64使用(※)
- MSVCのRuntimeを使用する
- libstdc++を使用する
- gccを使用する(~~現状12.2.0~~ →13.2.0)
- MSYS2などの環境に依存せず、作成したバイナリは単品で動作する
- Windows 10以降はmustで、可能ならそれ以前でも正しく動作させたい
- MSYS2環境のbashで動かす場合、環境変数LC_*/LANG/LANGUAGEは未設定とする(LC_CTYPE=ja_JP.UTF-8は可)
- 端末(conhost/mintty/etc...)は何でもいいし、適宜設定は変更するものとするが、原則デフォルトの状態で動作すること
- 日本語Windowsの場合、システムロケールのコードページは932でも65002でもどちらでも動作するものする
- 紐付けられた端末があり、端末への出力が実際にある場合、端末のコードページには追従してもいいし、しなくてもいいが、システムロケールのコードページと端末のコードページのいずれかで入出力できていること

※参考
https://www.msys2.org/docs/environments/

### 質問

MINGW64で日本語を扱うプログラムをC++で正しく記述する方法を教えてください。
何も考えずに実装すると、Hello, worldレベルで正しく動きません。

### 発生している問題・エラーメッセージ

例を2つほど挙げます
※ソースコードは次節参照

#### (1) std::coutに出力するケース
ビルドと実行(システムロケールはコードページ932でmsys2環境(mintty)で実施)
```bash
$ g++ -g -Wall -static hello.cpp -o hello
$ env | grep LANG
$ env | grep LC
LC_CTYPE=ja_JP.UTF-8
$ ./hello
縺薙ｓ縺ｫ縺｡縺ｯ

$
```
msys2環境のminttyの設定はja_JPのUTF-8にしようが、defaultのままにしようが、同じです。
一言で言えば、この状態からcmd /c "dir"したときに日本語が化けないのと同様の、CP932→UTF-8の変換が「どこかで」かかっている文字の化け方をしています。

#### (2)  std::wcoutに出力するケース
```bash
$ g++ -g -Wall -static hellow.cpp -o hellow
$ ./hellow

$
```
これは端末以前に何も出力されていないことを示しています。(実際にパイプで繋いでも何も出ていません。)

### 該当のソースコード

**hello.cpp(utf-8で保存)**
```C++
#include <iostream>
int main() {
    std::cout << "こんにちは" << std::endl;
    return 0;
}
```
**hellow.cpp(utf-8で保存)**
```C++
#include <iostream>
int main() {
    std::wcout << L"こんにちは" << std::endl;
    return 0;
}
```

### 試したこと

#### (1) hexdumpで調べる
```bash
$ ./hello | hexdump -C
00000000  e3 81 93 e3 82 93 e3 81  ab e3 81 a1 e3 81 af 0d  |................|
00000010  0a                                                |.|
00000011

$ ./hellow | hexdump -C

$
```
MSYS2 bashでパイプで出力する場合、./helloはUTF-8で出力されている
MSYS2 bashでパイプで出力する場合、./hellowは何も出力しない

#### (2) iconvで調べる
```bash
$ ./hello | iconv -f utf-8 -t cp932
▒▒▒▒ɂ▒▒▒

$ ./hello | iconv -f utf-8 -t cp932 | hexdump -C
00000000  82 b1 82 f1 82 c9 82 bf  82 cd 0d 0a              |............|
0000000c

$
```
iconvでシフトJISに変換出力してみたが、さらに文字化けするだけだった
hexdumpの結果を見る限り変換は正しく実施されている

#### (3) catを噛ませてみる
```bash
$ ./hello | cat
こんにちは

$./hello | cat | hexdump -C
00000000  e3 81 93 e3 82 93 e3 81  ab e3 81 a1 e3 81 af 0d  |................|
00000010  0a                                                |.|
00000011

$ env | egrep -E '(LC_|LANG)'
LC_CTYPE=ja_JP.UTF-8

$ 
```
MSYS2のcatを噛ませると、同じ内容(hexdumpの結果からUTF-8と分かる)でも「なぜか」正しく表示される。
bash/minttyへの出力方法が./helloとcatで異なっていて、その区別から./helloだけCP932→UTF-8変換をかけられていると推測する。

#### (4) cmdから見てみる
```cmd
C:\>hello
縺薙ｓ縺ｫ縺｡縺ｯ

C:\>hello | C:\msys64\usr\bin\cat
こんにちは

C:\>chcp
現在のコード ページ: 932

C:\>set | findstr LC_

C:\>set | findstr LANG

C:\>
```
※conhost.exe上のcmd.exe(minttyなどMSYS2環境ではなく、純粋なWindows環境)

コマンドプロンプトからでも(3)の現象は同様に再現する。また環境変数の影響でもなく、cmdは子プロセスに変換などの細工をしないので、helloは素直にUTF-8で出力していることが確定し、catが単体でUTF-8→CP932の変換をしているということが分かる。

#### (5) 絵文字を出力させてみる
```bash
$ cat emoji.cpp
#include <iostream>
int main() {
    std::cout << "😊" << std::endl;
    return 0;
}

$  g++ -g -Wall -static emoji.cpp -o emoji

$ ./emoji
・

$ ./emoji | cat
😊

$ ./emoji | cat | hexdump -C
00000000  f0 9f 98 8a 0d 0a                                 |......|
00000006

$
```
絵文字を表示可能なことから、シフトJISで表示しようとしていないことが分かる。さらに具体的に言えば、bashやcatがパイプからの読み込み時に変換をかけていないこと、受け取ったminttyも変換していないことが分かる。

#### (6) リテラルをシフトJISとしてコンパイルさせる
```bash
$ g++ -g -Wall -static -fexec-charset=CP932 hello.cpp -o hello_sjis

$ ./hello_sjis
こんにちは

$ ./hello_sjis | hexdump -C
00000000  82 b1 82 f1 82 c9 82 bf  82 cd 0d 0a              |............|
0000000c

$
```
シフトJISとして出力されており、正しく表示されている(minttyはロケールCの文字セットUTF-8)。

#### (7) 依存DLLを調べる
```bash
$ ldd hello
        ntdll.dll => /c/WINDOWS/SYSTEM32/ntdll.dll (0x7fffc4950000)
        KERNEL32.DLL => /c/WINDOWS/System32/KERNEL32.DLL (0x7fffc4660000)
        KERNELBASE.dll => /c/WINDOWS/System32/KERNELBASE.dll (0x7fffc2400000)
        msvcrt.dll => /c/WINDOWS/System32/msvcrt.dll (0x7fffc45c0000)

$ ldd `which cat`
        ntdll.dll => /c/WINDOWS/SYSTEM32/ntdll.dll (0x7fffc4950000)
        KERNEL32.DLL => /c/WINDOWS/System32/KERNEL32.DLL (0x7fffc4660000)
        KERNELBASE.dll => /c/WINDOWS/System32/KERNELBASE.dll (0x7fffc2400000)
        msys-intl-8.dll => /usr/bin/msys-intl-8.dll (0x430b30000)
        msys-2.0.dll => /usr/bin/msys-2.0.dll (0x180040000)
        msys-iconv-2.dll => /usr/bin/msys-iconv-2.dll (0x5603f0000)

$ ldd `which bash`
        ntdll.dll => /c/WINDOWS/SYSTEM32/ntdll.dll (0x7fffc4950000)
        KERNEL32.DLL => /c/WINDOWS/System32/KERNEL32.DLL (0x7fffc4660000)
        KERNELBASE.dll => /c/WINDOWS/System32/KERNELBASE.dll (0x7fffc2400000)
        USER32.dll => /c/WINDOWS/System32/USER32.dll (0x7fffc3a60000)
        win32u.dll => /c/WINDOWS/System32/win32u.dll (0x7fffc2970000)
        msys-2.0.dll => /usr/bin/msys-2.0.dll (0x180040000)
        GDI32.dll => /c/WINDOWS/System32/GDI32.dll (0x7fffc32e0000)
        gdi32full.dll => /c/WINDOWS/System32/gdi32full.dll (0x7fffc20c0000)
        msvcp_win.dll => /c/WINDOWS/System32/msvcp_win.dll (0x7fffc2360000)
        ucrtbase.dll => /c/WINDOWS/System32/ucrtbase.dll (0x7fffc2260000)

$
```
catやbashなどはmsys-2.0.dllをリンクしており、MSYS2ランタイムで動作しているのが分かる。
helloはMINGW64プログラムなのでMSYS2ランタイムで動作していない。
以上から標準入出力の繋がり方が、MSYS2ランタイムを使ったもの同士とそれ以外で異なるのではないかと推測している。
パイプの場合はbashとcmdで違うのではないかと推測している。

#### (8) wcoutの設定
```bash
$ cat hellow2.cpp
#include <iostream>
int main() {
    std::wcout.imbue(std::locale(""));
    std::wcout << L"こんにちは" << std::endl;
    return 0;
}

$ g++ -g -Wall -static hellow2.cpp -o hellow2

$ ./hellow2.exe
terminate called after throwing an instance of 'std::runtime_error'
  what():  locale::facet::_S_create_c_locale name not valid

$
```
システムロケールへの設定はできない→wcoutは使えない
(https://stackoverflow.com/a/20181564)。
より正確にはwcoutは日本語の出力ができない。libstdc++がgnuモデル以外(今回はgeneralモデル)での変換を実装していないため。

#### (9) 調べたことまとめ
上記から、MINGW64で正しく日本語を扱うには、
- wcoutを使わず、coutを使う
- msvcrtかWindowsAPIか外部ライブラリなどを使って自分でエンコーディングを(システムロケールのコードページか端末のコードページに)変換する
- リテラルをマルチバイトの固定エンコーディングにする(シフトJISなど)とワイド文字経由のコードページ変換が2度必要になり、手間がかかるため、ワイド文字列のリテラルか、u8プレフィックス付きを使うべき(ただしC++20でchar型での扱いができなくなる)
なのかと思う

ただマルチバイト(cout)にすると、
- 入出力時に変換が必要になり、わざわざマルチバイトにして出力した文字列をWin32側でまたワイド文字列に戻すなどの処理が入りそう
これはそもそもWriteConsoleWがワイド文字列を受け取れるから。

普段使いしてる人の正しい日本語の扱い方を知りたい

### 補足情報（FW/ツールのバージョンなど）
msys/msys2-runtime ~~3.4.6-2~~ → 3.4.10-2

※デバッグ用のシンボル情報が欲しくて最新バージョンに更新してビルドしました(2023/12/18)。

MINGW64で作ったC++プログラムで正しく日本語を扱いたい

VisualStudio c++にてfloat型の変数に330245000代入したところ、330244992.となってしまいました。
これは桁落ちというやつなんでしょうか？
桁落ちって小数点以下で起こるものだと思っていたのですが、
floatは、有効桁数7桁とあったのですが、7桁以上は整数部分でも桁落ちするという意味なのですか？

Float型について

# 環境
c++17
(必要であれば、c++20に変更可能)

# やりたいこと

```c++
class CustomInt {
public:
    CustomInt(int rhs) : value(rhs) {}
    explicit operator int() const noexcept { return value; };
private:
    int value;
}
std::ostream& operator<<(std::ostream& lhs, const CustomInt& rhs)
{
    lhs << static_cast<int>(rhs);
    return lhs;
}

int main() {
    // 1
    CustomInt hoge = {0};
    std::cout << hoge << std::endl;
    hoge = 20;
    std::cout << std::pow(static_cast<int>(hoge), 2) << std::endl;
    
    // 2
    std::cout << std::pow(hoge, 2) << std::endl;
}

```

現在のコードだと、1の部分は問題なく実行できますが、2のコードは下のようなコンパイルエラーが出ます。

```
no matching function for call to 'pow(CustomInt&, int)
```

hogeというCustomIntのインスタンスが、あたかもint型のように振る舞うためにはどうoperatorなどを設定すればよいのでしょうか？



powやsinなどの引数に入れることができる自作classの作り方を知りたい

leetcodeの以下の問題で二分探索の勉強をしています。
シンプルな二分探索はできるのですが、以下のような応用的な問題でつまづきます。
[leetcodeの問題](https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/)

以下のようなキレイなコードがディスカッションにいくつも投稿されています。
```Python
def searchRange(self, nums, target):
    def binarySearchLeft(A, x):
        left, right = 0, len(A) - 1
        while left <= right:
            mid = (left + right) / 2
            if x > A[mid]: left = mid + 1
            else: right = mid - 1
        return left

    def binarySearchRight(A, x):
        left, right = 0, len(A) - 1
        while left <= right:
            mid = (left + right) / 2
            if x >= A[mid]: left = mid + 1
            else: right = mid - 1
        return right
        
    left, right = binarySearchLeft(nums, target), binarySearchRight(nums, target)
    return (left, right) if left <= right else [-1, -1]
```
しかしどれも”left”・"right"を、"mid"で更新していくときに、+1、-1が出てきます。このような実装も理解はできるようになりましたが、それでもコーナーケースの理解はややこしいので、「めぐる式二分探索」というのをwebで学んでから、普段はそれをベースにしていました。ですので、この問題も似たようなパターンで解けないか考えています。ですが、どうしてもうまく行きません。
[めぐる式二分探索](https://twitter.com/meguru_comp/status/697008509376835584)


私が最初に書いたコードは以下です。
あまりキレイではなく、読みにくくてすみません。
```Python
class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        # find end        
        left = 0
        right = len(nums) - 1
        while right - left > 1:
            mid = left + ((right - left) // 2)
            if nums[mid] == target:
                if mid == right or nums[mid + 1] > target:
                    end = mid
                    break

            if self.isin_left_area(nums[mid], target):
                right = mid
            else:
                left = mid
        else:
            end = -1      
            
        # find start   
        left = 0
        right = len(nums) - 1
        while right - left > 1:
            mid = left + ((right - left) // 2)
            if nums[mid] == target:
                if mid == left or nums[mid - 1] < target:
                    start = mid
                    break
            
            if self.isin_right_area(nums[mid], target):
                left = mid
            else:
                right = mid
        else:
            start = -1

        return [start, end]
            
    def isin_left_area(self, mid_val:int, target:int):
        return mid_val > target
   
    def isin_right_area(self, mid_val:int, target:int):
        return mid_val < target    
        
```

ケースとして、nums=[1], target=1やnums=[1, 1, 1], target=1などの場合がうまく行きません。開区間で考えようとすることで、リストnumsの先頭と末尾の判断ができないのが原因と思います。これらのケースは、「めぐる式二分探索」をベースにシンプルな実装をしようと思うと、例外として条件を作るしかないでしょうか。うまく実装できるような方法があれば教えていただきたいです。

leetcodeの二分探索の問題でめぐる式二分探索がうまくいかない理由

運営側への質問です。
コードブロックで使える言語の一覧はどこかにありますか？ちょっと見当たらないようです。
さっき、VBA を書こうとして困りました。vbnetで代用ですかね。
Windowsのバッチスクリプトは試行錯誤で見つけましたが、BATでもCMDでもなく何故かDOS。懐かしい単語ですが、DOSバッチと、現在のWindowsのバッチは別物です。CMDが望ましいでしょう。

#追記: 2018-08-08
現時点では↓のようです。
```plain
1c:"1C"
abnf
accesslog
actionscript:"ActionScript", as
ada
apache:"Apache", apacheconf
applescript:"AppleScript", osascript
arduino:"Arduino"
armasm, arm
asciidoc:"AsciiDoc", adoc
aspectj
autohotkey:"AutoHotkey"
autoit
avrasm:"AVR Assembler"
awk
axapta:"Axapta"
bash:"Bash", sh, zsh
basic
bnf
brainfuck:"Brainfuck", bf
cal
capnproto, capnp
ceylon
clean, clean, icl, dcl
clojure-repl
clojure:"Clojure", clj
cmake:"CMake", cmake.in
coffeescript:"CoffeeScript", coffee, cson, iced
coq
cos, cos, cls
cpp:"C++", c:"C", cc, h, c++:"C++", h++, hpp
crmsh, crm, pcmk
crystal, cr
cs, csharp:"C#", c#:"C#"
csp
css:"CSS"
d:"D"
dart
delphi:"Delphi", dpr, dfm, pas, pascal, freepascal, lazarus, lpr, lfm
diff:"Diff", patch
django:"Django", jinja
dns, bind, zone
dockerfile, docker
dos:"DOS.bat", bat, cmd
dsconfig
dts
dust, dst
ebnf
elixir:"Elixir"
elm
erb
erlang-repl:"Erlang REPL"
erlang:"Erlang", erl
excel, xlsx, xls
fix:"FIX"
flix
fortran, f90, f95
fsharp:"F#", fs, f#:"F#"
gams, gms
gauss, gss
gcode
gherkin:"Gherkin", feature
glsl:"GLSL"
go:"Go", golang
golo
gradle:"Gradle"
groovy
haml:"Haml"
handlebars:"Handlebars", hbs, html.hbs, html.handlebars
haskell:"Haskell", hs
haxe:"Haxe", hx
hsp
htmlbars
http:"HTTP", https
hy, hylang
inform7, i7
ini:"Ini", toml
irpf90
java:"Java", jsp
javascript:"JavaScript", js:"JavaScript", jsx
json:"JSON"
julia
kotlin
lasso:"Lasso", ls, lassoscript
ldif
leaf
less
lisp:"Lisp"
livecodeserver
livescript, ls
llvm
lsl
lua:"Lua"
makefile:"Makefile", mk, mak
markdown:"Markdown", md, mkdown, mkd
mathematica, mma
matlab:"Matlab"
maxima
mel:"MEL"
mercury, m, moo
mipsasm, mips
mizar:"Mizar"
mojolicious
monkey
moonscript, moon
n1ql
nginx:"Nginx", nginxconf
nimrod:"Nimrod", nim
nix:"Nix", nixos
nsis:"NSIS"
objectivec:"Objective C", mm, objc, obj-c
ocaml:"OCaml", ml
openscad
oxygene:"Oxygene"
parser3:"Parser3"
perl:"Perl", pl, pm
pf, pf.conf
php:"PHP", php3, php4, php5, php6
plain:"Plain text"
pony
powershell, ps
processing
profile
prolog
protobuf
puppet, pp
purebasic, pb, pbi
python:"Python", py, gyp
q
qml, qt
r:"R"
rib:"RenderMan RIB(RIB)"
roboconf, graph, instances
rsl:"RenderMan RSL(RSL)"
ruby:"Ruby", rb, gemspec, podspec, thor, irb
ruleslanguage
rust:"Rust", rs
scala:"Scala"
scheme
scilab:"Scilab", sci
scss:"SCSS"
smali, smali
smalltalk:"Smalltalk", st
sml, ml
sqf, sqf
sql:"SQL"
stan
stata, do, ado
step21, p21, step, stp
stylus, styl
subunit
swift:"Swift"
taggerscript
tap
tcl, tk
tex:"TeX"
text:"Plain text"
thrift:"Thrift"
tp
twig, craftcms
typescript:"TypeScript", ts
vala:"Vala"
vba:"VBA"
vbnet:"VB.NET", vb
vbscript-html
vbscript:"VBScript", vbs
verilog, v, sv, svh
vhdl:"VHDL"
vim:"Vim Script(Vim)"
x86asm:"Intel x86 Assembly"
xl, tao
xml:"XML", html:"HTML", xhtml, rss, atom, xjb, xsd, xsl, plist
xquery, xpath, xq
yaml, yml, YAML, yaml
zephir, zep
```

このサイトのMarkdown記法のコードブロックで使える言語一覧

c++で出力を小数表示ではなく√なんとかと表示させたいです。
今二次方程式の解を求めるプログラムをxcodeで作っていて
```c++
#include <iostream>
#include <iomanip>
#include <cmath>

using namespace std;

int main()
{

　　double a, b, c;
       double d, sol[2];

　　cout<<"a=";
　　cin >> a;
　　cout<<"b=";
　　cin >> b;
　　cout<<"c=";
　　cin >> c;

　　cout << "二次方程式は: ";
　　cout<<a<<"*xˆ2+";
　　cout<<b<<"*x +";
　　cout<<c<<"=0"<<endl;

　　d=b*b-4*a*c; 25:
　　sol[0] = (-b + sqrt(d)) / (2 * a);
　　sol[1] = (-b - sqrt(d)) / (2 * a);
　　cout.precision(20);
　　cout << "Solutions: " << sol[0] << ", " << sol[1] << endl;

　　return 0;
　　}
```

と書きました。これでは解が±√２の時1.4142135623730951455,-1.4142135623730951455
と表示されます。これを√２,-√２と表示させるにはどのようにしたら良いでしょうか？
また、解が1.732.../4.232...(2.5±√3)の場合は５＋２√3/2、５ー２√３/2と表示させたいです。
つまり中学高校の時に二次方程式を解いたような回答の仕方にしたいのですが、可能でしょうか？