「初中級者が解くべき過去問精選 100 問」を解いていきたい

ここではAtCoder茶色、及び緑色を目指して、以下で紹介されている問題を解いていきます。

https://qiita.com/e869120/items/eb50fdaece12be418faa#2-3-%E5%88%86%E9%87%8E%E5%88%A5%E5%88%9D%E4%B8%AD%E7%B4%9A%E8%80%85%E3%81%8C%E8%A7%A3%E3%81%8F%E3%81%B9%E3%81%8D%E9%81%8E%E5%8E%BB%E5%95%8F%E7%B2%BE%E9%81%B8-100-%E5%95%8F

対象読者として、A問題、B問題は余裕でC問題に手を焼くというレベル感の人々を想定してます。（筆者もそのくらいのレベルです)
使用言語はpythonです。
<br>
<br>
<br>
<br>
<br>
<br>

# diff[?] [最古の遺跡](https://atcoder.jp/contests/joi2007ho/tasks/joi2007ho_c) 2024/10/22
「全探索：工夫して通り数を減らす全列挙」の三番目です。
メモリ制限が64MBとなっているため、pypyだと問答無用でMLEしてしまいます。Cpythonを使ってください。
difficultyはわかりませんが、たぶん緑相当はあるでしょう。
## 普通の全探索
四つの柱の組み合わせを指定し、正方形である事を確認するのが無難ですが、$N<3000$であるため$O(N^4)$のアルゴリズムは当然TLEします。

## 計算量の減らし方
この問題は正方形を見つけ出す問題です。
正方形を見つけ出したいなら、柱二つによって`ベクトルを一つ指定`するだけで十分です。
指定したベクトルから、画像のように青色の正方形が見えてくるはずです。
あとは青頂点の座標に柱があるか調べればOK

![無題93_20241022205533.jpeg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3909330/e22ea54f-33e9-df09-d948-8bc67c5dd792.jpeg)

