講義「プログラミングチャレンジ」のまとめ


# はじめに

私は今年から他大から筑波大学院に入った学生、ganariyaです＞＜

[Claus Aranha](http://conclave.cs.tsukuba.ac.jp/)先生によるプログラミングチャレンジに関する授業[「Programming Challgenges」](https://github.com/caranha/Programming-Challenges)は、大学3年生向けに開講されていますが、私が競プロが好きであるため、この授業を受講させていただいています。

内容は

- (第1週) Introduction + Ad-hoc
    - 導入
    - アドホック（問題特有の解き方）
- (第2週) Data-Structures
    - 簡単なデータ構造
- (第3週) Search Problems
    - 全探索や枝刈りなど
- (第4週) Dynamic Programming 1
    - 動的計画法問題
- (第5週) Graphs Part I
    - グラフ問題
    - 橋・関節点
    - DAG
    - 二部グラフ
- (第6週) Graphs Part II
    - グラフ問題
    - 最短経路 dijkstra warshallfloyd bellmanford
    - フロー問題
- (第7週) String Manipulation
    - LCS(最長共通文字列)
    - Suffix Tree
    - Suffix Array
    - 文字列に関するDP
- (第8週) 未定義
- (第9週) 未定義
- (第10週) 未定義

です。

系統だった競技プログラミングの勉強動画は、日本語に関してなかなかないので、とてもありがたく勉強させていただいております。

# リンク

- https://github.com/caranha/Programming-Challenges
- https://www.youtube.com/playlist?list=PLG8uV3QAbSpmdC8vftsJGX9DJKHOeETzs


# UVA

Programming Challengeの授業では、かなり歴史のあるサイト「UVA Online Judge」を使用しています。

そのため

- ジャッジそのものが遅くて不安定
- 問題の形式が悪い
    - 問題文が分かりづらい
    - 制約がきちんと書かれていない
    - 入出力が非常に面倒
- 言語が古い
    - C++11･･･

などの問題が発生し、「問題の難しさ」よりも「問題の理解と入出力」のほうが難しい状態です。

そのため、本記事では動画内で出てくるUVAの問題の簡単な日本語の説明をまとめておくことが目的です＞＜

すでに現在第6週のため、合間を縫って1~5週も更新していきます。
$\LaTeX$が使いたいため、Qiitaでやっていますが、他に良いサイトがあれば（Wiki形式でLaTeXが簡単に使える）そちらに移行したいです。
Wikiだと英語版も簡単に作れそうなので嬉しいのですが･･･（GitHubだとLaTeX使えないのが悲しい）

# 第6週 Graphs 2

## [Wormholes](https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&category=0&problem=499&mosmsg=Submission+received+with+ID+25115573)

$N (\leq 2000)$頂点, $M(\leq 2000)$からなる有向グラフがあります。
$i$本目の辺のコストは$t_i$です。

このグラフの中に、負のコストのサイクルが一個以上存在するか判定してください。

存在する場合は"possible", 一個も存在しない場合は"not possible"と出力してください。

## [Metting Prf.Miguel](https://onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=1112)

若い男と年寄がいる。

26頂点(A~Z)のグラフが与えられる。
辺は$N$本与えられ、各辺は、

- 若い男のみが辺を使えるか？年寄りのみが辺を使えるか？
- この辺は有向か？それとも無向か？

の情報とともに、実際に結ぶ二頂点と辺の移動コストが与えられる。

若い男は、頂点$X$から、年寄は頂点$Y$から、それぞれが通れる辺のみを使用して、同じ頂点に集まりたい。
このとき、若い男の移動コストと年寄の移動コストの合計の最小値を求めよ。
ただし、どうやっても出会えない場合は"You will never meet."と出力せよ。


## [Full Tank?](https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=0&problem=2352&mosmsg=Submission+received+with+ID+25115693)

$N$頂点$M$辺からなる町がある。
この町の$i$本目の無向辺はあるコスト$d_i$が設定されており、この辺を通るためにはガソリン$d_i$が必要である。
$i$番目の町では、$p_i$円を払うことで、ガソリンを1リットルもらえる。

$Q$個のクエリに答えよ。

- 頂点$s_i$にいるあなたは、最大$c_i$リットル入る車を持っている。ここから頂点$e_i$を目指したい。最初車は0であり、うまく各頂点でガソリンを買い,
辺を通ることで、頂点$e_i$に移動する。このとき、移動にかかる最小金額を求めよ。ガソリンが余っても良い。

ただし、どんなにお金をつかっても移動できない場合は"impossible"と代わりに出力する。

## [Degrees of Separation](https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3497)

$N$人の人間がいて、$M$個の関係がある。
各人間は、それぞれ名前が与えられている（文字列、面倒ですね＞＜）

$i$個目の関係は、この二人がつながっていることを表してる。

このグラフの`degrees of separation`とは

- すべての任意の2人のうち、最も長い最短経路の長さ

を表す。つまり、$N$人から選んだ二人のうち最も長い（最短経路の距離）を`degrees of separation`とする。

このdegrees of separationを出力せよ。

ただし、$N$人のうち、知り合いがいない（つまり、連結成分が１でない）ときは、
DISCONNECTEDと出力せよ。

## [Avoiding Your Boss](https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=0&problem=1295&mosmsg=Submission+received+with+ID+25116144)

$N$頂点あり、$M$辺の無向辺がある。
「Y = あなた」は会社をサボった。
Yはあなたの家から市場に行って買い物をしないといけない。
ただし、上司も家にいて、会社に出勤するため、この上司に出会いたくない＞＜


上司は、家$BH$にいて、会社$OF$に最短距離で移動する。
家$BH$と会社$OF$の最短距離上にある頂点と辺は、Yは通ることが出来ない。（Yが通ると上司にバレてしまうため＞＜）

Yも短絡的なので、Yの家$YH$から市場$M$に最短距離で移動するとする。

家$YH$から市場$M$に最短距離で移動するときに、もしどうやっても「上司が家$BH$から$OF$に最短距離で移動するときの頂点と辺」を通らないといけないならば`MISSION IMPOSSIBLE.`と出力せよ。
もし、家$YH$から市場$M$まで最短距離で移動できるならば、その最短距離を出力せよ。


## [Software Allocation](https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=0&problem=195&mosmsg=Submission+received+with+ID+)


あなたが所属する研究室には、`A~Z`のアルファベット名が付けられた26個のアプリケーションがあり、これらのアプリケーションを使いたい研究室のメンバーがいる。

研究室には、10台のコンピュータ(0~9)があり、それぞれ使えるアプリケーションが決まっている。

このとき、研究室のメンバーがそれぞれアプリケーションを使いたいとき、全員を上手にPCに配置して、アプリケーションの要望を満たせるか答えよ。

例えば、

```
A4 01234;
Q1 5;
P4 56789;
```
という入力であれば

- Aというアプリケーションを使いたい人間は4人いて、01234の5台のパソコンでAを使える
- Qというアプリケーションは1人いて、5という1台のパソコンのみ
- Pは4人使いたい、5台(5, 6, 7, 8, 9)

である。

このとき、`AAAA_QPPPP` (0台目A, 5台目はQといったアプリケーションの割当)で全員の要望を答えられる。


もし、例えばアプリケーションを使いたい人間が11人いる場合や、うまく全員に配置できない場合は`!`と出力する。

## [Sabotage](https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1421)


$N$個の頂点と$M$個の辺がある。

$i$本目の辺は頂点$a_i, b_i$を結び、コスト$c_i$である。

あなたは、頂点$1$と頂点$2$を完全に分離したい。(頂点$2$であることに注意、Nとかではない)
そのために、いくつかの辺を完全に断ち切る。

このとき、$1$と$2$を完全に異なる連結成分にするために必要な最小の断ち切る辺の集合を求めよ。ただし、どの順で出力しても良い。