変換するということである。以降、この変換が施された後の値を「標準形」と呼ぶことにする。ある標準形の値について、掛け合わせると立方数となる標準形の値を「補数」と呼ぶことにする。交換することで得られる。全て標準形に変換したときに同じ値のものを1つの頂点とする。するとこの頂点から張られる辺は、補数からなる頂点のみとなる。補数からなる頂点も同様なので、2つのうちどちらか1つは選ぶことができる。よって標準形が同じものを一まとまりにし、補数の集合と要素数が多い方を貪欲に選べばそれが最適解となる。集合だけは例外で、ここからは1つだけ選ぶことができる。高速化しかし、これを愚直に実装すると間に合わない。そこで何らかの高速化をする必要がある。標準化だが、これは以下のような高速化をした。以下であるものを前計算で列挙する。この全要素について割れるだけ割る。個なので、これで間に合う。あとは補数を高速に求める必要があるのだが、この方法が思いつかなかった。以下の素数を前計算で列挙したものをダメ元で出してみたら、なんと通ってしまった。以下のコードは2582msで動く(制約は5000ms)。想定解ではないけど、本番もこれくらいの実行時間の人がそこそこいたのでセーフってことで。0;}感想ガチで高速化したら1100点なんだろうなぁ。上の解法は900点くらいな気がする。考察パートだけで部分点がほしいね。累計4時間くらいの考察でようやく解法に至った。