本講義では情報科学の重要な基礎となっているアルゴリズムとデータ構造に関して学習します．具体的には，

• アルゴリズムとデータ構造に関する基礎知識を習得する
• Pythonを用いて代表的なアルゴリズム・データ構造を実装する
• 講義内で学習した内容を元に応用的なコーディング課題に取り組む

ことを目的としています．この講義を通して

• 代表的なアルゴリズムの考え方を理解する
• その考え方をコードに落とし込む力を養う
• 競技プログラミング等，様々なコーディング課題に取り組める知識を積み上げる

ことができるように授業が設計されています．

本授業はハイブリッド形式で実施する予定です． 講義はZoomにて配信する予定です．講義の配信動画を視聴するためには，インターネット環境，およびブラウザが必要です．なお，従量課金制による通信費がかからないよう，無料で使えるWifi環境がある場所や定額制のインターネット接続環境で視聴することを強く推奨します．

講義配信用ZoomのURLは以下のドキュメントに記載します．ECCSアカウントでログインする必要があります．
https://docs.google.com/document/d/1AOyeNwbEqCOH-jNFO2pG8DROUDPC8FIkn6uLz6D0zRo/edit?usp=sharing

講義終了後の録画を見るためのURLも上記ドキュメントに記載してありますので，授業後に確認してください（授業終了から数時間後には共有する予定です）．

本講義を受講希望の方は以下のフォームより登録を行ってください．ECCSアカウントでログインしておく必要があります．また，単位習得のためにこの講義を受講する方はUTASでの登録を別途行ってください．

[受講の受付は終了しています．]

本講義を受講する場合，以下の知識，経験，および実験機器があることを想定しています．

• 基礎的なPythonに関するプログラミング技術がある．
  • 電子情報工学科，電気電子工学科の授業でいえば，2年生冬学期のプログラミング基礎演習，ソフトウェア1・2あたりを受講し，理解できていればOKです．
  • 基礎部分を補いたい方は，Pythonプログラミング入門もとても良いかと思います．
• trackでコーディングを行えるPC環境がある．OSに関しては問わない．ブラウザはChromeおよびFirefoxを推奨する．
• slackを使うことができる．講義内でアナウンスはこのホームページの他，slackでも行います．
• zoomを使うことができる．講義の配信はzoomにて行います．なお，ECCSアカウントが必要です．

本講義では，工学部2号館246教室でオフラインでの講義を行い，同時にオンラインでの配信を行います．246教室で受講を希望する方は，モバイルアプリMOCHAをご自身のスマートフォンにインストールし，事前に入室予約を行ってください．

https://mocha.t.u-tokyo.ac.jp

事前に入室予約を行っていない方には，教室の混雑状況によってその場で退室をお願いすることがあります．どうぞよろしくお願い致します．

本講義のオンラインでの受講にはECCSアカウント（xxxx@g.ecc.u-tokyo.ac.jp）が必須です．セットアップ後使用できるようになるまで少し時間がかかりますので，自分のアカウントの詳細がわからない，という人は以下の動画を確認し，講義開始までに準備をしておいてください．

https://www.youtube.com/watch?v=89_fjWDdzQ4&feature=youtu.be

成績の評価は以下のように行います．

• コードチャレンジ基本課題（全24課題）：34点
• 以下の2つの課題より選択：33点
  • コードチャレンジExtra課題（全11課題）
  • レポート課題（全1課題）
  • 両方提出した場合には点数の高い方を成績に利用
• 期末試験（70〜80分程度を予定，対面で実施予定）：33点

ただし，以下の制約に1つでも引っかかる場合，この講義の成績は「未受験」という扱いになります．もし，上記制約に引っかかる場合であっても自分の成績をつけてほしい場合は，個別に期末試験前日までに連絡をしてください．（もちろん成績は総得点によりますので，連絡をしたら必ず単位が来る，ということではありません．）

• コードチャレンジのうち，未着手のままの提出の回数が累積4回以上．
• Extra課題，レポート課題のどちらとも全て未提出．
• 期末試験を受験しなかった．

病欠，公欠等の理由により期限内の提出ができない場合，講義担当者へメールにて連絡をして，対応を相談してください．事前の相談がない場合は救済措置が難しいことをご承知おきください．

この講義は毎回2つのパートに分かれています．

