令和5年度 大阪大学大学院情報科学研究科 博士前期課程 学部3年次学生を対象とする特別選抜 受験記

「令和5年度 大阪大学大学院情報科学研究科 博士前期課程 学部3年次学生を対象とする特別選抜」の第 1 次試験に合格しました! おめでとう!

制度の利用者が少ないので (今年の場合たぶん受験生 6 人) 後世のために記録を書いておきます.なお,ここで言及するのはいわゆる「5 専攻」の話であり,そのうち制度が変わることもあり得るので自分できちんと調べてください.

「学部3年次学生を対象とする特別選抜」とは

学情報科学研究科には「飛び入学」の制度があります.学外の人も含めて,学年さえ適合すれば誰でも出願できるようです.学内の場合は取るべき単位を取っていて卒業要件を難なく満たせそうであれば十分挑戦可能だと思います.高年次配当科目を先取りする必要もありません (4 年次配当科目は授業を受けないまま退学することになります).

簡単に流れを書いておきます (全然簡単になっていないのですが,それは制度が複雑だからです,細心の注意を払いましょう).

  1. TOEIC を早め早めに受けておきます.出願のおよそ 2 年前までの結果が有効です.何度か受けて最も良かった 1 回の成績を提出します.
  2. 3 年生になった 4 月の履修指導の際にこの制度の説明を受けます.同じく 4 月に 4 年生向けのオンライン研究室紹介 (各研究室が 5 分ずつぐらいスライド発表した後,興味のある研究室と個別に相談できる) があり,4 年生に紛れて一緒に参加できます.募集要項もこのすぐ後ぐらいの時期に出ます (個人的にはかなり前から「全然出ないな」と監視していましたが,そんなものです).
  3. 成績証明書,在学証明書を自動発行機で印刷しておきます (事前審査に必要).
  4. 第一志望の専攻の長にメールします.成績証明書のスキャンデータを求められると思うので,それを送ることで出願資格があるか否か判断してもらえます (取るべき単位を取っていれば大丈夫だと思います).
  5. 5 月末ごろに「事前審査」のための書類 (志望理由書など) を郵送します.後日合格と書かれた A4 の紙 1 枚がぺらっと入った小さい封筒が届きます.
  6. 6 月末ごろに「出願」のための書類 (願書,TOEIC の成績表など) を郵送します.後日受験票や注意事項などが入った角 2 の分厚い封筒が届きます.TOEIC の成績表も同封されて返却されます (もう戻ってこないと思っていた).
  7. 7 月末ごろに「第 1 次試験」(筆記試験と口頭試問) を受けます.
  8. お盆明けぐらいに「第 1 次試験」の合否が発表されます.←イマココ
  9. 「第 2 次試験」(その後も単位を取り続けているかのチェック) があります.まだやっていないのでよくわかりません.
  10. 3 月の頭に「第 2 次試験」の合否が発表されて晴れて合格です.やったぜ.まだ合格してないけど.

TOEIC

前年 6 月に受けたときは 870 点,12 月に受けたときは 915 点で,後者を提出しました.割と高い方だと思います.

以前は 600 点ぐらいが平均と言われていたようですが,個人的な体感としては学生の英語力が上がっており,700 点は欲しいのではないかと思います.

どういう傾斜で選考に組み込んでいるのかは「○○点以上は実質同じ」「○○点取っておくと筆記試験で大問 1 つやらかしても大丈夫」など様々な説や迷信があります.専攻ごとに使われ方が異なるから説が入り乱れるのではないかと考察しています.

なお,TOEIC の成績は筆記試験の当日に提出または再提出可能であり,直前の 6 月の回が最後のチャンスになるはずです.自分もこの回を受けようかと思っていたのですが,その時期に忙しかったので止めてしまいました.結果として「あのときもう数十点稼いでおけば良かったかも」とずっと後ろめたさを抱えることになったので,最後まで全力で臨んだ方が良いです.

筆記試験の勉強方法

試験範囲となっている学部の授業を真面目に受けましょう!!! それだけやっていれば受かります.決して難しい試験ではないです.

