考えたこと ・初期地点も都市として扱い、都市のリストに追加。それらを位置でソートする。 ・両端の都市の距離を用いて二分探索で隣り合う都市間の距離を割った余りが０になるように設定するとよいのでは？二分探索（O(logN)）と各都市間距離を見ていく（O(…

リストのコピーはコストが少なくともコピーする要素分かかる。 リストのコピーを作るのは、リストをいじる必要がある場合かつ、コピー＆いじる操作を含めて時間内に処理が終わる程度のデータ数に対してのみ。それ以外はいのす法みたいに最後にまとめて処理す…

AB2だけAC、CはTLE、Dはそもそも見てない。 ◆Cについて ・「一つを好きな値に変える＝取り除く」までは分かったので、残りに対して二分探索で最大公約数を求めようとしたがTLEから抜けられなかった。選んだ要素の左右の配列について最大公約数を求め、両者の…

四月頭から参加＆過去問解き始めて３５～１００番までABC-C問題に挑戦したけど、なんか少ない。 とおもったらARCのAに反映されてた。

過去問をちょこちょこ解いているのだがちょっと詰まったので忘備録。 ・最初はbreakで抜けるのではなく、indexを超える場合はappendしないようにしていたが、ループ回して何もしないのは無駄なので容赦なくbreakする。 ・setを使うと元のlistの順番は保証さ…

蟻本で出てきた。ダイクストラとかはまだちょっと飲み込み切れてないけどこれは割と簡単だと思った。 ノードiからノードjに行くまでに、ノードkを経由するかしないかの距離短い方を全ノード間について選んで、最短経路を求める感じ。 i->jまでが距離xなら、d…

aaa = list(range(10)) for i in aaa: print(i) if i == 4: aaa.remove(i) ＝＝＝＝出力＝＝＝＝ 0 1 2 3 4 6 7 8 9 ＝＝＝＝出力＝＝＝＝ で5が出ない。 aaa = list(range(10)) for i in aaa.copy(): print(i) if i == 4: aaa.remove(i) ＝＝＝＝出力＝＝＝…

蟻本読んでたら出てきたのでC++からpythonにした。 同じ集合に所属するかどうか（Union-Find！）や、集合を合体するときに使う構造らしい。 練習問題も後日解いてみよう。 class UnionFindTree: def __init__(self, n): #親のノード番号を入れる。初期値はす…

ABC１２３からAtCoderを始めた。Cまで解けたがコンテスト参加回数が少ないとランクが著しく低く出るということで、現在は灰色（最低）ランクだ。 過去問もちょこちょこ解いてみたりしている。 A,Bは基本的に解けるが、Cは解けないもののほうが多い。Dはわか…