LL(1)文法、字句解析、構文解析の感覚的説明

言語処理系についてのあいまいなことのまとめと整理

　こんにちは、くりすぷです。今回は自分用にメモ。授業の言語処理は論理的にはわかるけど、感覚的には意味不明、わけわかめだから、整理。

字句解析と構文解析

　「解析」はGoogle検索で出てきた一番上の定義だと

事柄を細かく分けて、組織的・論理的に調べること。

だけど、コンピュータ自体、秩序(組織)・論理的なので、

字句解析

プログラム→単語群(複数の形態素)　へと変換

構文解析

単語群は構文規則に当てはまっているか2値分類

と整理できる。 かなり大雑把にいうと、ここでの解析は分類です。

LL(1)文法とはなんぞや

　LL(1)文法とは下向き構文解析において最左導出によるアルゴリズム。

※これは定義ではなくインスタント説明です。詳細な定義についてはググりましょう。

ある文字列を生成規則に適用しまくってある文字列を作ることが導出なんだけど、最左導出というのがその適用の仕方がとりま左から適用していくよというやつです。下向き構文解析は下向きにもりもり構文木をつくっていく感じです。

---

余談

名称の由来の推測

LL(1)の由来は(少しググってもよくわからない、ググる気がなかったので推測)多分LanguageLeft(1)を略したものだと思います。１というのはググった結果、先読みしても良い文字数らしいです。 ソース はこちら。

その根拠は方法の名称には、人の名前か、あるいは、何がやりたいのか簡潔に示しているものなので、似たようなものにLR(1)法というのがあるんですが、そこから考えると、人名ではなさそう。それでいて、明らかにLとRとか、これは右と左の対応だよね、さらに、対象が言語だから、ということです。

個人的には語源というものは、よくわからないものについては、学者がこんな感じじゃねともっともらしい根拠を付けて説明していることも多々なので、生活レベルとしては自分に納得できる説明ができればいいかなと思っています。覚えやすさ重視。正しさなんてよくわからないからね。

余談終わり

---

LL(1)文法の中身

よくある言語の定義(文法、記号列)に加えて、First（終端、非終端記号含む文字列　→　終端記号）、Follow（非終端　→　終端）、 非終端 → 文字列という遷移ができるとき、Director(遷移に必要なもの、具体的には、非終端と終端　→　終端記号)が定義されていて、このDirector関数について条件があるんですが、それは、ある非終端記号に限定したとき、任意の遷移先に対して、Director関数を適用したとき、タブリがない、ということです。

さて、この関数は順に感覚的に説明すると、Firstが文字列を入力されたときその文字を遷移させていったとき文字列の一番左に来る可能性のある終端記号たちを返す関数、Followは入力の隣にくる終端文字を返す関数で、Directorは入力のように遷移させたときに一番左に来る可能性のある終端記号を返す関数です。

この情報から、先ほどのLL(１)文法に感覚的に特徴づけると、それは左から読むと誤解のない文法というわけです。読むというのは、解析で、誤解のないというのは、ダブりがないということです。

おしまい。

Math Enjoy Contest

  こんにちは、とぼです。今日は完全に趣味で,算数・数学・パズル関連の問題セットを作りました。エンジョイ勢の作った問題セットです！

　問題はかなりくだけた雰囲気のものを多めにしました。難易度は、完全にAから順に難しくなっていくわけではないですが,後半の方が難しいものが多めです。ただ,問題セットの難易度は比較的取り組みやすいものを多くしています。

　「見た目難しくても,やってみると意外と簡単！」

という問題も多いので是非やってみてください。

　解いてくれた方はコメントで解けた問題の解答を送ってください！

　２週間後に解答を公開しますが、コメントはそれまで非公開にします。

★Math Enjoy Contest

全13問 : 制限時間(目安) 2時間30分 (オーバーしてもOKです)

A. 反転数

　ある３桁の自然数abcがあります。

