競技プログラミングで解法を思いつくための典型的な考え方 | アルゴリズムロジック

競技プログラミングの問題を解くためには２つのステップがあります。 問題で要求されていることを言い換える知っているアルゴリズムやデータ構造を組み合わせて解く 必要な（知っておくべき）アルゴリズムやデータ構造は色々なところで学ぶことができます。 しかし、「問題の言い換え」や「アルゴリズムを思いつく」というのは、非常に様々なバリエーションがあり、問題をたくさん解かないとなかなか身につきません。 そこで、この記事は以下のことを言語化し、練習のための例題を提示することを目標とします。 問われていることを、計算しやすい同値なことに置き換える方法アルゴリズムを思いつくための考え方競技プログラミングで「典型的」と思われる考え方 ※一部問題のネタバレを含むので注意 ※良く用いられるアルゴリズムやデータ構造については競技プログラミングでの典型アルゴリズムとデータ構造 を参考にして下さい。 入力の大きさ(制約)

[healthyprog]

こういうのはヒントではあるが、自分で試行錯誤した末にここに辿り着かないと身につかない気がしている。

[aceraceae]

競技プログラミングをやるつもりはないけど普段の実務でもまともにやると計算量が大変なことになるのをなんとかしなきゃならない場面がわりとあるんで引き出しは多く持っていたい。

[mamuchi]

実装後のコードより、そこに至る過程を考えるのはとても勉強になる。

[hnw]

競プロやったことない人、DPが何だかわかってない人には無意味な記事だと思うんだけど何でこんなに伸びてんの…問題サイズから解法特定とか実戦じゃありえないけど競プロでは基本戦法なんだよなあ。

[thaim]

これはよく疑問に上がる「どうやってその解法を思いついたんだ？」に対する回答では．問題例含めて確認したい．

[kastro-iyan]

これそのまま業務用のプログラミングにも応用できるな

[shimozun]

ある程度の経験者が「それな！」って確認する内容であって、これ見て勉強は難しいと思われる

[sbrtnpg]

家庭が落ち着いたら競プロちゃんとやりたいんです。嘘じゃないです。

[pokuwagata]

コンテスト中に詰まったら見ても良いかも

[sadness_ojisan]

どういうときにどう考えるか

[masa8aurum]

もしかして coding interview にも使える？

[masayuki14]

DPの壁にぶつかっているので乗り越えたら読むかもしれん。

[takilog]

ほえぇ

[knok]

転職時に試験として出すところもあるので、動的計画法、幅/深さ優先探索ぐらいは練習しておきたい

[gomer-pyle]

多分読まないけど

[ardarim]

これを全部丸暗記していつでも引き出せるくらいに咀嚼できていないといざという時に役には立たない知識だろうな。

[Bryntsalov]

あとで読む

[buhoho]

あとで読むー

[natu3kan]

受験数学とかもだけど、どれだけ問題を解いて実際に動かしてみて解法が体に染みついてるかって所はあるよなあ。

[t_nkjm]

すごくまとまってる

[hara_boon]

ぶこま

[programmablekinoko]

具体的で良い

[kagehiens]

ここにさらに自分のやり方を足してまとめたい。

[otoan52]

勉強しとこ

[virtualbox]

後で読む

[tumo300-500]

よさげ