・辺の選択、すなわち柱二本の組み合わせ全列挙に$O(N^2)$
・青頂点の座標に柱があるか確認するのに$O(N)$...といきたいところですが、ちょっと待った。リストの検索ではなく[集合の検索](https://qiita.com/Hironsan/items/68161ee16b1c9d7b25fb#set)を用いれば、この確認は$O(1)$で行えます。結構重要なテクニックです。
・晴れて正方形が見つかれば、面積を計算する。
以上よりこのアルゴリズムは$O(N^2)$です。

##### 補足

直交ベクトルは「左側」のほかに「右側」も存在します。今回は左側のみ確認しましたが、右側の直交ベクトルによって作られる正方形も考えたくなりますよね。
でも今回の場合は左側だけで十分なんです。
"右側"の正方形も柱二本の選び方を変えれば"左側"の正方形として表せます。
より細かい事を言うと、実装の過程で組み合わせ(i,j)をi<jとして表現する事や、整数の大小関係に関する話も関与してきます。(ヒント：任意の実数a,b,c,dについてa<b<c<d<aみたいな不等式は成り立たないことを使って背理法)



## 実装
メモリの制限があるためpypyは使えない事に注意。

柱の座標をリストで受け取るのはもちろんのこと、座標から柱の存在を逆引きするために集合も作っておきます。
```python:筆者の回答時間:120分
n = int(input())
pillars = []
set_of_pillars = set()
for _ in range(n):
    x,y = map(int,input().split())
    pillars.append((x,y))
    set_of_pillars.add((x,y))

def exist(pillar1,pillar2,vertical):
    return (pillar1[0]+vertical[0],pillar1[1]+vertical[1]) in set_of_pillars and (pillar2[0]+vertical[0],pillar2[1]+vertical[1]) in set_of_pillars
    
max_area = 0
for v1 in range(n):
    for v2 in range(v1+1,n):
        vertical = (pillars[v2][1]-pillars[v1][1],pillars[v1][0]-pillars[v2][0])
        if exist(pillars[v1],pillars[v2],vertical):
            max_area = max(vertical[0]**2+vertical[1]**2,max_area)

print(max_area)
```




<br>
<br>
<br>
<br>
<br>
<br>

# diff[838] [D - Lucky PIN](https://atcoder.jp/contests/sumitrust2019/tasks/sumitb2019_d) 2024/10/17
今回やるのは「全探索：工夫して通り数を減らす全列挙」の二番目、difficultyは838で、緑相当の難易度です。
未だ灰色コーダーの私にはやや困難かもしれません。

## 普通の全探索は困難
N個の中から3つ選ぶ組み合わせを全列挙するにはO(N^3)かかりますが、N<30000ですので、ざっくり9*10^12回の計算になります。これでは間に合いません。

ここで、生成されるpinのパターンはそれほど多くない事に注目しましょう。
Sの中から三つ選ぶ組み合わせは非常にたくさんありますが、それでも生成されるpinは3桁各10通りずつ、全10^3通りしかありえません。
従って、pinのパターンを基準にして全探索を行えれば十分高速なコードになりそうです。

## 全探索の組み方
任意のpinのパターンを選んで、i,j,kとおきます。
このpinがSから生成できるか判定し、もしできるなら設定可能なpinとしてカウントする、という方針で組んでみましょう。
以降、設定可能か判定するための具体的な方法を説明します。
#### 設定可能or不可能の判定
まずSの中にiがあるかどうかをチェック。
もしあれば最初に出てくる物が何桁目か記録しておきます。この桁数をfirst_indexと呼ぶ事にします。
もし無ければ設定不可能。以降の操作は行いません。

次に`first_indexより後の桁`にjが存在するか確認。
もしあれば最初に出てくるものが何桁目か記録しておきます。この桁数をsecond_indexと呼ぶ事にします。
もし無ければ設定不可能。以降の操作は行いません。

次に`second_indexより後の桁`にkが存在するか確認。
もしあれば最初に出てくるものが何桁目か記録しておきます。この桁数をthird_indexと呼ぶ事にします。
もし無ければ設定不可能。

以上によってi,j,kと対応する
first_index < second_index < third_index
を取得できた場合、i,j,kは設定可能pinである事がわかります。
#### 計算量`O(N)`
pinひとつに注目すると、Sの桁を前から順に見ていきますので最悪N回の計算が行われます。
pinのパターン数についてはNに依存しないので、全体でO(N)であることがわかります。よって十分高速なコードが書けそうです。
とはいえパターン数10^3は無視するには大きすぎるので、O(N*10^3)みたいに書いた方が似合いますね。
<br>
<br>
#### 蛇足
Sの中にiが複数ある場合、二番目以降の物は気にしなくていいのか、と考える人がいるかもしれません。
では二番目に現れるiの桁数を指定し、その後無事にj、kも発見できたとしましょう。
得られた桁数を
first_index`2` < second_index`2` < third_index`2`
とおきます。
これと対応するpinは、
first_index < second_index`2` < third_index`2`
と同一となります。
なぜなら、first_index、及びfirst_index2と対応するのはどちらもiであるためです。
以上より、first_indexを指定した場合のみ考えればよい事がわかります。
## 実装
Sは整数ですが、あえて文字列型で受け取る事によって、各桁へのアクセスをindexの指定だけで済ますことができます。取り扱う時はint型に変換するのを忘れずに。
findメソッドは、第二引数を入れる事でサーチの範囲をずらせます。

```python:筆者の回答時間：60分
N = int(input())
S = input()


ans = 0
for i in range(10):
    first_index = S.find(str(i))
    if first_index == -1:
        continue
    for j in range(10):
        second_index = S.find(str(j),first_index+1)
        if second_index == -1:
            continue
        for k in range(10):
            third_index = S.find(str(k),second_index+1)
            if third_index == -1:
                continue
            else:
                #first,second,thirdを無事取れたら設定可能pin
                ans += 1

print(ans)
```





<br>
<br>
<br>
<br>
<br>
<br>

# diff[291] [C - Half and Half](https://atcoder.jp/contests/abc095/tasks/arc096_a) 2024/10/16
まさか本当に次があるとは！
今回やるのは「全探索：工夫して通り数を減らす全列挙」の一番上、difficultyは291でだいぶ易しいようです。

## 全探索っぽさは何処にある？
ピザAの数、ピザBの数、ピザABの数のパターンがいくつか考えられるけども、どれが一番お得なの？という事を問われています。
いくつものパターンがある時は全部調べてしまいましょう。
とはいえ、普通に再帰で全探索するとXとYが大きいのでTLEします。計算量を落とす工夫が必要です。

## A,B,ABの内一つのみに注目すれば十分
ピザA,B,ABのうちどれかの数を決定すれば他の数もおのずと求まる事に気が付きましたか？
（気づけなかった方は、ピザA,B,ABの数をそれぞれs,t,uとして、X,Yとの関係を式で表してみましょう。3変数の方程式２つが出てくるので、解は変数一個で表されることがわかるでしょう。）

例えばAだけに注目すれば、Aの枚数は0,1,2,3,…,Xの計X通り考えられます。X<=10^5ですので、せいぜい10＾5回の計算しか必要ない事になり、十分高速なコードが書けそうです。

## ABの数を用いてA,Bを表してみる
私の場合はピザABの数に注目しました。
ピザABはA,B半分ずつを表しますので、こいつに注目すればわかりやすい対称式がもってこれそうだなーという目論見です。

A,B半分ずつに対しX,Yは整数ですので、ピザABは偶数個の場合しか考えなくて良い事になります。
従って今後ABは二枚一組として考えます。

以下、ABの二枚一組の数をiとおいてA,Bをiで表します。
#### iの制約を考える
iが一番大きくなるのは、A,BをどちらもABだけで容易した時、よって多くともmax(X,Y)です。
#### A、Bの数を考える
Aの数はX-i枚、Bの数はY-i枚…といきたいところですがちょっと待った。
もしi=max(X,Y)だったらどちらかが負の数になってしまう。
こういう時は負の数にはならないように、

max(X-i,0),max(Y-i,0)

と書いておきましょう。X-iがどんどん小さくなっても、０でちゃんと止まってくれます。

#### 合計金額
以上でA,B,ABの数がわかったので、合計金額も計算しておきます。AはA円、BはB円、ABは二枚一組で2*C円ですので、合計は以下となります

max((X-i),0)*A+max((Y-i),0)*B+(2*C)*i

目論見通り対称式を得ることができ…ん…？対称っぽさはあるけど「[対称式](https://ja.wikipedia.org/wiki/%E5%AF%BE%E7%A7%B0%E5%BC%8F)」ではないな…まあ、いいか…
## 実装
ここまできたらあとはやるだけ！
全てのiを調べてresultを最小化しましょう。
```python:筆者の回答時間:20分
A,B,C,X,Y = map(int,input().split())

result = float("INF")
for i in range(max(X,Y)+1):
    result = min(max((X-i),0)*A+max((Y-i),0)*B+2*C*i,result)

print(result)
```
diff400未満に対して20分も取られているようではいけませんね。





<br>
<br>
<br>
<br>
<br>
<br>

# diff[?] [C - カラオケ](https://atcoder.jp/contests/pakencamp-2019-day3/tasks/pakencamp_2019_day3_c) 2024/10/13
今回やるのは全探索の練習問題の内の一つ。

## 全探索と気づくためには？
問題文を読めば
「あらゆる場合を調べれば（計算量はともかくとして）答えがでる」
系統の問題であることがわかります。
そういった場合に有効なのが全探索でした。
実際は他の手法も頭をよぎったりもするのですが、入力のN,Mがせいぜい100以下と小さい値になっていますので、多分全探索で通るだろうな～と目星をつける事ができるはずです。
（全探索問題として紹介されてるんだからそこは考えなくて良くね？みたいな野次は禁句）

## 全探索の組み方と計算量
問題文に従って素直に全探索アルゴリズムを組んでみます。
#### ステップ１　M曲の中から２曲選ぶ（それぞれT1,T2とする）`O(M＾2)`
Mこの中から二つ選ぶ方法はM*(M-1)/2通りあります。
よってすべての組み合わせを列挙するにはO(M**2)かかります。
#### ステップ２　各生徒のスコアを集計し、グループの得点を算出する。`O(N)`
任意の一人の生徒iさんに注目した場合、iさんの得点はT1の得点とT2の得点の内大きい方、つまりO(1)でとってこれます。
この操作をN人に対して行い総和を取るので、スコア算出にかかる計算量はO(N)です。

#### 計算量は　O(NM＾2)
以上から全探索にかかる計算量は、`O(NM＾2)`です。
N、Mはせいぜい100程度ですので、ざっくり10＾6といったところです。
atcoderでは10＾8より小さい計算量であれば大体間に合うので、この全探索は十分高速といえます。

## 実装
組み合わせの全列挙にitertools.combinationsを使いましょう。
そのほかは上記で説明したことに沿って実装すればOK。

```python:筆者の回答時間：５分
import itertools

n,m = map(int,input().split())
#iさんの曲TのスコアはA[i][T]で取得できます
A = []
for i in range(n):
    A.append(list(map(int,input().split())))

#resultに探索した中での最大得点を記録していこう
result = 0
#ステップ１　組み合わせ全列挙
for conb in itertools.combinations(range(m),2):
    #totalを使ってグループの得点を計算しよう
    total = 0
    #ステップ２　得点計算
    for i in range(n):
        total += max(A[i][conb[0]],A[i][conb[1]])
    #resultに結果を記録
    result = max(total,result)

print(result)
```
初めて記事をしたためたのですが、これはなかなか高カロリーですねえ。
次があればまたお会いしましょう。