microbeの活動日記

プログラミングコンテストとかいろいろ

胎児から始める計算複雑性理論 P≠NP予想編

はじめに

絢辻詞に踏まれたい

 

P≠NP予想とは

P≠NP予想の説明をWikipediaから抜粋すると

P≠NP予想(P≠NPよそう、P is not NP)は、計算複雑性理論(計算量理論)におけるクラスPクラスNPが等しくないという予想である。P対NP問題(PたいNPもんだい、P versus NP)と呼ばれることもある。

わかる人にはそのままだと思いますが,わからない人には全然わからないと思います.ぼくにはわかりません.

そもそもこの説明を理解するにはPやNPなどの用語を理解する必要があるので,最初はこれらの用語から説明していこうとおもいます.

用語の説明

判定問題

判定問題は決定問題とも呼ばれ,入力に対して[1 / 0] や [Yes / No]などのいずれかしか出力しない問題を指します.例を挙げると,整数Nが素数か否かを判定する問題も判定問題となります.

 

決定性チューリングマシン

そもそもチューリングマシンとはなんぞやという話なんですが,
チューリングマシン(機械)は計算模型のひとつで,計算機を数学的に議論するために単純化・理想化された仮想機械のことです.

チューリングマシンは無限の長さを持つテープと有限状態機械(有限オートマトン)から構成され,原理としてはこのようになっています.

チューリングマシンはあらかじめ設定された幾つかの「状態」を持っており、その「状態」とヘッドから読み出したデータの組み合わせによって、「ヘッドをテープ上で一マス移動させる」「テープのヘッドのあるマスにデータを書き込む」「『状態』を変更する」のいずれかの動作を行う。その後、移動後のヘッド位置からデータを読み込み、そのデータと新しい「状態」の組み合わせに従って、次の動作を行う。

 難しそうに見えますが乱暴な言い方をすると,「手順に従ってテープへの読み書きやテープ上の移動とかをやっていくよー」ということになります.この手順がいわゆる”アルゴリズム”と言われるものになります.

特に決定性チューリングマシンとは,入力xに対して出力yが一意に定まっているものを言います.

チューリングマシンは仮想機械のことですが,現代の一般的なコンピュータは決定性か非決定性かは置いといて,このチューリングマシンに基づいて設計されています.言うなればテープがメモリ,有限状態機械がCPUに相当します.

 

非決定性チューリングマシン

チューリングマシンと決定性チューリングマシンについては前述しましたが,非決定チューリングマシンでは入力xに対して出力 yは一意に定まっておらず,状態遷移がその都度,問題を効率的に解けるように選択されていくマシンのことを言います.

 

多項式時間還元

Wikipedeaから概要を抜粋すると

ある問題 A の各問題例を、別の問題 B の問題例に決定性チューリングマシンを用いて多項式時間で変換して答が同じにできるとき、「A は B に多項式時間変換可能である」といい、  と書く。 ただしここでの変換は A の入力内容に依存してはならない。つまり A という問題の全パターンが B に変換できなければいけない。

となっています.わかるか?おれにはわからない.

例えば問題Aの問題例と問題Bの問題例の2つにおいて,問題Aの各問題はすべて問題Bとして捉えなおすことができるとします.その捉えなおす作業を決定性チューリングマシンを用いて多項式時間で捉えなおすことができるとき,問題Aは問題Bに多項式時間変換可能であるといいます.
また,概要にある通り,問題Aの全パターンが問題Bとして捉えなおさなければなりません.

 

P

クラスPは定義によると「判定問題のうち、ある決定性チューリング機械によって多項式時間で解かれるものの全体をPで表す。」となっています.

クラスPを大雑把に説明すると,判定問題のうち多項式(積和で表される式)時間で解ける問題の集合のことを指します.O記法を用いたものだと,O(n^2)は多項式オーダーなので多項式時間で解くことができますが,O(2^n)は指数部に変数を持っており指数オーダーとなってしまい,これはNPというクラスに属します.

問題例としては,ダイクストラ法やオイラーグラフ(グラフを一筆書きできるかどうか)が挙げられます.

 

NP

クラスNPは複雑性クラスのひとつで,Non-deterministic Polynomial time(非決定多項式時間)の略で定義は次の2つになります.

  1. 非決定性チューリングマシンによって多項式時間で解くことができる問題。
  2. yes となる証拠が与えられたとき、その証拠が本当に正しいかどうかを多項式で判定できる問題。

誤解されがちなんですが,NPは多項式時間で解けない問題つまりNot Pのことではありません.

クラスNPを端的に説明すると「答えを見つけるには計算量がどうなるのか分らないけど答えが正しいかどうかを確かめるのは多項式時間で出来るよ」ってことになります.
また,クラスNPも判定問題,つまりはYes/Noで答えられるものでないとそれはNPではありません.

