コンテンツ構成:
アルゴリズム・思考回路・関連知識の深掘り 28分
ライブコーディング説明(Python) 25分
模範コード(Python, C++)
レクチャーのpdf
何が学べる:
IOI(国際情報オリンピック)金メダリストの思考回路
難問へのアプローチの仕方
重要トピックへの深い理解
関連する基本知識への深い理解
対象:
実際のトップ企業の面接でどんな問題が聞かれ、どこまでできるべきか、ゴールを知りたい方
Easyは一通り解けるが難し目のMediumになると解けなくなる
最適解に辿り着くのに時間がかかる
自分で結構問題を解いてきたが飛躍が見えない
今日は、GoogleシートやExcelのようなスプレッドシートアプリケーションの、はるかにシンプルなバージョンを作ります。それをOpenSheetと呼びましょう。OpenSheetのセルは、整数(int)か、二つのセルを合計する数式か、この2種類のみを持つことができます。
この機能を処理するプログラムを書く任務があなたに与えられます。このプログラムをどのように構成するかは、自由に決定できますが、任意のセルを呼び出せるsetter/getterのメソッドを必ず実装して下さい。すべての入力は文字列(string)として提供されます。
setterの場合は、セルの番地とセルの値の2つの入力が与えられます。
setterの例
set_cell("C1", "45")
set_cell("B1", "10")
set_cell("A1", "=C1+B1")
getterに関しては、呼び出される際、セルの番地が入力として与えられます。
getterの例
set_cell("C1", "45")
set_cell("B1", "10")
set_cell("A1", "=C1+B1")
get_cell("A1") # この場合は55を返すべきです
前提条件
メモリ内ストレージ
すべてのセルの番地の入力は正しく与えられます(コードで検証する必要はありません
すべてのセルの値の入力は正しく与えられます(コードで検証する必要はありません)
セルの値の入力は、他の二つのセルの合計か整数のいずれかです
空白セルにアクセスする場合は、その値は0として扱われます
依存関係をグラフにする
有向グラフと無向グラフの違い
DFS(深さ優先探索)
メモ化
グラフにおけるサイクル検出アルゴリズム
バックトラッキング
キャッシュ
計算量
面接時の評価基準(どこまでできたらどんな評価がもらえるか)
この問題に関連する他の良問リスト