　とぼ君はこの数の一の位aと百の位cを入れ替えた数cbaと元の数abcを足すとちょうど3桁のゾロ目である数になることに気が付いて一人で喜びました。

　つまり、  abc + cba = ddd となります。(a,b,c,dは各位の数を表しています)

　このような3桁の自然数abcは何通りありますか。

B. 宇宙人

 　宇宙人が合計128人襲来しました。優秀なカメラマン富岳氏がこの宇宙128人全員を全身捉えた写真を収めることに成功し、これをYMUR新聞社に送りつけました。

　後日YMUR新聞社の記事に掲載された富岳氏の写真を見た宇宙人マニアの冬木君は、この宇宙人は足の数によって２種類の宇宙人「ゴモモ星人」と「ムルル星人」に分類できることを発見しました。冬木君の発見した情報は以下の３つです。

　・「ゴモモ星人」の足の本数は必ず32本である。

　・「ムルル星人」の足の本数は必ず64本である。

　・今回襲来してきた宇宙人128人の足の本数の合計は5504本である。

　さて、今回襲来してきた宇宙人のうち「ゴモモ星人」は何人いるでしょうか。

C. 9で割れるパンデジット数

 　0以上9以下の数字が各桁に１回づつ出現する１０桁の自然数を「パンデジット数」と呼びます。0が最上位に来てはいけないことに注意すると、9で割り切れるパンデジット数はいくつあるでしょうか。

D.　DDD大王の野望

　計算が苦手なDDD大王は自国の円周率を３にしてしまおうと考えました。これで円の面積の計算も楽勝です。

　しかし、物知りフームはこれに猛反対。フームは

「もし円周率を３にしたら円周の長さがそれに内接する正６角形の周の長さと同じになってしまうわ」

　と反論しましたがDDD大王は、

　「ワシは面積の計算が楽になればそれでいいんだぞい。ホレ、円周率を3にしても、円と正六角形の面積は違うゾイ！！」

　といい訳しました。フームは思わず

　「ぐぬぬ...,なんて暴論なのかしら...」

  とあっけにとられて押し黙ってしまいました。フームを助けるべく、円周率を3と仮定した場合に円の面積と等しくなってしまう、円に内接する正多角形を求めてあげましょう。

E.計算ミス

　整数a,b,cを用いた計算『a+b×c』は、当然b×cを先に計算します。しかし、ぼと君は昨夜徹夜したため寝ぼけていたので、a+bを先に計算してしまいました。その結果、本来の答えよりも60だけ計算結果が大きくなってしまいました。困った、困った。

　さて、このような(a,b,c)の組み合わせは何通りあるでしょうか。

　まあ、ぼと君にはよく寝てもらうとしましょう。

F. 世界のFizzBuzz

  3の倍数と3のつく数を読み上げるときにボケる「世界のアツナベ」,5の倍数と5のつく数を読み上げるときにボケる「宇宙のツナベア」の２人が,1から1000まで順に整数を読み上げていきます。2人がともにボケるような整数はいくつあるでしょうか。

G. Gaint Integer

  99⁹⁹以上100¹⁰⁰以下の整数はいくつあるでしょうか。答えは大きすぎるので、その下３桁を答えてください。

H.一筆書きボードゲーム

  m×nマスの長方形型ボードがあります(横mマス、縦nマス)。このボードを使い、以下のルールで遊ぶ「一筆書きボードゲーム」をします。なお、このゲームは一人用なのでぼっちでも楽しめます。

<ルール>:

 右からa番目、下からb番目のマスを(a,b)と記します。

 まず、1つの駒をボードの最右下のマス(1,1)におきます。

駒をタテ・ヨコに隣接するマスへ移動させていき、すべてのマスを１回ずつ通って最後に最左上のマス(m,n)にたどり着ければ「ゲームクリア」です。

　さて、m,nを１以上1000以下の整数とするとき、「ゲームクリア」可能な(m,n)の組み合わせは何通りあるでしょうか。

I. 狂気のKIRA