• スライドを使った講義パート
• trackを利用したコードチャレンジパート

この講義では両パートに積極的に参加することが求められています．

講義はzoomを利用した配信します．授業開始5分前くらいからミーティングを開始させますので，準備ができ次第お入りください．

質問等がある場合は，授業のslackでコメントをしてください．

授業のzoom meetingに接続できない場合，utacのアカウントでzoomにログインしていることを確認してください．以下の方法でzoomのクライアントアプリでログインを先に行ってから，接続をすると問題なくいくとはずですので，お試しください．

Zoomの通常のサインイン画面からサインインする方法（アプリからサインインする場合はこの方法です）

1. Zoomの通常のサインイン画面で，「SSO」または「SSOでサインイン」と書かれた文字を探して押してください．

　・この画面のメールアドレス・パスワード欄にUTokyo Accountの情報を入力してもサインインできません．

2. 表示される画面によって手順が異なります．

　・「会社のメール」という欄が表示されたら，[UTokyo Account] を入力してください．

　・「会社のドメイン」という欄が表示されたら，u-tokyo-ac-jp と入力してください．

3. UTASなどと同じような東京大学のユーザ名とパスワードを入力する画面（安田講堂の画面）が出たら，UTokyo Account（10桁の共通ID）または xxxxxxxxxx@utac.u-tokyo.ac.jp の情報を入力してください

授業中及びその後の授業内容に関する質問は，slackで行ってください．

コマンドを利用することで匿名でメッセージを送ることができます．名前を出したくない場合は，その機能を使ってください．

また，講義担当者からは授業の理解度を図るために，授業中にslackで呼びかけを行いますので，リアクションしてもらえると嬉しいです．

成績のうち約1/3は，Extra課題を毎週提出するか，以下に示すレポート課題を期限までに提出することで与えられます．レポート課題を提出した上で，Extra課題を提出している方は，より点数の高い方を成績評価に利用します．

レポート課題の具体的な内容は以下のPDFを参照してください．

https://yatani.jp/teaching/lib/exe/fetch.php?media=2022algorithms:report.pdf

レポート課題の提出にはTurnitinを利用します． Turnitin以外での提出方法は認められません．Turnitinによる提出方法に関しては後日説明いたします．具体的な提出方法は，以下のページを確認してください．

https://yatani.jp/teaching/lib/exe/fetch.php?media=2022algorithms:submission.pdf

本講義のコードチャレンジではtrackというシステムを使います．trackはオンライン上でプログラミングに関する学習を行ったり，指定された課題に対して自分のコードを提出したりすることが出来ます．またコーディング自体をブラウザ上でできるようになっているため，コーディングに必要な環境構築等を行う必要がありません．

本講義ではPython3を使用します．trackではPython3.6.1がサポートされています（2021年3月現在）．それ以外の言語の使用は認めません．また，track以外のシステムを用いた課題提出も認めません．

コードチャレンジには2種類あります．

• 基本課題: 講義内で紹介された擬似コードの実装や変更を行うもの．授業の内容をしっかり追えばできるようになっており，受講者のほぼ全員に出来てほしい課題．
• Extra課題：授業の内容を踏まえた発展的な課題．競技プログラミングとかにも出てくる内容を含んだ，頑張ればできる腕試し的課題．

基本課題はぜひしっかりと取り組み，解いてください．その上でExtra課題にも取り組んでもらえればと思います．Extra課題はレポート課題との選択肢気になっており，どちらか一方を提出していただければ問題ありません．Extra課題を提出した上でレポート課題を提出した場合は，より点数の高い方を成績評価に利用します．

講義パート終了後すぐ，google formにより登録していただいたメールアドレスに対して，trackからのメールを配信します．そのメールに該当する回の課題を行うページへのリンクが記載されています．track上でのコーディング・デバッグ方法，および課題提出方法はこちらのPDFを参照してください．

メールはnoreply@tracks.runより配信されますので，メールクライアント等においてフィルタリング機能を設定している場合には，このメールアドレスからのメールを受信できるように予め設定をしてください．また，アドブロッカーなどを使用していると，ブラウザ上でうまく表示できなかったり，エラーを起こしたりすることがあります．この場合には，アドブロッカーを一時的に停止させてみてください．

trackにおけるトラブルが発生した場合は，slackにてTAさんに連絡をしてください．

