・相手の取得するマス目を減らすように行動する→相手よりそのマス目に近ければ取得できる ・DFSするときは再帰の回数を増やしておく（いつも上限に達してRE出てから気が付くので気を付ける） atcoder.jp

in ~~ でやると100msだけ早くなったがまだ遅い。collectionsとか使う方がいいのだろうか atcoder.jp

考えたこととりあえず貪欲法的にポイントの高い寿司からK個選ぶ。選んだ中で小さいものを残りの選んでないネタの寿司のなかでもっとも大きいものといれかえる、を繰り返せばいいはずとは思ったものの、・残ったものの中で選んでないネタの得点の一番大きい寿…

ここ一か月でABC35~120のC問題に挑戦して４５からは自力で解けたか解説を見たかが残してあるので自力で解けてないものについて再挑戦する。 考えたこと 文字列は長さが１０までなので、数字の間に＋を入れるか入れないかで2^9通りなので、全パターン試して十…

再帰的な処理は多少かけるが、深さ優先探索を実装することがうまくできないことが多いので、すこしまとめてみた。 どんな時に使えるのか 「ある物/配列要素に対し操作1,2,3...のいずれかを行う（選ぶ/選ばないなど）」のパターン全列挙 いくつかの文字の中か…

自力では解けなかったのでカンニングした。 考えたこと 375とか537とかの753数の頭に3,7,5のどれかを付け足すと簡単にできそう。 いや、3557も753数。ベースとなる数字が753数とは限らない。 とりあえず3,5,7を適当に並べた数字を作るか。でもその方法が分か…

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

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

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

蟻本で出てきた。ダイクストラとかはまだちょっと飲み込み切れてないけどこれは割と簡単だと思った。 ノード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): #親のノード番号を入れる。初期値はす…