ちなみに 4 年生の人たちは時間が空いて忘れてしまっていることも多く,講義資料やオンライン授業の動画などを見返して一から勉強しているケースが多そうです.

出題範囲

[選択] の 5 題中 2 題を選択し,合計で 4 題を解答します.

[必答] 1. アルゴリズムとプログラミング

対応する学部の授業:プログラミング A, B, C (C 言語),データ構造とアルゴリズム

C 言語で実装されたアルゴリズム (ソート,グラフ探索,動的計画法など) を読み取って,配列の中身や printf の結果,オーダーや最悪ケースの作成などに取り組みます.

[必答] 2. 計算機システムとシステムプログラム

対応する学部の授業:計算機アーキテクチャオペレーティングシステム

計算機アーキテクチャオペレーティングシステムの試験・レポートで見たような問題が出ます.
計算機アーキテクチャ:2 の補数,浮動小数点数アセンブリ言語,パイプラインプロセッサ,キャッシュ など
オペレーティングシステム:プロセスのスケジューリング,仮想記憶,ファイル管理 など

[選択] 3. 離散構造

対応する学部の授業:情報数学基礎 (前半),情報論理学

年によって割といろいろな問題が出ます.漸化式や数学的帰納法,関係が満たす○○性の証明,グラフの表現や性質の証明,述語論理をスコーレム標準化してからの導出原理,天才以外お断りパズルなど.

[選択] 4. 計算理論

対応する学部の授業:計算理論

計算理論の授業や試験の内容がそのまま出ます.有限オートマトン,文脈自由文法,プッシュダウンオートマトン.与えられた構造で受理される指定長以下の語を列挙する,遷移を埋める,何らかの性質を証明する,反復補題,別の構造に変換するなど.

[選択] 5. ネットワーク

なにもしりませんが,情報解析 A と情報ネットワークに関係していそうです.情報論 A との関連はわかりません.

[選択] 6. 電子回路と論理設計

対応する学部の授業:電子回路,情報数学基礎 (後半),論理設計

電子回路しか出ない年,論理設計しか出ない年があり,これらは全然似ていないので対策が難しいです.電子回路は微分方程式とか複素数とか位相とかが出てきます.論理設計は状態遷移図やカルノー図を描いて論理式を求め,回路図を描いたり遅延を計算したりします.CMOS が出ることもあります.

[選択] 7. 数学解析と信号処理

なにもしりません.

過去問

各研究室が 20 年分ぐらいの過去問と先代の解答例を蓄積しています.研究室に訪問して先輩方に頂くと良いです.

ちなみに自分の第 1 志望の研究室は大人気で学外からの志願者も多く,配属者数が例年 6 人ぐらいであるのに対し,今年は 15 人ぐらい受けるっぽいと噂されていました.倍率 2.5 倍! 驚愕! 勉強会をやる研究室も多いそうですが,今年は無かったのかお誘いを受けませんでした.

もらった過去問ですが,自分は直近 10 年分を解きました.選択問題は離散構造,計算理論,論理設計を解きました.計算理論は解きやすい問題ばかりで範囲も狭いため確定で,離散構造で天才以外お断りパズルが出たら論理設計に逃げ,電子回路が出たら離散構造に逃げることにしていました.試験時間は 3 時間ありますが,5 題合わせて 2 時間あれば十分に解き切れると思います (なんでこんなに試験時間長いんだ).

筆記試験当日

なんと,早く解き終わった人は途中退室可能でした! 試験開始 30 分後までは遅刻者が来る可能性があるため退出不可,試験終了 10 分前からはややこしいので退出不可です.自分は試験終了の 15 分前に退出してみましたが,他は誰も退出する気配がありませんでした.試験監督の先生方がマニュアルを片手にあわあわしていました.使うことを想定された制度ではなかったのかもしれません! 検証結果は以上です! いかがでしたか?