コードチャレンジではいくつかのテストケースが予め設定されています．それらテストケースの通った数を元に，原則[配点]*[テストケース合格率]で点数を計算します．採点に特別な扱いがある場合には，その旨を問題文に記します．

頻繁にテストケースを実行し，デバッグを行ってください．これにより提出間際でのミスを防ぐことができる他，コードが自動保存されるので，万が一提出作業を行えなくても，最終保存されたコードを元に採点が行われます．

採点は最終提出物に対してのみ行われます．したがって，途中でどれだけミスをしていてもペナルティはありません．また，提出までにかかった時間の長短は採点に考慮されません．

Extra課題に関しては提出されたコードに対して後日類似度チェック等を行い，明らかに類似したコードがあった場合は，その全てに対してペナルティを課します．基本課題に関してはほぼ同じようなコードになるはずですので，このルールを直接は適用しませんが，類似度チェックは行います．また，指示に従った提出物になっているかのチェックも行います．

講義で使うシステムではコードをテストケースにかけた時点で，自動でバージョン管理します．コピペ等を行なった場合には，不自然にコード行数が増えたり，テストケースにパスする回数が突然増えたりするので，その辺りも必要に応じてチェックします．不自然な編集があった提出に関してはペナルティを適用することがありますので，十分気をつけてください．

与えられた基本課題においては，入出力や問題文で指示がある場合を除き，実装すべき処理において標準ライブラリや問題で指定されていない外部の関数やライブラリ等を使用しないでください． そのような提出物はテストケースに合格していても，採点されませんで注意してください．Extra課題においては，適宜外部の関数等を使っても良いものとします．

コードチャレンジの課題によってはコードの一部分（コーディング画面の初期コードとは別のコード）があらかじめ与えられている場合があります． その場合，問題文に明記してありますので，指示に従ってください．

コードチャレンジの課題を見ながら，本やWeb上の情報を参考にすることは問題ありません．ただし，記載されているコードなどをそのまま使うことのないようにしてください．また，友達同士で教え合うのも積極的に行ってください（教えることができる，というのは十分に理解できている証拠でもあります）．ただし，書いたコードを直接見せ合うのではなく，考え方だけを共有するようにしてください．

この講義で重要なのは，「自分で手を動かす」ことを大切にすることです．アルゴリズムやコーディングに自信がなくても，授業で紹介されている内容を理解し，努力すれば一定の評価につながるようになっていますので，後から誤解を招きかねない行為をしないようにお願いいたします．

提出物に対しては後日類似度チェックを行います．以下のような提出物は該当するものすべてに対して採点を取り消します．

• 提出物間でほぼ同一のコード
• Webや参考書に記載されているものとほぼ同一であることが判明したコード
• track上での課題取り組み時間（終了時刻 - 開始時刻）が極端に短い
• 与えられたテストケースに通るようにだけ設計されたコード
• その他，明らかに不正行為の証拠があるもの

悪質な場合にはより大きなペナルティになることがあります．十分気をつけてください．

コードチャレンジの締め切り後はシステムの仕様上，提出したコードにアクセスすることができません．後日こちらからgoogle drive経由で提出されたコードを返却します．テストケースも共有しますので，ご自身での自習に活用してください．

また，Extra課題に関しては，解答例と簡単な解説をその次の講義回にて共有します．基本課題は授業のスライドにある情報で実装できるようになっていますので，授業のスライドをよく確認してください．

手元，もしくはtrack上でより細かくどのテストケースでうまく行っていないかを確認するためには以下のようなコマンドを使用すると良いです．

python3 main.py < ./test/in/basic/[入力するファイル名] | (cat ./test/out/basic/[想定出力結果のファイル名] | diff /dev/fd/3 -) 3<&0

期末試験は原則対面です．期末試験の実施方法に関しては，ここで詳細を連絡をします．

過去の期末試験は，こちらに置いてあります．自習の参考にしてください．ただし，試験時間，大問・小問の数，解答形式，出題範囲，問題の難易度などは年度により変更がある可能性があります．授業中のアナウンスを十分よく確認してください．

https://drive.google.com/drive/folders/1Coxpw6JYwA09npRfTwq-Aa_XwlRTviq8?usp=sharing

期末試験座席表はこちらのとおりです．もし，受験予定で，自分の学籍番号がない場合は，至急矢谷まで連絡をしてください．

