問題が解けない原因を考えたい
背景
競技プログラミングの能力を鍛えたい。
ただ、何ができなくて解けなかったのか？や、問題の難しい部分はどこなのか？など簡単な抽象的・体系的でとらえたいお気持ち。
なんとなく思ったことがあるので、それを書き出して整理してみる。
「アルゴリズムを考えること」
「アルゴリズムを考えること」＝「"問題"と"アルゴリズム"を辺でつなぐこと」
"問題"が与えられたとき、"問題"を"分解または言い換え"て、アルゴリズムの"使い方や制約"を踏まえて"アルゴリズム"を適用する。
ただし、"問題"以外のノードは与えられないため、自分で利用可能なノードを増やす必要がある。
問題が解けない＝辺をつなぐのを失敗すること
"問題"から"アルゴリズム"までの辺を貼ることに失敗すると問題を解くことができない。
「分解・言い換え」のノードが足りない
"問題"を「グラフにして考えてみたり」、「複数の問題に分解したり」することに失敗。
ここの部分のノードの作り方が難しい問題は、「難しい」問題の印象。
「使い方・制約」のノードが足りない
アルゴリズム自体は知っていても、その"使い方や制約"をきちんと理解できておらず、適用できない。
例えば、動的計画法というアルゴリズムは知っていても、その使い方で「状態設計」「遷移」「高速化」などがちゃんと考えられないと、ノードが作れず、辺を貼るのに失敗する。
辺が張れていない、間違って張ってしまった
ノードは用意できてもノードとノードの関連性をちゃんと理解できていないと張れると気付かなかったりして失敗。
また、張れると思って張ったら実は嘘解法で張れない辺を張ってしまって失敗。
勉強すべきこと
問題が解けない時、「ノードが足りていない」のか、「辺が張れなかった・間違って張った」のか考えたい。
ある程度、頻出パターン(頻出ノード、頻出エッジ)があるようで、効率的に勉強するには頻出パターンから攻めたほうがよく、「"使い方・制約"と"アルゴリズム"」の部分は体系的にまとめられている。
他には、グラフ系・文字列処理系・幾何系など特定分野に絞って勉強するのもよいのかも。
”分解・言い換え”ノードを増やす
あんまり体系的にまとまっていない気がするし、問題に合わせて考える考察力・発想力が問われる気がする。
"問題"側から"分解・言い換え"側を考える場合は、いろんな問題を解いていろんな言い換えや分解方法を憶えておくか、それらの発想の基となる既存の理論・学問を勉強したりとかが必要なのかも。。。
"使い方・制約"側から"分解・言い換え"側を考えることもできるかもしれなくて、ある程度関係ありそうなノードを考えて辺が張れるか考えてみたり。
また、小さいパターンで実験してみて問題に含まれるパターンを見つけたりというテクニックとかも有効かも。
典型とかもあって、「絶対値を見たら45度回転」とか「Nが小さければbitで2^N全探索できないか」とか、こう来たらこう考える、みたいなのもあるっぽい。