　ある独裁国家KIRA王国。その国の国王がKIRAさんです。

　この国のとある監獄「ローライト」に、１から600までの整数番号が割り振られた600人の死刑囚がいます。KIRA国王は少し気がふれているので、とある順番で死刑執行を行い、最後に残った２人は免罪にするように死刑執行人に命じました。その順番とは以下の恐ろしいルールに従います。

＜ルール＞：

　生き残っている死刑囚を割り振られた番号の若い順に右から左へ１列に並べる。そして、右から数えた順番が３の倍数である死刑囚を全員処刑する。以上を死刑囚が残り２人になるまで繰り返す。

　さて、この恐ろしいルールで処刑によって最後に処刑される不幸な死刑囚に割り振られた番号の和はいくつでしょうか。

J.立対角線

 「立対角線」とは、立体の２頂点を結ぶ線分であって、立体のいずれの面にも含まれないものをいいます。正１２面体の「立対角線」の本数を求めてください。

K.不思議な数列

　 A₁=1,

    An＝１＋（1/An-1）：（nは２以上の整数）

とするとき、An の一般項を直接求めるのは難しいですが、ある知識を持っている方なら以下の問題を解けばわかるかもしれません。

 [問] lim[n→∞] (An) を求めてください。

L.失われた幸福

　幸福の失われた123456890年後の世界では幸せの象徴である数字「7」が使用禁止になりました。この世界では、整数を0から順番に数えていくと

　0, 1, 2, 3, 4, 5, 6, 8, 9, 10 , 11 , 12 , 13 , 14 , 15 , 16 ,18, 19 ,20,...,69, 80, ...

 というようになります。

 すなわち、通常の我々の世界での10進法表記でNとあらわされる数がこの幸福レスな世界でd(N)とあらわされるとするとき、

　d(6)=6, d(7)=8, d(8)=9, d(16)=18 ...

のようになります。

　d(7777)を求めてください。

M.不思議なパーティ

 くりすぷ君は自分を含め1001人が参加する「ミステリ・パーティ」に来場しました。そこでしばらくの間まわりを観察していると、驚くべき以下の事実に気が付きました。

＜事実＞：

　1以上1000以下の任意の整数iに対して、自分以外の1000人のうちいずれか一人の「このパーティにおける知り合いの人数」がちょうどi人となる。

　なお、一方的な知り合い（AさんがBさんの知り合いであって、かつBさんがAさんの知り合いでない)は存在しないものとします。このパーティにおけるくりすぷ君の知り合いの人数を求めてください。

[問題終わり]

最長増加部分列(LIS)の期待値についての考察(その2：本題、LISの期待値)

　こんにちは、とぼです。今回の記事は、前回記事が長くなりすぎた最長増加部分列(LIS)問題の期待値に関する考察の続き...もとい本題です。

　 LISについては前回の記事でめっちゃ詳しく書いたので、(もしご存じでない方がいれば)(むしろプロがこの記事を見かけてくれたら、むしろさすまた投げてください。)

yadrfu.hatenablog.com　では早速、LISの期待値に関する考察をします！！　

本題：LISの期待値

 丁寧に書いていたら、多分前書きの方が長くなったんですが、ここから本題(?)。Twitterで「整数1~nのランダムな並び替えのLISの期待値」はnに対してどのような挙動をとるのか、という話題が上がっておりまして、大変興味深かったので、少し実験をしてみました。

　少し実験してみましょう。以下、1～nのLISの期待値をEL(n)と書くことにします。

  （１）n=1のとき、EL(1)=1は自明。

  （２）n=2のとき、数列が{1,2}ならLIS=2,{2,1}ならLIS=1なので、EL(2)=(1+2)/2=3/2。

  （３）n=3のとき、数列が{1,2,3}でLIS=3,数列が{3,2,1}でLIS=1,それ以外ではLIS=2と なるのでEL(3)=(1+3+2*4)/6=2。

  （４）n=4のときは...,うーん手計算では難しい(面倒)！と、いうわけでネクパ

    (next_permutation。詳しくはProject Eulerの記事その３

yadrfu.hatenablog.com

を参照。)を使って、各組合せに対しLISを求め、（脳筋全探索で）期待値を求めてみましょう！！