クラスPも多項式時間で解くことができる以上,答えの正しさの証明も多項式時間で出来るためクラスPはクラスNPに含まれます.

問題例はNP完全の説明と一緒に挙げます.

 

NP困難 

NP困難(NP-hard)とは,問題が「NPに属する任意の問題と比べて,少なくとも同等以上に難しい」ことです.定義は「NPに属する任意の問題LがHへ帰着可能である」とされています.何言ってるのかわからないですね.

簡単にまとめると「”少なくとも”NPと同等以上に難しい問題」ということになります.また,NP困難は必ずしもクラスNPに属するかはわかりません.

NP困難な問題の例としては,巡回セールスマン問題やナップザック問題が挙げられます.

 

NP完全

NP完全問題(NP-complete problem)とは,

  1. クラスNPに属する決定問題
  2. 任意のクラスNPに属する問題から多項式時間還元可能なもの

のことをいいます.

簡単に説明するとNPかつNP困難であり,多項式時間還元可能なもののことです.
NP完全はNPの中では最も難しい問題になります.

NP(完全)の問題例としては,3-SATや部分和問題,ハミルトン閉路などが挙げられます.

 

改めてP≠NP予想とは

これらの用語を説明すればあとは初見よりはわかるとは思います.

P≠NP予想とは,NPはPを含みますが,PとNPは等しくないという予想になります.

多くの研究者はP≠NPと信じています.ですが,P=NPと予想する研究者もいないわけではありません.詳しくはググってください.

仮にP=NPが示された場合,指数オーダーアルゴリズムしか見つかっていない様々な問題に対して効率的な多項式アルゴリズムが存在する可能性を示すことになります.

また,予想とあるように,P≠NPはまだ証明されていません.P≠NP予想はミレニアム懸賞問題として懸賞金100万ドル(およそ1億円)がかけられています.

 

まとめ

1億円ほしい.

日本情報オリンピック2017/2018 本選参加記

2/10(土)から2/11(日)につくばで行われた第17回日本情報オリンピック本選に参加してきました.

 

会場までの移動(2/10)

飛行機で関東まで向かいました.あまり飛行機には乗ったことなく耳が痛くてつらかったです.

関東についてから会場があるつくばまでの途中で秋葉原に昼食をとるために寄りました.蒙古タンメン中本に一度は行ってみたいなと思い蒙古タンメン中本まで向かったんですが,行列がすごいことになっていて並んでいたらプラクティスに間に合わないことを悟り適当に店を探して昼食を済ませました.ヨドバシカメラすごかった.

昼食を済ませた後はつくばエクスプレスで会場であるつくばカピオまで向かいます.

 

会場到着後(2/10)

会場に到着したので本人確認や交通費振込申請などの受付を済ませます.
20180210_210836
受付で予選Aランクの楯をもらいました.うれしい.

荷物置き場に荷物を置きに行ったんですがプロたちがたくさんいてこわかったです.

