【10日目】ABC197のE,Fを振り返る

昨日の続きということで、今日はEとF問題。これらは完全にアルゴリズムを思いつかず解けなかった。どういう発想が必要だったのか考察してみる。

E - Traveler

「同じ色のボールをどういう順番でとるかがカギだな」「各色について、取り方は高々2通りしかないな」というところまでは至ったものの、そこで行き詰ってしまった。

この問題の場合、i色目までを取った段階で考えられる状態は2通りしかないので、その2通りについてi色目までを取り終える最短時間を帰納的に求めることでO(N)時間で解が求まるのだが、「各色について2通り→全部で通り」という考え方をしてしまったので、そこで行き詰ってしまった。要は「過去の遷移」と「現在の状態」をごちゃまぜにしてしまったわけだ。

F - Construct a Palindrome

これは自分で新しいグラフを作らなければならない系の問題。この手のはまだまだ弱い。長さkの回文でつながっている２つの頂点の組(i, j)を順に列挙、、とやってTLEになったが、ここをもう一歩進んで「だったら(i,j)をノードに持つグラフを作ればよい」と考えられるかが今後の課題。そこのワンステップを踏み出せればその先はそこまで苦戦せずに解ける気がしているのだが。

どちらも今の段階では自力解決は難しい。「こういう問題ではこうする！」みたいな一般化もまだできない。慣れがまだ必要。

Fは明日実装する。あと明日は割と時間があるのでもう一つABCをやろうと思う。

それから、アルゴリズムを考えるだけでなく実装もより良いコードを書けるようにするために、他の人のコードを見て学ぶという方法も少しずつ取り入れていきたいと思っている。具体的には解説のコードやレッドコーダーの人のコードを覗いてみて。そう言う人たちのコードは自分にはパッと見ただけでは何をしているのか理解しきれないことが多いのだが、そこをじっくりと1行1行読み込んで、真似できるところから真似していきたい。