以下のような脳死コードを書きました。

#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <cmath>
#include <set>
#include <map>
#include <string>
#include <numeric>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <iterator>
#include <cstring>

using namespace std;

#define rep(i, a) for (int i = 0; i < a; i++)

//ユークリッドの互除法
ll gcd(ll x, ll y) {
    if (x < y) swap(x, y);
    if (y == 0) return x;
    return gcd(y, x%y);
 }

//最長増加部分列の長さの計算
int LIS(vector<int> V) {
     int DP[11] = { 0 };
     fill(DP, DP + V.size(), INF);
     rep(i, V.size()) {
        *lower_bound(DP, DP + V.size(), V[i]) = V[i];
     }
    return lower_bound(DP, DP + V.size(), INF) - DP;
 }

int main()
{
    rep(i, 10) {
        vector<int> V(i+1);
        iota(V.begin(), V.end(), 0);
        int nEx = 0;  //期待値分子(EL(n)の分子)
       do {
             nEx+=LIS(V);  //期待値分子の加算
        } while (next_permutation(V.begin(), V.end()));
        int All=Kaijou(i + 1);   //期待値分母=n!
        int t = gcd(All, nEx);  //最大公約数求めて約分
        nEx /= t; All /= t;  //約分
       cout<<"n:"<<i+1<<", Ex:"<<nEx<<"/"<<All<<endl;  //EL(n)を分数表示
    }
   return 0;
}

   唯一工夫した点は、期待値を浮動小数形式ではなく、ユークリッド互除法によって既約分数形式で表示させるようにしたところです。あとでこの工夫が活きてくることになるとは、このとき思っていなかった。

　実行結果を以下に示します。

　以上のようにn=1~10までのEL(n)を導出できました。これ以上は実行時間が長くてダメですね(まあ、n=12くらいまでは数分レベル待てばできるとは思うが)。

　で、法則を見つけようとか、nと増加量の関係とか考えようとしましたが脳死していたのでよくわかりませんでした。(2016がいてちょっと喜ぶくらい)

　そこで　""　つ「オンライン整数列大辞典(OEIS)」 !!!!   ""

折角分数表示したので、各EL(n)の分子{1,3,2,29,67,2261,499,7601,163673,3146141}をOEISにぶち込みます。

　で、見事ヒットします。OEISマジで整数列ならなんでもあってヤバイ（語彙力）。

　さらに、よく見ると...

...ん？どこかで見覚えのある分数列が...

あっっっ！！！！

まさにEL(n)ですやん...。OEISやべぇな。（語彙力)

というわけで、手元では（現状のアルゴリズムでは）計算困難なn=21までのEL(n)の値を得ることができました。

これをExcelにぶち込んで、nとEL(n)の関係を表すグラフを描いてみました。下図の青実線がnとEL(n)の関係を示すグラフで、赤点線が、それをもとに推定させた近似曲線です。近似曲線のパターンを「線形」、「対数形」、「累乗形」と試したところ一番フィットした「累乗形」を採用しています。下図に示すように

　　　　EL(n) = 0.9972n ⁰・⁶³⁴⁹ ≒ n ⁰・⁶³⁴⁹

の近似曲線を得ることができました。

 　しかしながら、OEISにさえFOMULAが載ってなかったので、正確なEL(n)の一般解を求めるのは困難と思われます。

　まあ今回は近似曲線を求めることができたので個人的には満足です。

　現場からは以上になります。

人工知能のまとめ(人工知能の現代の定義とそれに至る過程の概観)

　こんにちは。くりすぷです。人工知能についての授業を受けたのですが、結構哲学的なので、整理のためにメモしていきます。 ※これは個人が授業で学んだことをまとめたものなので違和感や間違いなどあれば指摘した抱ければ幸いです。

