0x19f (Shinya Kato) の日報

主にプログラミング関連の話をします

【メモ】UNIX V6コードリーディング(割り込み, p154〜159)

UNIX V6

今回の内容

前回の続きから.
アセンブリで書かれたcallとtrapの実行を詳しく見ていきます.

0x19f.hatenablog.com

call, trapの実行

書籍ではあまり言及されていない箇所が多くあまり進みませんでした.
以下, ざっくりとした理解です.
(間違っている箇所がありそう.)

割り込みの場合は, callの内部でr0に格納された割り込みハンドラが呼び出されます.
このr0に割り込みハンドラが格納される箇所は前回見たとおりです.

トラップの場合は, nofaultにトラップハンドラが指定されている場合とそうでない場合で分岐が発生します.
nofaultにトラップハンドラが指定されている場合は, そのトラップハンドラが呼び出されます.
そうでない場合は, callの中へとジャンプしC言語で書かれたtrap関数が呼び出されます.
(アセンブリ中では_trapで参照されています.)

基本的には, スタックになにが積まれていくのかが大事なようです.
ちらっと先読みした感じだと, この後割り込みハンドラ/トラップハンドラに処理が移った際にこのスタックがC言語で書かれた関数の引数になるようです.

trap

トラップ種別が含まれたPSWの値をカーネルスタックに格納します.
trap関数内でこの種別によって処理が分岐するんでしょうか.
nofaultが0かで分岐するのをtst, bne命令で実現しています.

nofaultにトラップハンドラが指定されている場合:
SR0レジスタを1で初期化.
ここが若干謎で, SR0の1ビット目が1になるとMMUが有効になるらしい.
しかし, なぜこのタイミングでSR0に1を格納しているのかがわからない.
実は割り込みが発生したタイミングでMMUが無効になってたりするんでしょうか.
nofaultをカーネルスタック上の割り込みされたプロセスのpcが格納されている場所に格納.
rtt命令でnofaultが指すトラップハンドラに飛びます.
もう一つよくわかっていないのが, この後のトラップハンドラからどうやってユーザープログラムに復帰するのかということ.
rttによって割り込まれたプロセスのPSWとpcが元に戻されているところまではわかるのですが...

nofaultにトラップハンドラが指定されていない場合: あまり細かく読んでいないのでざっくりと. jsr命令でr0を退避, _trapのアドレスを代わりに格納してcall1にジャンプ. callの中へジャンプ.

call

全然読めてないです.
最終的には割り込みハンドラへと飛んでいく感じ？

次回の予定

もう少しcallとtrapを詳しく.

DDCC2017本戦に参加してきました

参加記 競プロ

11/3(金)にDisco Discovery Channel Code Contest 2017の本戦に参加してきました.
予選ではC問題を解くのが遅めで本戦通らないかと思ったのですが, 19卒枠の繰り上がりで本戦に参加することができました.

https://discoverychannel.jp/ddcc/discoverychannel.jp

会場はDiscoのオフィスでした(200人も入れるスペースがあってすごい).
到着するとすでに多くの方がDDCC Tシャツに着替えて準備万端という感じでした.

コンテスト本戦

まずは, 10:30からコンテスト本戦.

ddcc2017-final.contest.atcoder.jp

コンテスト時間は2時間で問題は5問.
自分はABを解いて2完, 最終的な順位は200人中の88位.
90分間座ってるだけコンテストでした.

A問題:
問題を見た瞬間に第一象限だけ調べて4倍しようと思ったのですが, 200/Kや300/Kが奇数の場合に正方形の頂点がグリッド上に乗らないことに気づき場合分け.
結構時間がかかってしまいました.
円の中心を(0, 0)に置くって固定観念にとらわれなければもう少し楽に解けますね...

B問題:
サンプルを見てこれはA[i]とZのGCDを計算してLCMを取ればいいのでは？と思い書いてみたら通ってしまいました.
個人的にはAよりもBの方が簡単だと思います().

C問題:
何もわからない, ばなな.
そもそもグラフの上でループを考える時にどうすればいいのかが全くわかりませんでした.
解説を読んでもあんまり理解できてないです.

D問題:
一応目を通しましたが, 見た瞬間にわからなさそうだということがわかりました(？).

E問題:
実はC問題がわからなさすぎてコンテスト中はずっとE問題を考えていました.
まぁ, もちろん解けませんでしたよね.
これ以上辺を伸ばしたら直径を維持できないという状態になったあとは葉を選んで辺を伸ばしていけばいいと思ったのですが, その状態までがどうすればいいのかわからず.