問題文は A4 の片面に印刷されており,ホチキスで止まっています.試験が始まったらホチキスを外すと解きやすいです.解答用紙は B4 縦で,業者が用意したっぽいよさげな紙です.大問 1 つにつき 1 枚あります.必答の問題は小問ごとに解答欄が用意されており,選択の問題は真っ白なので自分で開拓していきます.裏面も使用可能で,特に証明問題が来ると裏面が使いたくなると思います.それ以外にもう 1 枚,選択問題調査票があり,選択した大問に丸を付けます.

8:35 アナウンス開始,8:45 には TOEIC の回収や問題の配布が終わり,15 分ぐらい暇でした.

時計は持っていきました.試験開始の待ち時間にシャーペンを見たら中に予備の芯が一本も入っておらず,シャー芯ケースも持ち歩いていなかったので焦りました.なんとか試験終了まで持ちこたえてくれました.普段筆記用具を使わない同志の方は気を付けてください.

なお,電子回路しか出なかったので離散構造を解きました.

試験終了後は一緒に受けた人と答え合わせをしました.出来が悪かった人は口頭試問で解きなおしをさせられることもあるそうなので,やっておくと良いです.ざっくり採点の結果は,
[1] 105/125
[2] 125/125
[3] 110/125
[4] 125/125
[全体] 465/500
で,9 割あるかなという感じでした.近年は問題数が減少し,長文の記述問題も減少し,ちょっとした数え上げや計算のケアレスミスが致命傷になり得る感じで,採点するまで怖かったです (採点業務のスリム化かな).

口頭試問当日

受理順に受験番号が割り振られ,受験番号順に呼び出されるため,あまり待ちたくない人は早めに出願すると良いと言われています.自分も早めに出願したのですが,飛び入学の志願者は受験番号の上の位が一般の志願者より大きく,呼び出されたのはほぼ最後でした.待ち時間は電子機器類の使用が禁止されているため,紙媒体で何か持っていくと良いです.

呼ばれたけど行方不明の人が 10 人に 1 人ぐらいのペースでいたように記憶しています.筆記試験の出来が悪くて来られなかったのかな・・・.恐ろしや・・・.

ノックして部屋に入ると,若めの先生から着席して受験番号と名前を言うように言われました.その後,ベテランっぽい先生から

  • どうやって勉強したか? (過去問を 10 年分解いた)
  • いつごろから勉強したか? (6 月後半から)

を聞かれました.その後,その先生にやたら褒められました.

  • 筆記試験の出来が良かった.
  • 願書 (事前審査で出した成績証明書のこと?) を見たが,教職課程も取っていて偉い.
  • 「学部学生による自主研究奨励事業」もやっていて凄い.

もうべた褒めでした.合格確定演出でした.ありがとうございます.大学院でも頑張っちゃいます.

その後先ほどの若めの先生から「学部 3 年次を対象とする特別選抜受験者に対する合格条件」という A4 の紙を渡されました.端的に言うと,3 年秋~冬学期までに配当された各科目の単位を修得すれば本当に合格になるというものです.そして退出を促されました.

志望動機とか飛び級したい理由とかは聞かれたら答えられるように準備していたので,あっさりしすぎていて少し寂しかったです.でもボーダー上でガンガンに質問されるのは怖すぎるのでそれが無くて良かったです.

第 2 志望の専攻の面接に行くように言われず,この専攻の研究室は 1 つしか書いていない (「専攻内指定無し」も書いていない) ので,実質合格確定でした.この確認方法は便利です.

部屋は筆記試験のときにも使った部屋で,受験者が 80 人ぐらい収容されていたのではないかというサイズ感です.その教卓の位置にちょこんと座りました.聴者側の座席にはまばらに 15 人ぐらい先生がいらっしゃったのではないかと思います.たぶん講師・准教授・教授がここにいて,助教が控室の整理などに回されているのではないかと思います.

付録:想定質問集

過去に実際にあったとされている質問を元に作成しました.

  • ○○専攻を志望したのはなぜですか?
  • ○○研究室ではどのような研究がしたいですか?
  • 昨日の筆記試験は難しかったですか?
  • どの問題が難しかったですか?
  • 昨日の筆記試験は何割ぐらい取れたと思いますか?
  • この分野の出来はどうでしたか?
  • 選択問題でこの 2 題を選んだのはなぜですか?
  • TOEICは何回受けましたか?
  • TOEICはどのように勉強しましたか?
  • 博士前期課程の修了後は就職を予定していますか?

