# アルゴリズム サンプル問題
**注意事項**
このサンプル問題は，本講義の期末試験で出題される問題のフォーマットを例題を通じて示すものです．どのような形式で本講義で学んだことを問われるか，の参考にしてください．
**==このサンプル問題は，大問・小問の数，出題範囲，問題の難易度を規定するものではないことに留意してください．==**
<br>
---
# 試験時の注意事項（問題冊子の表紙に記載予定）
以下の内容は変更されることがあります．当日の注意事項に関する指示をよく読むようにしてください．
- 本冊子上部に，学籍番号，名前を間違いなく明瞭に記入すること．
- 試験中はマスクを着用すること．
- 本冊子には解答欄が含まれており，指定された部分に解答を記すこと．解答はどのような順番で行ってもよいが，指定された場所に記入すること．誤った場所に書かれた解答は採点されない．
- 本冊子は切り離してはならない．切り離した部分の解答は無効となる．
- 自然言語，擬似コードによる解答では日本語，もしくは英語を使用すること．
- pythonによる解答では必要に応じてコメントを添えること．
- 採点者が誤解なく読むことができるように，解答は丁寧に記載すること．明瞭・丁寧に記載されていない解答は採点されない．
- 試験の録画，録音を行ってはならない．
- 監督者の指示に従うこと．
- 監督者に申し出ることがあれば，挙手をして監督者に知らせ，監督者の指示を仰ぐこと．
- 不正行為が発覚した場合，本試験の採点は行わず，現在までの課題提出状況に関わらず，成績を不可とする．特に悪質なものはさらなる処分の対象となり得る．特に以下のような行為は発見し次第，即座に不正行為とみなす．
- 持ち込みが許可されている筆記用具，時計以外の電子機器，参考書，補助ツール等を使用した．
- 他者と連絡・やり取りをした．
- 監督者の指示に従わない．
- 他の受験生の受験を阻害する行為を意図的に行った．
- 内容に関する質問には答えない．問題の指示が曖昧だと考えられる場合，適切な仮定を自身で設定し，その仮定を解答内で説明すること．
- オンラインで受験をする者は，別途指示された方法により受験環境を準備すること．必要な準備ができていない場合，受験を認めない．
<br><br>
# 大問（正誤判定）
以下の各問の記述が正しいかどうかを答えてください．正しい記述であれば解答欄に「**正**」とだけ書いてください．誤った記述であればどのような誤りかを簡潔に自然言語で説明してください．
<br>
#### 問A．与えられた配列の長さが$n$である時，クイックソートの時間計算量は，平均的な場合$O(n \log n)$である．
> 正
#### 問B．与えられた配列の長さが$n$である時，線形探索の時間計算量は，平均的な場合$O(\log n)$である．
> $O(n)$である．
#### 問C．照合対象の文字列の長さが$n$，パターンの文字列の長さが$l$である時，文字列照合の力任せの空間計算量は，平均的な場合$O(l)$である．
> $O(1)$である．
#### 問D．連結グラフにおけるダイクストラ法では最大ヒープを利用することにより，平均的な場合における時間計算量を$O((|E|+|V|)\log(|V|))$程度にすることができる．ただし，$|V|, |E|$はそれぞれグラフにおけるノードの総数，辺の総数をそれぞれ表す．
> 最大ヒープではなく，最小ヒープを使う．
#### 問E．トポロジカルソートのソート結果は，与えられる有向グラフに対して一意に決まる．
> ソート結果は複数あり得る．
<br>
<br>
# 大問（記述式）
以下の小問に関して，答えてください．
#### 問A．シェルソートについて知っていることを自然言語で説明してください．必要に応じて擬似コードや数式を使用しても構いません．
> 間隔の離れた要素の組に対して挿入ソートを行い，この間隔を順次小さくしながら挿入ソートを繰り返す．これにより，間隔が小さくなるにつれ，ほぼソートされている列が出来上がると期待でき，単純な挿入ソートよりも高速に動くことがで期待できる．時間計算量としては与えられた配列の長さが$n$である時，$O(n^{1.5})$や$O(n^{1.25})$になるものが知られており，どのように間隔を設定するかによって依存する．
<br>
<br>
# 大問（コーディング）
Kojiさんは与えられた整数の配列```seq```（長さ：$N$）において，「$k$倍分割」できるかどうかを調べたいと思っています．この$k$倍分割とは，ある$i (0 \le i \le N-1)$を用いて，
- 左部分列：seqの要素[0, i)の連続する部分列
- 右部分列：seqの要素[i, N)の連続する部分列
に分割したときに，
```
k * [左部分列の総和] = [右部分列の総和]
```
が成立する分割の仕方を指します．
Kojiさんは，もし$k$倍分割できる場合は最も小さい$i$を，そうでない場合は，-1を返すプログラム```KDivide```を書くことにしました．ただし，以下に示すような制約条件があります．
```python
def KDivide(seq, k):
# この部分を考える
return [最も小さいiか-1を返す]
```
この問題に対して，以下の小問に答えてください．
---
**制約条件**
- $1 \le N \le 10^7$
- $-10^7 \le seq[i] \le 10^7$
- $1 \le k \le 10^4$
- pythonのリストの基本関数（min，max，sum等）を使用することはできない．
---
**入力例1**
```
KDivid([1,2,6], 2)
```
**出力結果**
```
2
```
$1+2 = 3$で，2 * [左側の部分列の総和] = [右側の部分列の総和]が成立するので，$i$の値2を返します．
**入力例2**
```
KDivid([1,2,8], 2)
```
**出力結果**
```
-1
```
どのように分割しても2倍分割できないので，-1を返します．
**入力例3**
```
KDivide([-5,6,-4,2,7,-1,13,-2,14], 4)
```
**出力結果**
```
５
```
<br>
---
#### 問題A. Kojiさんはこの問題を解くために以下のような擬似コードで表されるプログラムを実装しました．
```python
def KDivide1(seq, k):
[iが0からN-1までのループ]:
[ループで左部分列の和を計算]
[ループで右部分列の和を計算]
if [k倍分割になる]:
return i
return -1
```
このプログラムの平均的な時間計算量を$N$，$k$，あるいはその両方を用いて表してください．さらに，その計算量になる理由を簡潔に自然言語で説明してください．
> $O(N^2)$．1つ目のループが$(N)$，部分列の和を計算するループが合わせて$O(N)$，よって，それらをすべて合わせると，$O(N^2)$．
<br>
#### 問題B．Kojiさんは最初はこのプログラムに満足していましたが，$N$が大きくなると遅くなることに気が付き，改良することしました．平均的な場合における時間計算量が問題2-Aのプログラムよりも小さいコードをpythonで示してください．また，そのコードの平均的な場合における時間計算量を示してください．
> 部分列の和を毎回計算するところが非効率なので，そこを改良する．$O(N)$．
```python
def KDivide2(seq, k):
left = right = 0
for i in range(len(seq)):
right += seq[i]
for i in range(len(seq)):
if k * left == right: return i
else:
left += seq[i]
right -= seq[i]
return -1
```
Sign in with Wallet
Connect another wallet