---

はじめに

　人工知能という分野は分類するといろいろあるらしいので、自分がとった授業は人工知能の概観という感じらしい。具体的には人工知能の基本や考え方について学ぶ。まとめたものと自分の考えたことと共に提示していきます！

人工知能といろいろ

人工知能の研究目的

　はじめ、人工知能の目的として、認知科学の面でいえば、人間はどうやって認識するのかを理解するためで、哲学の面でいえば、人工知能という技術を用いた哲学的な問題の探求のためで、計算機科学の面でいえば、計算機にスマートに計算をさせるためがある。

人工知能の当初の目的は人間の知性を多面的に解明するためとまとめられる。

知能(知性)をどのように捉えるか

辞書的な意味での知能の定義 はリンクの通りだけど、何ができたら知能があると呼べるのかという問題がある。それに対して、人間の決定や判断(外的である行動と内的な思考)と合理性の2つの観点がある。その観点には人工知能が人間をどこまで真似るのかという観点が共通している。ただ人間は時に合理的に動けば時に感覚的に動いているため、AIの目的は、現在、2項対立的な、２つの観点の程度の組み合わせ４つから、複合的に捉えていくことにより知性を追究していくことである。合理性という視点で観点を2分割したときに、考え方として強いAIと弱いAIがある。

様々な研究を経て

　現代の人工知能とは、そういった多面的なことが考慮された知性を考えて、知的に行動する合理的エージェントである。

---

というわけで、流れを意識してまとめてみました。感想としては大学の授業スライドは流れを意識しづらいです。どこまでが文脈の句切れかわからないですね。このように定期的に文脈を意識してまとめていきたいと思います。

最長増加部分列(LIS)の期待値についての考察(その１：LISの導入)

　こんにちは、とぼです。

　最近、とても眠いです。1日に10時間くらい寝てしまう。これも春の影響でしょう　か。新しい年度の始まる春ですから、もう少し気を引き締めていきたいものです。

　さて、今回は動的計画法の定番問題LIS(最長増加部分列)の関する話題です。

　完全に個人的な気分で書きます。メモ代わり。

　でも、なるべく詳しく、分かりやすく書けるよう頑張ります。

そもそも、最長増加部分列(LIS)問題とは？

　日本のオンラインジャッジサイトで最大級のAOJ（Aizu Online Judge）に典型的な最長増加部分列の問題が掲載されています。

　例として、

　A={ 1, 2, 0, 3, 2, 5 }

という数列を考えてみましょう。

　この数列から、順番を変えずにいくつかの数字を取り出したものを「部分列」といいます。

例えば、この数列から、左から1,4,6番目の数字を取り出すと

　1, 3, 5

という長さ３の部分列を得られます。この部分列は、左から右に向かって数字が大きくなっています。

つまり、1 < 3 <5 ですから (一番目の数字) < (二番目の数字) <(三番目の数字)

となっています。

このように、左から右に向かって数字が大きくなっている部分列のことを「増加部分列」といいます。

　一方、この数列から、左から1,2,3,4番目の数字を取り出すと

　1, 2, 0, 3

という長さ４の部分列を得られます。この部分列は、２番目の数字「2」から３番目の数字「0」にかけて数字が減ってしまっています。従って、これは増加部分列とはいえません。

　また、左から1,2,4,6番目の数字を取り出すと

    1, 2, 3, 5

となります。この部分列は左から右に数字が増加しているので「増加部分列」であるといえます。また、この増加部分列の長さは４であり、これより長い増加部分列は存在しないことが分かります。よって、数列Aの「最長増加部分列 = Longest Increasing Subsequence(LIS)」は「1, 2, 3, 5」であり、その長さは４であるといえます。

　このように、与えられた数列の最長増加部分列の長さを求める問題を「最長増加部分列(LIS)問題」といいます。