後日談:合格発表

アナログなことに,吹田キャンパスの掲示板に合格者の番号を貼りだしているらしく,インターネットでは結果がわかりません.合格発表の日にオンラインの研究ミーティングが入ったのもあって掲示板を見に行かなかったら,ミーティングの最後に先生にサラッと合否を告げられることになりました.「そ,そうなんすか」みたいな絶妙に中途半端なリアクションをしてしまいました.合否結果は郵送もされるはずなのですが全然来なくて,速達でも書留でもなく掲示発表の 2 日後に郵便受けに入れられていました (お金無いのかな・・・).

飛び入学に意味はあるのか?

最後にこの質問の答えを出しておこうと思います.研究室訪問の際にも聞かれて,いろいろと考えていました.

前述の履修指導で言われた一般的なメリットとして,

  • 同級生 (知り合い) が増える
  • 試験範囲の記憶が新鮮なうちに院試を受けられる
  • 学費を抑えられる
  • 社会に早く出て活躍できる

などがあるそうです.一方でデメリットとして,

  • 学部 4 年の授業が受けられない
  • 卒業研究の経験が無いまま博士前期課程の研究をすることになる
  • 退学になるため,院で事故ると最終学歴が高卒になる (コワイ)
  • ごく一部の国家試験等は学士を受験要件としていて,修士だけでは受験できない (らしい)

などがあります.特に卒業研究の経験を積めない点は人によっては深刻で困るそうです.

自分の場合は前述の通り「学部学生による自主研究奨励事業」で卒業研究よりは本格的そうな研究経験を積ませてもらいましたし,正直講義を聞くよりも教科書を自分で読んだ方が効果的に勉強できると感じている部分があるため,デメリットはあまり感じませんでした.

また,将来の選択肢を増やせるというメリットは大きいと思います.就職するなら相当強いエピソードとして有利に働いてくれると思いますし,博士後期課程に進学するなら学費面の後ろめたさが和らぎます.

ただ,そういう理性的な議論はさておき,飛び入学をすることに決めたのは「なんか面白そうだから」に尽きると思います.変な制度があると使いたくなってしまうんですよね (←筆記試験を途中退室した無礼者はこちらです).

これからもワクワクを追いかけていこうと思います.

追記:第 2 次試験についての補足

面接の退室前に「学部 3 年次を対象とする特別選抜受験者に対する合格条件」というのをもらいますが,ここには次のように書かれていました.

令和 5 年 2 月 22 日までに以下の (1) - (5) に示す単位を修得していること.
(1) 共通教育系科目及び専門基礎教育科目については,所定の卒業要件単位数.
(2) 専門教育科目の必修科目については,3 学年までに配当の 54 単位すべて.
(3) 専門教育科目の選択科目については,A 群から 8 単位以上,B 群から 8 単位以上.
(4) 専門教育科目の高度教養教育科目については,2 単位以上.
(5) 専門教育科目の高度国際性涵養科目については,「情報科学ゼミナール B」を含む 1 単位以上.

3 年春~夏学期までの成績が反映された「成績証明書」と 3 年秋学期の「履修登録確認表」,3 年冬学期の「履修登録確認表」(KOAN から PDF をダウンロード可能) の 3 枚を大学院係に提出します.提出方法について問い合わせたところ,窓口で手渡しでも郵送でも良いそうです.

追記:退学についての補足

第 2 次試験にも無事合格しました.今度は速達で送られてきました.中身にはあまり大したことが書かれていなかったのですが,入学料振込の領収書と顔写真を郵送することで入学手続きを取れました.募集要項の注意事項に書かれた 2 日間にピンポイントに届くように郵送しないといけないのがやや難です.

面倒なのは退学手続きの方です.募集要項の注意事項には

本研究科博士前期課程に入学するために学部3年次で退学する者は、合格者発表後速やかに、所属大学(学部)に「退学」手続きを行ってください。