https://drive.google.com/file/d/1Y1Zuj9S2siGyqwQyXRGspjqmkVdZR8C2/view?usp=sharing

以下の情報をメールにて，algorithms “at-mark” iis-lab.orgに送ってください．可能な限り事前に，事後でも速やかにお願いします．

• 病欠，公欠を希望する授業日
• 病欠，公欠の理由
• 理由が正当なものであることを裏付けるもの（診断書，処方箋，出席する学会のプログラム等のスキャンデータ，感染症に関係するホットラインへの相談記録）

認められた場合，課題提出期限をこちらが指定する日時まで延長します．

大きな怪我や病気などの例外を除き，病欠，公欠を希望する授業日から1週間以上を経過した場合は，認めないものとします．

剽窃や不適切な引用，改竄などはAcademic Misconductとして重い処分を受けます．この講義ではコードチャレンジにおける提出物や，期末試験での答案における不正行為により不当に評価を得ようとする行為に対して特に厳重に処罰します．例えば，

• インターネット上にあるライブラリやサンプルのソースコードを引用することなく用いた，
• 他人が書いたソースコードを無断かつ引用なしに転用した，
• ほかの学生が書いた回答を盗み見て利用した．

などが挙げられます．特に重大なAcademic Misconductが発見された場合，その影響度の大きさに応じて以下の罰則を与えることになります．

• 不正が見つかった課題を不採点(0点扱い，既採点の場合は採点取り消し)，
• 今までに提出されたすべての課題を不採点，
• 今までに提出されたすべての課題を不採点，かつ以降の課題提出を認めない．

レポートやソースコードは誤解の生じないように十分注意して作成・管理してください．

以下の書籍・リンクはこの講義の資料を作る際に参考にさせていただいたり，講義内容に関する大きな刺激を受けたものになります．以下に挙げているもの以外にも参考になる様々な情報がありますので，興味を持ったトピックに関して色々とご自身で調べていただければと思います．

• プログラミングコンテストチャレンジブック 第2版．秋葉拓哉，岩田陽一，北川宜稔．
• プログラミングコンテスト攻略のためのアルゴリズムとデータ構造．渡部有隆，Ozy，秋葉拓哉．
• 新・明解Pythonで学ぶアルゴリズムとデータ構造．柴田望洋．
• 問題解決力を鍛える!アルゴリズムとデータ構造．大槻兼資，秋葉拓哉．
• 累積和を何も考えずに書けるようにする！
  • https://qiita.com/drken/items/56a6b68edef8fc605821
• 二分探索をはじめからていねいに
  • https://hcpc-hokudai.github.io/archive/algorithm_binary_search_001.pdf
• 二分探索アルゴリズムを一般化 〜 めぐる式二分探索法のススメ 〜
  • https://qiita.com/drken/items/97e37dd6143e33a64c8c
• ソートを極める！ 〜 なぜソートを学ぶのか 〜
  • https://qiita.com/drken/items/44c60118ab3703f7727f
• 典型的な DP (動的計画法) のパターンを整理 Part 1 ～ ナップサック DP 編 ～.
  • https://qiita.com/drken/items/a5e6fe22863b7992efdb
• プログラミングコンテストでの動的計画法
  • https://www.slideshare.net/iwiwi/ss-3578511
• Candies [Educational DP Contest / DP まとめコンテスト M]
  • https://www.hamayanhamayan.com/entry/2019/01/10/235150
• Union-Find木の解説と例題
  • https://qiita.com/ofutonfuton/items/c17dfd33fc542c222396
• 競技プロ的なアルゴリズムのスライドのまとめ
  • https://yukicoder.me/wiki/slide
• Atcoder tags
  • https://atcoder-tags.herokuapp.com/explain
• ICPC Challenge　実践的プログラミング (全学自由研究ゼミナール)
  • http://www.graco.c.u-tokyo.ac.jp/icpc-challenge/

またpythonの基礎の学習には様々なオンラインコースがありますので，それを活用することをおすすめします．

• https://www.python.ambitious-engineer.com/introduction-index#i-4
• https://www.python-izm.com/introduction/
• https://docs.python.org/3/
• https://www.learnpython.org/

ここでは講義中に出た講義に関係する質問とその返答を取り上げています．