お昼のビュッフェ

お昼は会場でビュッフェでした.
以前にオンサイトでお会いした方やTwitterではよく絡むけど実際には会ったことないという方と交流できて楽しかったです.

ただし, お腹いっぱいになってきたタイミングで寿司が出てきたことだけは許さない().

座談会

お昼の後は, Ponanza開発者の山本さんとプロ棋士の西尾さんの対談(with モデレーターのchokudaiさん)でした.

いろいろと面白いお話が聞けたのですが, 中でも興味深かったのがプログラムを生成する人工知能が今後どれぐらいの速度で成長するのかという話題.
競技プログラミングにおいても問題を解くAIというのがちょこちょこ研究されているらしいですが, 驚くことにそういったAIはすでにAtCoderのレートで言うと1000を超えてきているとのこと.

ちなみに, このAIはサンプルの入出力に合うようなプログラムをひたすら投げ続けるというものみたいです.
前日にDDCC参加者のみなさんとご飯を食べていた時に話題に出たのですが, 過去のAtCoderのコンテストでこの方法を使って3秒でA問題をACしたという事例があるそうです.
(探してみたけれどこれでしょうか？Submission #286413 - AtCoder Regular Contest 030 | AtCoder)

問題の内容を把握した上で正解を導くというのはまだまだ先になりそうですが, こういった無理やり試す系のものはこれからどうなっていくのか楽しみですね.
懇親会の時にも, CodeforcesなどのHackが可能なコンテストなら大量にプログラムを収集してきて適当な入力を入れてみて出力が同じになるものとそうでないものに分ければ後者をHackできるのでは？などといった話が出ていました.

他に印象に残っているのは, プロ棋士の方が機械学習のアイディアを取り入れて将棋の学習をしている話でしょうか.
細かいことは忘れてしまったのですが, 棋譜を学習データとテストデータに分けるらしいです.
いや, 凄まじいなと...

会社見学

会社見学ではA問題の元ネタ(？)であるシリコンウェハから正方形のチップを切り出す機械などを見せていただきました.
そもそも「Discoって何してる会社なの？」という感じだったので, 非常におもしろかったです.
ちなみに, シリコンウェハが円盤状なのはシリコンの単結晶が円柱状になっていてそれをスライスしてシリコンウェハが作られるかららしいです.

懇親会 & 記念撮影

懇親会も豪華で再びお寿司が出てきました.
なお, お寿司は一瞬でなくなりました.
一般枠で参加されていた大学のOBの方とお話ができたりもしました.

あと, 話題のchokudaiさん看板で記念撮影もしてきました.
僕はchokudaiさん本人が看板の写真と同じポーズをしている公式コラ画像(？)が一番好きです.

最後は参加者全員で記念撮影.
コンテスト運営の方々, お話してくださった参加者のみなさん, ありがとうごいました.
CODE THANKS FESTIVALに参加される方はまた近いうちに, そうでない方はまたいつかお会いしましょう.

【メモ】UNIX V6コードリーディング(割り込み, p144〜153)

UNIX V6

勉強会の趣旨

UNIX V6ソースコードを読もうという会です.
この本に沿って読み進めてます.

はじめてのOSコードリーディング ~UNIX V6で学ぶカーネルのしくみ (Software Design plus)

はじめてのOSコードリーディング ~UNIX V6で学ぶカーネルのしくみ (Software Design plus)

月曜5限後にラーニングコモンズでひっそりやってるので興味がある方がいればぜひどうぞ.

これはその勉強会の内容のメモです. (自分が後から見返すよう程度なのであんまり参考にはならないと思います.)

今回の内容

10/30
第3部の割り込みから.
途中からメモを取り始めたので, 第1部, 第2部のメモはないです...
ざっとプロセスについて読んで, execあたりで心が俺て飛ばすことにした(forkあたりまでは読んだ感じ).

割り込み・トラップ

割り込み
  • 周辺デバイスからの非同期的な要求を処理するための仕組み.
トラップ
  • CPU内部で起こる出来事を非同期的に処理するための仕組み.
  • 0除算, バスタイムアウトなどの例外発生をシグナルとして処理する.
  • システムコールはトラップを用いて実現される.

割り込みとトラップの違いは, きっかけとなる要因が外部デバイスかCPUか.

優先度

割り込みには0から7までの優先度が設定される.
割り込み優先度の方がPSWのプロセッサ優先度より小さい時だけ割り込みは処理される.
トラップには優先度がない.
トラップは発生すると即座に処理される.

割り込み・トラップベクタ

カーネルプロセスが割り込み・トラップ処理を開始する際に設定されるPSW, pcの値が格納されているアドレス.
(このアドレスはユーザープロセスの仮想メモリアドレス？カーネルプロセスの仮想メモリアドレス？)
ベクタの値はPDP11によって決められているっぽい.
ベクタデータはカーネルプログラムの下位アドレス部に書かれている.

割り込み・トラップの発生

割り込み・トラップの発生
→PSW, pcをカーネルスタックに退避, ベクタが指すアドレスからPSW, pcを読み込む(ハードウェア処理).
→読み込んだpcから処理を再開(call, trap関数が実行される).

カーネルプログラムの下位アドレス部分を読むと, 0番地にジャンプ命令があって飛んだ先でstart関数を呼び出している.
その部分を除くとだいたいは割り込み・トラップベクタのデータになっている.

ベクタデータの中身は, トラップの場合は, trap関数のアドレスとPSWが格納されている.
割り込みの場合は, それぞれ関数が用意されていてそのアドレスとPSWが格納されている.
その関数の中でcall関数が呼び出される.
ここで使われているjsrが少しわかりづらい.
REF: PDP-11のjsrの動き：いや、まさにログ的な：So-netブログ

ややこしいのが, trap命令とtrap関数がどちらも同じtrapという名前なところ.
一応, このアセンブリではsys命令が擬似trap命令になっているらしく, trapと書いてあったらtrap関数だと思って良さそう(？).

これまたややこしいが, br4〜br7はPSWの値.
トラップの場合はPSWの下位3ビットにトラップの種類を表す値が格納される(br7+4など).
(下位3ビットと書いてあるのに, +9とかしている箇所があって謎.)

次回の内容

call, trap関数の中身を詳細に読む予定.
割り込みが発生した場合, トラップが発生した場合の処理を丁寧追う必要がありそう.
特に, 割り込みの方はjsr命令によってr0とpcの値がいろいろと変わるので気をつける必要がありそう.

会津大学競技プログラミング合宿2017に参加してきました

参加記 競プロ

いろんな人の参加記を見ていたら自分も書きたくなったので書きます.
9/18〜20で会津大学の競技プログラミング合宿に行ってきました.

3日間の日程があってそれぞれ立命館大学, 会津大学, 北海道大学が作問した問題をICPC同様のチーム戦で解くという感じでした.
ちなみに, チームはほぼその場で強さが偏りすぎない程度に適当に決めてました.
実は初めてのオンサイトコンテストだったのでACすると風船が上がる感じとかとても楽しかったです.
コンテスト自体はAOJ上で行われていて, オンラインで参加している方もたくさんいました.

Day 1

東京駅を9:00に出発, 12:00頃に会津若松駅に到着.
郡山まで東北新幹線使うとかなり近いですね.
そして駅からしばらく歩いて会津大学に到着.

f:id:mizu0x19f:20170926205813j:plain

1日目は立命館大学が作問した問題セットでした. ACPC2017Day1 (解説)

チームは会津大学の方二人と組ませていただきました.
自分はB問題を解いたのですが, バグらせまくって本当に申し訳ないという感じです...
B問題を通した時にはすでにA, C, Dが解かれていました.
残ったE, F, Gは結局解けませんでした, 残念.

合宿終わった後に全部問題ちゃんと見た感想です.

  • A: 丸付け (解答)
    • 2文字ずつ見ていけばO(N)で判定可能.
  • B: 全日本帰りたい協会 (解答)
    • 次の人を迎えに行くまでに1Fに戻っても間に合うならば, 1Fに行くのが常に最適.
    • ...なのですが, 結構チェックしないといけない箇所が多かったりして実装がしんどいです.
    • ちなみに, 僕は最初の人を迎えに行けるかどうかの判定を忘れて2WA出しました.
  • C: ツイート数 (解答)
    • DFSしながら葉からの最短距離を求めていけばOK.
  • D: 次元旅行 (解答)
    • i次元からi - 1次元にだけ辺を張ってダイクストラすればいいというのが面白かったです.
    • 普通に全部に辺を張ったらMLEしたので解説見ました.
  • E: 敵襲から守れ
    • まだACできてないです.
    • あんまり最大フローがよく理解できてないのですが, この期に理解してしまいたいので頑張って通したいと思います.
  • F: Steps
    • ランダムウォークではよくあるタイプの問題らしいのですが, あんまりちゃんと理解できてないです.
  • G: Cryptex
    • めちゃくちゃ頑張ると解けるらしいです(遠い目).

Day 2

二日目は会津大学が作問した問題セットでした. ACPC2017Day2
僕 + 立命館の方 + 社会人の方の3人チームでした.
自分はA, C, F, Lを解きました.
A問題は人生初のFA(オンサイトのみ)で結構嬉しかったです.
FAなので風船にかわいい動物がついてきました.
圧倒的にチームのみなさんが強くてオンサイト1位でした.

以下各問題の感想です(解けたもののみ).

  • A: Clock (解答)
    • 割って余り求めたらいけるやろ〜とか言って提出したら通りました.
    • 人生初オンサイトFAやったね！
  • B: Hating Crowd (解答)
    • ちょっと面倒ですが愚直にやると解けました.
  • C: Palindrome (解答)
    • N^2が間に合う制約なので, 回文にするときのペアを探してから辞書順に貪欲にとっていけばOKです.
    • ちょっと実装がややこしくてバグらせましたが...
  • D: Fissure Puzzle Easy (解答)
    • 白いマスの連結成分の数を数えて1引いて3で割ると答えが出るというちょっと面白い問題でした.
    • 領域を4分割していくのでも解けるみたいです.
  • E: Piano (解答)
    • 連続して増加, 減少している部分の最大を求めれば解けます.
  • F: nCm (解答)
    • 問題を見たらすでに考察がされていたので, その通りに実装したら通りました().
    • 結局2^kのところだけ見ればO(logN)で解けるようです.
  • I: Making Pairs (解答)
    • 木の上でマッチングをする問題.
    • DFSしながら, マッチしていないものと貪欲にマッチさせていけばOK.
  • L: RMQ 2 (解答)
    • クエリはQ個しかないので, 全部コピーする時は以前に変更があった箇所だけコピーすれば間に合います.
    • コンテスト時間中に通せてよかった...

コンテスト後はリクルートコミュニケーションズのアドテク部さんのおかげで無料で懇親会に参加することができました.
(その謎のお金は一体どこから出てきてるんでしょうねぇ......)

Day 3

三日目は北海道大学が作問した問題セットでした. ACPC2017Day3
僕 + 会津大学の方 + 立命館大学の方みたいなチームで臨みました.
B問題が鬼難しくて, Bとは何かについて哲学的な考察をしていました.

以下問題の感想です.

まとめ

初めてのオンサイトコンテストでしたがとっても楽しかったです.
また, 作問している方々を見て素直にすごいなという感想を持ちました.
うちの大学でも強い競プロerの人々がコンテスト開きたいと言っているので, その時は作問側もやってみたいなと思いました.

最後になりましたが, コンテスト運営してくださった方々, 作問をしてくださった方々, 当日チームを組んで下さった方々, 本当にありがとうございました.

(ちなみに, 実は会津合宿の帰りにもう一泊して「全部ACするまで帰れま10」という企画もやったのですが, その時のことはまた別記事で書きたいと思います.)

9/10 PyCon JP 2017に参加してきました

9/8, 9に行われたPyCon JP 2017に参加してきました.
pycon.jp

正直あまりPython書いたことないのですが, 今年は思い切って行ってみることにしました.
というのも, なんと参加枠に早稲田大学生という枠があって, しかも参加費無料だったんですね.
おまけに開催場所は普段まさしく授業を受けている理工のキャンパスの63号館.
これは参加しない手はないということで即connpassから申し込みました.
決して懇親会のタダ飯が目当てではないです.


PyCon JP 1日目

申し込んだものの, 1日目は大学の夏期集中講座と被ってしまったので, 夕方のLTからの参加です.
(昼間は隣の建物で授業受けてました.)

LTの中で印象に残っているのは, 「built-in関数への代入はやめよう」という趣旨の発表です.
Pythonそんなに書いたことのない自分はこの時は初めて知りました.
listってbuilt-in関数なのかよ！
間違いなく今までにlistという名前にリストを代入した覚えがあります.
知らずにbuilt-in関数の人権を侵害してきたんですねぇ, 申し訳ない...

その他では, ギャル語翻訳も結構インパクト強かったですね.
togetter.com

PyCon JP 2日目

2日目は丸一日参加しました.
いくつか印象に残ったセッションの感想を書いておきたいと思います.

Opening Keynote

speakerdeck.com

pandasとDaskのコミッタである堀越さんのセッション.
OSSコミッタがどんな仕事をしているのか, これからOSS活動を始めたい人が何をすべきなのかという内容でした.
最近Pythonで機械学習をした時にちょろっとpandasを使ったので, 聞いていて話の理解はしやすかったです.

セッションを聞きながら, OSSに貢献はしたい一方で, バグっぽいものに遭遇した時に自分のミスなのか本当のバグなのかの切り分けが難しいよなぁと.
巨大なソフトウェアともなると, ドキュメントだけでも読み切れないぐらいあるので.
そういう状況でissueを書くってのもなかなか勇気がいるなぁなんて考えてました.
あぁいうのってどれぐらいのノリで書くものなんですかね.

Pythonで実現する4コマ漫画の分析・評論 2017

slideship.com

4コマ漫画を各コマごとの画像に変換, セリフを抜き出し, 登場人物を特定するという試みでした.
正直に感想を言うと, ゆゆ式の話が気になって肝心の機械学習周りの話があまり理解できませんでした！

今でも当時のアニメ放送時間になるとエア実況が発生
2017年9月5日(火) 24:30放送(?)分で18クール214話

ゆゆ式の何があそこまで人を狂わせるのか気になったので, そのうちアニメ見てみたいと思います.

理論から学ぶPythonによるサーバーレス開発

slideship.com

サーバーレスって聞いたことはあってもどういうものか全く知りませんでした.
「名前から推測するにサーバーがないということなんだろうか？？？」とか思ってたぐらいです.
とりあえず, セッションを聞きながら一般的なWEBサービスとは相性そんなによくないのかな？って思ったぐらいしか理解できませんでした.

PyConJPで彼女つくってみた(LT)

slideship.com

支離滅裂な文章を返してくるところがマルコフ連鎖の面白いところですよね.
素敵な彼女さんができることを祈っています(遠い目).

まとめ

今までPythonそんなに書いてきませんでしたけど, 今回でいろいろと便利そうなものがあるのもわかったのでちょっと勉強していきたいと思います.

こんな素晴らしいイベントの参加権をいただけで本当に幸運でした.
スタッフのみなさん, 登壇者のみなさん, ありがとうございました.

IMG_4875

8/21 サマーウォーズを見てRSA暗号について調べた

普段テレビはほとんど見ないのだけれど, 先日は金曜ロードショーのサマーウォーズを見てました.
相変わらずいつ見てもいい作品だなぁとか夏希先輩かわいいなぁとか思いつつ, Twitterでわいわいしてました.

サマーウォーズが放送されると必ず話題に上がるのが健二が解いているあの暗号の話.
解いている様子の描写からRSA暗号じゃないかと言われています.
RSA暗号というと素因数分解というイメージが強いのですが, あまり暗号化と複合の部分がどういう原理でできているのかについては理解できてませんでした.
というわけで, サマーウォーズを見ながらいろいろと調べて考えてみたことをまとめてみたいと思います.

公開鍵暗号方式

そもそも, RSA暗号は公開鍵暗号方式の一種で, 2つの鍵を用いて暗号化と復号を行います.
簡単に言うと, 以下の2つの性質を持つような暗号です.

1. 片方の鍵で暗号化したら, もう片方の鍵でしか復号できない.
2. 片方の鍵からはもう片方の鍵は(簡単には)推測できない.

RSA暗号の基本的な仕組み

RSA暗号の基本的な仕組みについてはWikipediaなどを参照してもらうと良いと思うのですが, 簡単に書いておきます.
RSA暗号 - Wikipedia

p, q: 任意の素数, n = pq
e: (p - 1)(q - 1)と互いに素な任意の正の整数(公開鍵)
d: ed = 1 \pmod{(p - 1)(q - 1)}を満たす正の整数(秘密鍵)
m: 平文, C: 暗号文

暗号化: C = m^e \pmod{n}
復号: m = C^d \pmod{n}

というわけで, 実は累乗が計算できれば暗号化と復号は簡単にできます...
ってほんまか？となるわけですね.
これってつまり, m^{ed} = m \pmod{n}が成り立つってことに他ならないわけです.
さすがに自明ではないよなぁ......と.

復号がうまくいくのはフェルマーの小定理で説明できる

『高校数学の美しい物語』の説明がわかりやすかったです.

mathtrain.jp

少し補足をすると, 合同式には以下の性質があります.

a = b \pmod{p}かつ a = b \pmod{q}ならば a = b \pmod{lcm(p, q)}
( lcm(p, q)は pと qの最小公倍数を表す.)

つまり, m^{ed} = m \pmod{n}を示すためには, m^{ed} = m \pmod{p}を示せば十分ということになります.

興味深いのは, フェルマーの小定理を用いているところです.
これを利用してうまく暗号化ができるようになっているわけですね, 賢い.

素因数分解の困難性が安全を保証している

公開鍵暗号方式なので, 公開鍵 (e, n)から秘密鍵 (d, n)が推測されると暗号を突破されてしまいます.
秘密鍵を推測するためには ed = 1 \pmod{(p - 1)(q - 1)}を満たす dを計算する必要があります.
つまり, nを素因数分解して p, qを求め, (p - 1)(q - 1)を計算する必要があるわけです.

素因数分解は p, qが十分に大きな素数であれば現実的な時間で解くことはできません.
逆に言えば, 素因数分解ができてしまえば暗号を解読することができます.

「RSA暗号 = 素因数分解」というイメージ

サマーウォーズを見ながら, 流れてくるRSA暗号についてのツイートを眺めていたのですが, 「素因数分解する暗号」という説明が結構多かった気がします.
まぁ確かに「ふたつの素数 (p, q)から積 nを求めるのは簡単だけれど, nから (p, q)を計算するのは困難」と言われると, なんとなくわかったような気がしてしまうんですよね.
「素因数分解が効率よくできない」って直感的なのでそういう説明が出てくるのはわかるのですが, それって誤解の原因になりやすいんじゃないかなぁと.

人間って直感的な事柄の次に非直感的な事柄が出てくると, なんとなく理解した気になってしまうところがあると思います.
やはりそういう説明で納得してしまうことのないように気をつけたいなぁと.

まぁ, そんなことを考えていたよ, というお話でした.
(余談ですけど, はてなブログってTeXの数式を書くとMathJaxでレンダリングしてくれるんですね.)

8/11 AtCoder Regular Contest 080

この前うっかり寝過ごしてで損ねたARC080を解いた.

  • C: 4-adjacent - AtCoder Regular Contest 080 | AtCoder [解答]

    数列の要素を自由に並び替えて隣り合う要素の積が4の倍数になるようにできるか判定する問題. Aiが奇数, (4の倍数でない)偶数, 4の倍数で隣に置かなければならない数の条件が変わることに注目する. Aiが奇数なら, 隣には必ず4の倍数をおく必要がある. Aiが偶数なら, 隣には偶数をおく必要がある. Aiが4の倍数なら, 隣におく数はなんでも良い. ここから考えると, { 奇数, 4の倍数, 奇数, 4の倍数, ..., 4の倍数, 偶数, 偶数, ... }みたいな並びが作れるかを判定すれば良いことになる.

  • D: Grid Coloring - AtCoder Regular Contest 080 | AtCoder [解答]
    1, 1, 1, 2, 2, 3, 3, 3, 3, ...., N, N, Nと左上から順に要素数H * Wのマス目を埋めていき, 奇数番目の行だけreverseして表示すればOK.

  • E: Young Maids - AtCoder Regular Contest 080 | AtCoder [解答]
    辞書順で最小のものを構成するのは後ろから考えるとやりづらいので, 先頭から小さい数字を順に決めていくことを考える. 最初の状態からqの先頭2つの要素を決めるのには, 偶数番目の要素でもっとも小さい値とその要素以降で奇数番目の要素を取るのが最良. この二つの要素がpのi, j番目だとすると, pは[0, i), [i + 1, j), [j + 1, N)の3つの要素に分断される. qの次の2要素はこの3つの領域の偶数番目の値から最小のものを選ぶことになる. これを繰り返していけばO(N^2)でqを求めることができる.
    ここから計算量を落とすためには, 偶数番目/奇数番目の要素から最小を求めるのにセグメントツリー, 分割された領域からどれを選ぶかはpriority_queueを用いればよい. 具体的な手順としては,
    1. { [0, N), min_odd }をpriority_queueに入れる
    2. priority_queueから最小のものを取り出す
    3. 3つの領域に分割して, それぞれをpriority_queueに入れる
    4. priority_queueが空ならループ終了, そうでないなら2に戻る
    という感じ. 結構実装がしんどかった...