とあります.退学手続きは概ね次の手順で行われます.

  1. 基礎工学部の教務係の窓口で退学願をもらいます.もらった人の名前が控えられます (他の書類でももらう度に控えられます).1 週間以内に持ってくるように告げられます.
  2. 自身の署名と印鑑が必要です.
  3. 保護者の署名と印鑑が必要です (署名の筆跡と印鑑が自分のものと同一の場合受け付けられないと裏に書かれています).
  4. 学科長とコース主任の印鑑をもらってこなければなりません.
  5. 基礎工学部の教務係の窓口に退学願を提出し,控えを受け取ります.

対応が最も非自明なのは 4. だと思います.G 棟にある情報 2 コースの事務室は情報科学研究科の飛び入学に合格した人のリストを持っており,当該学生が来たら印鑑を代理で押すように指示されているようです.わざわざ学科長やコース主任にメールで連絡を入れたり吹田キャンパスに行ったりする必要はありません.情報 2 コースで保管されている印鑑には過去にも何度かお世話になっていて,とても感謝しています.情報 2 コースの事務室はいつも対応が良く助かっています.

ところで,今年の情報科学科の学科長は情報科学研究科所属 (≒ 情報 2 コース所属) だったのですが,基礎工学研究科所属 (≒ 数理科学コース所属) だった場合どうなっていたのでしょう.恐ろしいですね.

なお,基礎工学部の教務係は (基礎工学研究科の話ならまだしも) 情報科学研究科の飛び入学の事情を基本的に知りません.あまりスムーズに話が進みません.本当は学生の利便性を考慮したいような雰囲気でしたが,気軽に退学されては困ると学部長から圧力をかけられているようでした.それはそう.

情報学部はよ.吹田キャンパスの民になるのも微妙だけど.

追記:学研災・学研賠についての補足

学研災 (本学学生は全員必須)・学研賠 (情科は必須ではないはず) は個人ではなく学籍に結び付いているようです.研究科に入るタイミングで学籍が変わります.解約して 1 年分の払い戻しを受け,新たに 2 年分契約する必要があるようです.なお,博士前期課程在籍時に 5 年分払うことはできません.

同じ SSD を 2 台買って両方繋いだらブルースクリーンが出た件とその解決策

3 か月ぐらい前に SanDisk SSD PLUS 2000GB SCSI Disk Device を 2 台買いました.USB 接続のやつを買ったつもりが間違えて SATA 接続のを買っちゃいました (届いて開いてからめっちゃ焦りました).で,USB と SATA を変換するやっすいケーブルを 2 本 (同じ種類) 買いました.2 台同時に Windows に繋ぎました.2 台目の方がエラーが出て使えませんでした.無理やりマウントしたりしようとするとブルースクリーンで落ちました.今時ブルースクリーンを見ることになるとは.

たまに戦っては諦めてを繰り返していましたが,今日ついに解決しました.

DISKPART を起動して UNIQUEID を見たら被ってました.片方の最後の 1 桁を 1 大きくしました.無事両方同時に認識されるようになり,相互コピーとかも可能でした.やったぜ.

説明が雑でごめんなさい.でも自分が何をやったのか実はよくわかっていないのです.おしまい.


追記:パソコン再起動したらまた発生した

AtCoder Regular Contest (ARC) 115 E - LEQ and NEQ 解説

atcoder.jp

 A をソートしてあいだの範囲に注目して,

  •  dp[i+1][j] を, X_i j 番目の範囲の値にする  X_1, \ldots, X_i の場合の数

と定義すると,

  •  dp[i+1][j] = len(j) \times \sum_j dp[i][j] - dp[i][j] ( j 番目の範囲は  A_i 以下)
  •  dp[i+1][j] = 0 (otherwise)

となる.

あとはこれを高速に計算していきたいので,

  • 区間
  • 各ノードごとに事前に決められた係数 ( len(j)) の倍数を区間加算
  • 区間更新
  • 区間の値を負にする

に対応した遅延セグ木を書くと良い.

時間計算量  O(N \log N)

atcoder.jp