• 数学2Dの演習の授業も同じ曜限に開講されていて、どちらも履修したいのですがそれは可能でしょうか？
  • 残念ながら認められません．EEICでは情報よりの興味をお持ちであれば「数学2G＋アルゴリズム」を取れるように授業が設計されていますので，ぜひご検討ください．
• 他学部，もしくは他学科の学生ですが単位取得のために講義を受講することは可能ですか？
• 大学院生ですが単位取得のために講義を受講することは可能ですか？
  • 所属する研究科，専攻に卒業要件としての単位取得が可能かどうかを確認した上で，UTASでの登録をしてください．

• スライドとは違うアルゴリズムで提出してしまったのですが減点等はありますか？
  • スライドや問題文の指定と違うアルゴリズムで提出した場合は，テストケースに通っていても採点されないことがありますので，問題文の指示をよくお読みください．
• 聞き逃したかもしれないのですが、採点結果はITC-LMSなどで見れますか？
  • 採点は[配点]*[テストケース合格率]が原則ですので，それで自分の点数がわかります．ただし，問題中で明確に指定されている要件を満たしていない場合，採点が取り消される，あるいは減点となります．
• 採点のフィードバックはありますか
  • 私達からの個別のフィードバックはこの講義のサイズでは難しいので，テストケースに通ったかどうかが一応のフィードバックになるようにしてます．
• 課題を終えるまでにかかった時間は評価に入りますか？
  • 考慮しません．
• 翌週に模範解答的なものは公開されますか
  • はい．Extra課題に関しては公開予定です．
• 課題についてWEB上のコードを参照して、そっくりじゃなくても似ているコードはいけませんか？
  • 自分自身で咀嚼した上で書いたコードだと判断してよいと第三者が見て言えるレベルにしてもらえればと思います．
• dequeやheapqなどは使用しない方が良いということでしょうか？
  • 基本課題ではその類のものは原則使用できません（ただし，別途指示がある場合を除く）．またExtra課題であっても，既存のライブラリの効率性に依存する提出（もしそのライブラリを使わないコードに書き換えた場合，テストケースに通らないことが容易に予想される提出物）は減点の対象となります．

• ネットワーク接続（コンテンツサーバー）の異常で受験できません
  • adblock解除で接続できた報告がありましたので，試してみてください．それでもエラーが出る場合はこちらに連絡をください．
• テスト実行で一度保存すればブラウザを一度閉じてもコードが保存されるということでしょうか
  • はい．そうです．不安ならローカルにコピーしておいてください．
• SyntaxError: Non-ASCII character ‘\xe3’ in file main.py on line 4, but no encoding declared というエラーが出る
  • どこかに日本語が入っているためだと考えられます． # coding: UTF-8を入れるといけるはずです．
• 「解答を完了」したあと、「試験を提出する」を押さないと、採点されなかったりますか？前回は「試験を提出する」を押し忘れたようなきがするのですが
  • 期限が来ると自動で提出はされますが，押してもらうほうが確実です．
• デフォルトで書いてあるコードは、特に気にしなくていいものですか？それとも理解しないといけない内容が書かれていますか？
  • 気にしなくてよいです．このコードを利用せずに提出しても問題ありません．
• sys.stdin やdefを使わずに、inputなどだけを用いて提出したのですが(テストケースには正解)、それでもよかったでしょうか
  • 問題ありません．デフォルトのテンプレートを消した上で，提出してもらって問題ありません．
• Ctrl+sでテスト実行されました
  • こちらも便利ですね！
• 後から復習できるようにtrack上の問題文をローカルに保存する方法はありますか？
  • とりあえずwebページをPDFとかに保存してもらえればと思います．（何かしらの方法で公開できないか検討中）
• コードを初めからやり直したいときにリセットする方法はありますか？
  • 右上の歯車のところにテスト環境を初期化というボタンがあります．

• Command terminated by Signal 9というエラーが出ます．
  • 多くの場合，メモリ制限に引っかかっているものと考えられます．どこか効率的でないメモリの使い方をしていないか，確認してみてください．
• Command terminated by Signal 11というエラーが出ます．
  • もし再帰を使っている場合は，以下のようにして再帰回数の上限とスタック領域を拡大してみてください．

import sys

import resource

resource.setrlimit(resource.RLIMIT_STACK, (-1, -1)) # スタック領域を拡大

sys.setrecursionlimit(1000000) # 再帰回数の上限を拡大