最長増加部分列(LIS)問題を解こう！

　では、最初に掲示したAOJの問題を考えてみましょう。制限時間は１秒です。「制約」を見てみると、数列の長さnは１以上100,000=10⁵以下であることが分かります。

　一般的なPCやオンラインジャッジで１秒間で計算できる演算量はおおよそ10⁸回であることが知られています。ですから、長さnの数列に対しておよそn²回の演算をするとn=10⁵のとき、n²=10¹⁰（回）の演算をすることになってしまい、10⁸を優に超えてしまうので、O(n²)の（=n²に比例する演算回数の)　アルゴリズムでは時間に間に合わないことが分かります。

　一方で、対数log(n)を計算するとlog(10⁵)=11.51..になることが分かり、

10⁵log(10⁵)≒1.151×10⁶ < 10⁸ となるので、O(nlog(n))のアルゴリズムであれば制限時間１秒に余裕で間に合いそうだと考察できます。

　つまり、LISを求めるO(nlog(n))のアルゴリズムを考えればよさそうです。

＜LISのアルゴリズムの考察＞

　長さnの数列Aから数字をいくつか取り出して部分列を作る方法を2ⁿ通りあります。（n個の数字それぞれに対して、部分列の要素として「選ぶ」か「選ばない」かの２通りが考えられるからです。）

　従って、全探索の計算量はO(2ⁿ)となり、全く間に合わないことが分かります(2¹⁰⁰⁰⁰⁰ ≒ 10³⁰⁰⁰⁰)。

　そこで、配列を用いて計算結果をメモリに記録し、繰り返しの演算を避ける「動的計画法 = DP」を用いて解くことを考えます。

　例えば、上手いDPを作って、各要素i=1～nに対して、O(n)で要素iを含むようなLISを求めたとします。しかし、このようなDPの計算量は n×O(n)=O(n²)となるので、前述の議論により結局間に合わないと考えられます。O(nlog(n))でないと間に合わないのです。そもそも計算量にlog(n)が出てくるのはどのようなときでしょうか。

　結論から言うと、計算量にlog(n)が含まれるようなアルゴリズムは「二分探索」が用いられることが多いです。「二分探索」では、配列の要素を真ん中から順に条件を満たすかそうか判定していき、その結果によって次に調べる要素を上位半分の真ん中の要素にするか下位半分の真ん中の要素にするかを決定します。このようにすると毎回探索の範囲が1/2になるので、およそlog₂(n)=O(log(n))の計算量で1回の探索を終えることができます。ただし、「二分探索」は基本的に整列済みの配列（数値が大きい順や小さい順になっている）にしか適用できません。

　二分探索を組み合わせることで、要素i=1~nに対してO(log(n))でLISを求める上手いDPが作れれば、全体の計算量がn×O(log(n))=O(nlog(n))となり、時間内に問題が解けそうだと分かります。

　では、これを実現することで知られているDPを紹介します。なお、言語はC++です。C++の便利な関数をいくつか使っていきます。：

　以下のような配列を用意します。

DP[n] : DP[i]は長さがi+1である増加部分列の最後の(一番右の)要素となりうる最小値(存在しなければINF＝便宜的に無限に大きい値)

　このとき、配列DPは明らかに単調増加する（部分増加列が長くなるに連れて、増加部分列の最後の要素は確実に大きくなる）ので、数値は小さい順になるため、二分探索が適用できることが分かります。

　まず、配列DPの全要素をINFで初期化します(fill関数が使える)。

　次に、数列Aの1番目の要素A[0]から順に、二分探索によってA[i]以上の値をもつ配列DPの最小のインデックス（一番左の要素)を探し、そのインデックスをもつDPの要素の値をそのままA[i]に更新します(lower_bound関数で二分探索ができます)。これによって更新された(値がINFでなくなった)、

「(DPのインデックス)＋１」の長さの増加部分列は構成可能であって、