感想:ずっと定数倍 TLE.頑張って遅延セグ木を非再帰にしてみたものの TLE.ACL を使ってみたら AC.一生懸命育ててきた自分の木を裏切ってしまった感じがしてとても悲しい.ACL 速すぎる.

パソコン甲子園 順位表 まとめ

2023 予選

https://web.archive.org/web/20230909072222/https://radon.u-aizu.ac.jp/pckosien/stats/pck2023pre_standings.html

2022 本選

web.archive.org

web.archive.org

2022 予選

web.archive.org

2021 本選

web.archive.org

web.archive.org

2021 予選

web.archive.org

2020 本選

パソコン甲子園 2020 本選

drive.google.com

drive.google.com

https://radon.u-aizu.ac.jp/pckosien/stats/pck2020final_standings.html

パソコン甲子園 2020 もうひとつの本選

drive.google.com

drive.google.com

https://radon.u-aizu.ac.jp/pckosien/stats/pck2020fpub_standings.html

JOI 2007 春 2-3 SALT TREE XV 証明付き解説

(個人的には珍しく) まじめに証明を書く.

問題概要

2 人のプレイヤーが交互に,木に対して次の操作を行っていく.

  • 辺を 1 つ削除する.
  • 頂点を 1 つ削除する.その頂点が辺を持つならそれらの辺はすべて削除する.

操作ができなくなった方が負けである.

先手に必勝法があるので,それを実装せよ.(インタラクティブタスク)

https://www.ioi-jp.org/camp/2007/2007-sp-tasks/2007-sp-day2_21.pdf

解法

相手の手番に回すとき,(頂点の数, 辺の数) = (偶数, 偶数) となるようにする.

証明①

今,(頂点の数, 辺の数) = (偶数, 偶数) の場合,1 回の操作後に (頂点の数, 辺の数) = (偶数, 偶数) にできないことを示す.

  • 辺の削除を行ったとき,辺の数が奇数になるから不適.
  • 頂点の削除を行ったとき,頂点の数が奇数になるから不適.

よって,(頂点の数, 辺の数) = (偶数, 偶数) の場合,1 回の操作後に (頂点の数, 辺の数) = (偶数, 偶数) にできない.

証明②

今,(頂点の数, 辺の数) = (奇数, 奇数) の場合,1 回の操作後に (頂点の数, 辺の数) = (偶数, 偶数) にできることを示す.

辺の数が奇数であることから辺は少なくとも 1 つ存在し,葉が少なくとも 1 つ存在する.この葉を選べばよい.

よって,(頂点の数, 辺の数) = (奇数, 奇数) の場合,1 回の操作後に (頂点の数, 辺の数) = (偶数, 偶数) にできる.

証明③

今,(頂点の数, 辺の数) = (偶数, 奇数) の場合,1 回の操作後に (頂点の数, 辺の数) = (偶数, 偶数) にできることを示す.

辺の数が奇数であることから辺は少なくとも 1 つ存在するから,この辺を選べばよい.

よって,(頂点の数, 辺の数) = (偶数, 奇数) の場合,1 回の操作後に (頂点の数, 辺の数) = (偶数, 偶数) にできる.

証明④

今,(頂点の数, 辺の数) = (奇数, 偶数) の場合,1 回の操作後に (頂点の数, 辺の数) = (偶数, 偶数) にできることを示す.

すべての頂点の次数が奇数だと仮定すると,頂点の数が奇数であることから,次数の総和が奇数となるが,これは (次数の総和) = (辺の数) × 2 と矛盾する.
すなわち,次数が偶数の頂点が少なくとも 1 つ存在するから,それを選べばよい.

よって,(頂点の数, 辺の数) = (奇数, 偶数) の場合,1 回の操作後に (頂点の数, 辺の数) = (偶数, 偶数) にできる.


木において (頂点の数) = (辺の数) + 1 であるから,頂点の数と辺の数の偶奇は異なる.よって,最初の状態では (頂点の数, 辺の数) ≠ (偶数, 偶数) である.