会場についてしばらくすると本選環境に慣れるためのプラクティスが行われました.
プラクティスはそこまでの難易度はなかったので何とか全完しました.4問目がかなり苦手な類だったのでバグらせずに実装出来てよかったです.
らっはプロとプラクティスの最中にエンカしました(問題解いてる最中に話しかけて申し訳ない

プラクティス後はCiscoの方による講演会がありました.詳しい話をすると長くなるので省きますが,情報セキュリティ関係の話でした(Ciscoなのでそれはそう).情報セキュリティにはそれなりに関心があったので講演を聞けて良かったです.

講演会後は夕食も兼ねての交流会がありました.1人1人自己紹介があったんですが名前しか言えなかったうえにコミュ障を拗らせすぎて席の確保さえ困難でした.つらかった.コミュニケーション力大事.

 

本選競技(2/11)

翌日の2/11(日),9:00~13:00の4時間にかけて本選競技が行われました.問題や解答はこちらで公開されています.

結果としては150点,Bランクでした.最初の20分くらいで1問目を解きましたが,2問目の小課題3までは簡単に思いついて部分点をとるために提出して50点を得て以降は満点解法を狙って残りの時間ずっと詰まっていました.他の問題の部分点をとるために時間を回すべきでしたね…

もともと春合宿にいける精進も実力も全く足りないと思っていたので,Bランクをとれただけでも割と満足ではあるんですが最後のJOIともあって少し悔しさが残りますね.

本選後は問題作成者による解説がありました.解説を聞いていた感じだと2問目があと少しのところだったのでさらに悔しさがありました.
飛行機の時間の関係で解説を4問目まで見て会場をあとにしました.

 

最後に

もともと予選さえなぜAランクをとれたのかわからないくらいの精進量だったので本選へ出場できただけでも良い体験になったと思います.
来年度にもSuperConパソコン甲子園などがありますのでもこれ以上に精進していきたいと思います.

日本情報オリンピック2017/2018 予選参加記

本選参加有資格者として参加しました.今年が最後のJOI予選になります.(高校から存在を知った人にはチャンスが2年しか残されてないの罠じゃないですか)

この記事は熊本高専Advent Calendar 11日目の記事も兼ねています.

 

結果

A,B,C,Eの4完 + D部分点で410点でした.3完で終わると思っていたので4完出来てうれしかったです.

 

解説

1問目 鉛筆(Pencils)

問題:
鉛筆をN本以上買うときにA本でB円のセットとC本でD円のセットのどちらかのセットのみをいくつか購入するときの必要な金額の最小値を求める.

方針:
やる
問題文をよく読むとどちらか一方のセットしか買うことができないことに注意する.

gist4cc34e3387c4d0dbae738baa0e552aa6

 

2問目 双六(Sugoroku)

問題:
スタートとゴールを除いて1と0から構成されるN個のマスがあるので,1のマスを踏むことなくゴール出来るサイコロのうち最も面の数が少ないサイコロを求める.

方針:
考察するのが面倒だったので全探索した.
面の数が小さいサイコロから見ていき,出る可能性のある面をすべて再帰で求めていきゴール出来たらそれが答え .計算量が怖いので1を踏んだらそれ以上は枝刈りした.

gist60247aaaa2a52c1e59dfdb998382e5aa

あとから考えたら1が最多くも連続している箇所さえ超えられればいいので最も多く1が連続している個数+1で求まると気付いた.

 

3問目 幹線道路(Trunk Road)

問題:

南北にのびるW本の道路と東西に延びるH本の道路があって各交差点に人が住んでいる.南北,東西にのびる道路のうちそれぞれ1本の計2本を幹線道路とするとき,各交差点から最も近い幹線道路までの距離の総和の最小値を求める.

方針:
どれを幹線道路にするかを決めて各交差点からの距離*各交差点に住む人数をすべての組み合わせにおいて全探索する.O(H^2 W^2)

gistdb0f1ff0fa9465a8fff11b23bf6a3c95

 

4問目 水ようかん(Mizuyokan)

すぐにDPだと察したので部分点(10点)だけとって逃げました.予選終わってから各プロが話してるの見て解いた.

問題:
N本の切れ目がある水ようかんをどこかの切れ目でいくつかに切った時の長さ最大のピースと最小ピースの長さの差の最小値を求める.

方針:
dp[i][j] := i本の切れ目までの切り方を確定し,長さ最大のピースがjであるときのこれまでの最小のピースの最大値.
Lの累積和をとっておくと切った区間の長さをO(1)で求められるので計算量が減る.別にしなくても十分通るだろうけど.

gist91fce8a135515b29a854b7616cc02090

 

5問目 森林伐採(Deforestation)

何とか時間内にACして100点.

問題:
H*Wのマスで森林が構成されていて木が生えていないマスのみ1マス移動するごとに1分で移動でき,木が生えているマスはそのマスに隣接したマスから1分かけて1本切ることができる.北西から南東まで移動できるようになるまでにかかる時間の最小値を求める.ただし,木を1本切るたびに北西まで1度戻らなければならない.

方針:
問題見た瞬間に最短経路問題に帰着できることに気づき,拡張Dijkstraっぽいことをする.
北西から(i,j)までの最小時間とそこまでに行くことができる最小のマス数を持たせておく.すると1本木を切って北西に持って帰るまでの時間も簡単に計算できる.
グラフを構成してもいいけどグリッドでそのままやったほうが考えるのも実装も楽そう.楽しかった.

gistce24420dd3dc1e39657bbc53c74eb421

 

6問目 L番目のK番目の数(LthKthNumber)

部分点も取れなかった

問題:
横一列にそれぞれ数が書かれたN枚のカードが並べられており,連続するK枚以上のカードの列すべてに対して次の操作を行う

  • 選んだカードを,書かれている整数が小さい順に左から並べる.
  • 並べたカードのうち,左から K 番目のカードに書かれた整数を紙に書き出す.
  • 選んだカードを,すべて元の位置に戻す.

これから書き出された整数を昇順に並べた時,L番目の数を求める.

方針:
わかんないや!(放棄)
プロたちによると二分探索でうまくやるといけるらしい.

 

感想

最初にも書いてますが,3完で終わると思ってましたが4完出来てうれしかったです.ただ問題の雰囲気が今までと少し違って感じたので少し戸惑いました.難易度的には僕の感覚では全然わからないですが5問目が楽しかったです.いい加減DP問題を本番中に解けるようになりたいなあ...
ボーダーもさまざまな情報が飛び交ってますが全然予想できなくて怖いですね.400以上は確定と願いたいんですが1度だけボーダー420の年があるので余計怖い.頼むから通っててくれ.

 

余談ですが景気付けにHHKBを購入しました.おかげで気分が高揚してます.

 

 

 

追記(2017/12/14)

Aランク通過してました.

ガウスの消去法をC言語で実装

この記事は熊本高専Advent Calendar 8日目の記事です.

 

本日AdventCalendarに書く人がいなかったため,それを埋めるついでにガウスの消去法をC言語で実装したので紹介しようと思います.

 

ガウスの消去法とは

ガウスの消去法は,連立一次方程式を解くための多項式時間アルゴリズムになります.他に連立一次方程式の解を明示的に表すことができるものとしてクラメルの公式がありますが,クラメルの公式で大規模な問題を解こうとすると計算量が爆発してしまうためあまり計算機で解くことにおいてはおすすめしません.

ガウスの消去法は,前進消去と後退代入という2つの操作からなります.文字だけで見ると少し難しく感じてしまいますがアイデア的には中学数学レベルで解けるようなものでとても簡単です.

 

本当にその場しのぎみたいな記事で,詳しく解説する時間がなかったので詳しいところは以下のサイトを参考にしていただけると幸いです.

ガウスの消去法 - Wikipedia

 

ソースコード

gist2a2c29a2ae3da762f1cb226f9a7a8e10

 

 

ABC078参加記

AtCoder Beginner Contest 078 - AtCoder

ABC078に参加しました.

 

結果

Dを無限にバグらせてギリギリ全完.悲しいね.

 

A

gist030d7267b1b582d853e49093d1b9886f

 

B

gistb59a376415083e6e1db7c67403f838d5

 

C

電卓を使ってサンプルに合うようにいじいじすると式が出てきます.

gist575773c7b7902a815e5e97d1fb9f71fa

 

D

みんな大好きmini-max法
O(1)解法が想定解らしいのですが,僕は天才ではないのでアルゴリズムで殴ることしかできません.

gistea5b66baae10a05b61a0b98e51bda1bc

 

 

こんなんでJOI予選通れるとは思えないのであと一か月無限に精進しなければなりませんね.

しかし後期中間試験まであと1週間しかないため精進する時間があまりとれないので悲しい…

男子高専生は女子高生なのか?

所属している学科にもよりますが,周りに女子が少ない,女子レベルが低い場合は,一番女子に近い存在である男子高専生が自動的に女子高生にランクアップするため男子高専生は女子高生であると言えます.ちなみに僕は女子高生です.

第28回高専プロコン参加記

今年,山口県周南市で行われた第28回全国高等専門学校プログラミングコンテストに競技部門の選手として参加してきました.

 

公式サイトはこちら

第28回大島大会(2017)

いきなりですが成績から

・1回戦(第4試合) 1位通過

・準決勝7位通過

・決勝16位(未完成)

 

1回戦はなんかピースの形がやばくてソルバーが動きそうになかったので配置情報を3つ使用して人力でした.反省してます.(帰ってからソルバー使って解こうとしたけどやっぱりむずかしかった)

準決勝は配置情報2形状情報1を使用してぎりぎり完成で7位

決勝は配置情報1形状情報1でいこうと思ったのですがまさかのソルバーがバグってしまいました.こんなこともあろうかともう1台PCを用意していたのですがUSBハブが不調で周辺機器がつながらず断念し,結局未完成に終わってしまいました.プログラムで負けるのならともかくバグや周辺機器の不調で通常通り競うことができずやりきれない気持ちで決勝を終えました.バグについては後述の反省で.

ソルバーに関しては,傾き・長さが合うものに優先順位をつけてマージさせていく貪欲アルゴリズムです.公開しようかと思いましたが決勝でバグるようなものなので恥ずかしく,公開しません.

 

反省

今回の反省は何よりメンバーと作業分担が出来なかったことです.僕以外のメンバーが4年生でインターンなどによりあまり部活にこれなかったというのもありますが,作業の分担は決めたものの,ほとんどの作業を僕1人でやっておりバグを直す時間が全く足りなくなってしまいました.結局のところは全て僕の責任なのでメンバーには申し訳ないばかりです.

 

これは少し愚痴のようになってしまい申し訳ないですが,僕の所属している部活は全体的に競技部門に対するやる気がほとんどないように感じられます.確かに去年のように完全に人力部門になってしまったようなこともありましたが,それを除いても部員全体の競技部門に対する意識が「課題・自由部門に落ちた時の逃げ道」というものになっているようです.別にそれでもいいのですが,競技部門に出るのであればちゃんとやらないと絶対に勝てません.やるからにはちゃんとやること.これはとても大事だと思います.

 

感想

競技部門に関しては反省することが多々ありますが,大会に参加することはとても楽しかったです.他高専の方と交流もできましたし,らてプロともお話できたので大満足です.個人的に競技部門が一番性に合っているので来年もぜひ競技部門に参加出来たらなと思います.