逆に数列Aの全要素に対して以上の操作を行った後も値が依然INFであるようなDPのインデックスの意味する長さの増加部分列は構成不可能であるということになりますから、「数列Aのすべての要素に対して以上の操作を行った後に値がINFでなくなったDPのインデックスの最大値(一番右にあるやつ)＋１」が数列AのLISであると分かります。

　ちょっと文面だけでは分かりにくいので、具体例として最初に提示した数列

　A={ 1, 2, 0, 3, 2, 5 }

に対して上記のDP配列を埋めていきましょう。

　最初はDP配列の各値はINFになっています。

　A[0]=1ですから、A[0]より大きい値を持つ最小のインデックスのDPはDP[0](=INF)です。よって、DP[0]=１に更新します。

　次にA[1]=2ですから、A[1]より大きい値を持つ最小のインデックスのDPはDP[1](=INF)です。DP[0]の値は今１なのでA[1]=2より小さくなっていることに注意です。これより、DP[1]=2に値を更新します。

　次A[2]=0ですから、A[2]より大きい値を持つ最小のインデックスのDPはDP[0](=1)です。よってDP[0]=0に更新します。

　このような操作を繰り返すと、以下表のようになります。

Aの数値	DP[0]	DP[1]	DP[2]	DP[3]	DP[4]	DP[5]
(最初)	INF	INF	INF	INF	INF	INF
1	1	INF	INF	INF	INF	INF
2	1	2	INF	INF	INF	INF
0	0	2	INF	INF	INF	INF
3	0	2	3	INF	INF	INF
2	0	2	3	INF	INF	INF
5	0	2	3	5	INF	INF

　この表により、最終的な値がINFでないDPの最大のインデックスは3であるので、

求めるLISは3+1=4であることが分かりました。この結果が冒頭で計算したものと確かに等しくなっていることも分かります。

　以上から、このDPが正しく動作することが分かるので、あとは実装するだけです。以下のようなシンプルなコードで実装できます。

//最長増加部分列の長さの計算
int LIS(vector<int> V) {
    int DP[MAX_n] = { 0 };
    fill(DP, DP + V.size(), INF);   //DPの各値をINFで初期化
    for(int i=0;i<V.size();++i)
        *lower_bound(DP, DP + V.size(), V[i]) = V[i]; //V[i]を超える最初のDPに代入
    return lower_bound(DP, DP + V.size(), INF) - DP; //INFでない最大index+1
}

  なお、 MAX_nは数列Aの要素数として考えられる最大値を示します。先の問題ではMAX_n=100,000ですので定数constとして宣言しておけばOKです。

  これでAOJの問題を解けます。

  実際に今私が書いたコードを以下に示します。

 

#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <cmath>
#include <set>
#include <map>
#include <string>
#include <numeric>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <iterator>
#include <cstring>

using namespace std;

const int INF = (1<<30);
const int MAX_n = 100000;

//最長増加部分列の長さの計算
int LIS(vector<int> V) {
     int DP[MAX_n] = { 0 };
     fill(DP, DP + V.size(), INF);
     for (int i = 0; i < V.size();++i) {
        *lower_bound(DP, DP + V.size(), V[i]) = V[i];
     }
    return lower_bound(DP, DP + V.size(), INF) - DP;
 }

int main()
{
    int n;
    cin >> n;
    vector<int> A(n);
    for (int i = 0; i < n; ++i) cin >> A[i];
   cout << LIS(A) << endl;
   return 0;
 }

 

　このコードでACできます。Aの要素の最大値が10⁹ということで、INF=(1<<30)、つまり2^30にしました。LIS(A)って部分、アニソン感あって良くないですか？（は）

　...長くなりすぎたので、今回はLIS問題の導入ということで。あまり記事が長くなると読み込みが重くなるなどの弊害があるので。

その弊害を起こした記事👇

yadrfu.hatenablog.com　　...ということで、次回、LISの期待値について考察を進めていきます！

　次回が本題ではあるが、正直今回より短くなりそう（は？）。