以上の 4 つの証明より,相手の手番を常に (頂点の数, 辺の数) = (偶数, 偶数) にできるが,勝つためには頂点が 1 つだけ残っている状態で手番が回ってこなければならないから,相手は絶対に勝つことが出来ない.

N ≦ 2,000 より O(N2) が間に合うので,実装は雑でよい.

ABC 152 F Tree and Constraints 解説

パスを求める

dfs をして v[i] -> u[i] のパスを求めておく.このパス上に含まれる辺の集合を p[i] と置く.

問題の言い換え

以上により,この問題は次のように変換された.

N-1 個の白い辺があり,いくつかを黒く塗る.このとき,各 i (1 <= i <= M) について集合 p[i] に含まれる辺のうちいずれか一つは黒く塗られていなければならない.

bitDP

状態の持ち方は dp[N-1][2M] といった感じ.

各辺を順番に見ていく.今 dp[i][s] だとして,遷移は次の 2 パターンがある.

  • その辺を黒く塗らない dp[i+1][s]
  • その辺を黒く塗る dp[i+1][s2]

ただし,もしその辺が M 個の集合 p のいずれかに含まれていたら,s の対応する bit を立たせる.(立たせたものが s2)

最後に,n == N-1 のとき,s のすべての bit がちゃんと立っていれば return 1,立ってなかったら return 0.

時間計算量

  • パスを求める部分の計算量が O(NM)
  • bitDP をする部分の計算量が O(N 2M)

よって,全体では O(N(M+2M))

ソースコード

atcoder.jp

ABC 155 F Perils in Parallel 解説

まず思うこと

ソートしても題意が変わらないので,ソートします.(頻出中の頻出なので普通やる.)

ついでに座標圧縮もしちゃいましょう.

これで,問題が次のように変わりました.

爆弾が N 個あり,i 番目の爆弾は座標 i にある.各爆弾のオンオフ状態は s[i] である.
コードが M 本あり,j 番目のコードを切ると爆弾 l[j] 以上 r[j] 未満が切り替わる.(ついでに半開区間に変えた.)

ちなみに,この問題の場合,座標圧縮はしなくても解ける気がしますが,思考しやすくなるので題意が変わらないのなら圧縮すればよいです.

ゴールを見据える

便宜上,配列 s の前後に番兵を置いて,書き並べてみます.例えば

01101001100

こんな感じ.この隙間に注目します.

01101001100
^^^^^^^^^^^^

例えば,最初の部分,

01

これらは値が一致していませんが,最終的には 00 と値を一致させたいわけです.
よって,どちらかだけのオンオフを切り替える必要があります.
つまり,l[j] または r[j] がこの隙間を指し示すコードを奇数本切る必要があります.

逆に,隣接する値が一致している隙間では,コードを切る必要はありませんが,偶数本のコードを切ってもよいです.

グラフとみる

ここですこしひらめきが必要ですが,この隙間をノード,コードを辺とみて,その部分グラフを取ることにします.
部分グラフに選ばれた辺と切るコードが対応しています.

このとき,左右が一致していない隙間では,そのノードから出る辺を奇数本選択する必要があり,
左右が一致している隙間では,そのノードから出る辺を偶数本選択する必要があります.

DFS

辺を奇数本選ばなければならない頂点①から,DFS をして,他の辺を奇数本選ばなければいけない頂点②にたどり着きます.そのパスのコードをすべて切ることにします.

①―〇―〇―〇―〇―②

例えばこんな感じのパスの辺を部分グラフに選んだ (対応するコードを切った) として,ちゃんと①②から出ている辺は奇数本,〇から出ている辺は偶数本になっています.

なお,コードはつなぐことができると考えても問題ありません.

時間計算量がやばい

上の解法だと,O(N(N+M)) かかってしまい,困ります.

要は s[i] = 1 になっている辺同士のパスを見つければ (作れば) いいわけです.

適当な部分木を取って根つき木にします.

辺が奇数本でないといけない各頂点について,深い方から少しずつ上っていきます.別の上ってきた誰かと鉢合わせたら無事ペア成立,パス完成です.

ソースコード

atcoder.jp