cplib-cpp
cplib-cpp copied to clipboard
hitonanode
C++ competitive programming library
TSP
- 問題例 - [DMOPC '21 Contest 5 P5 - Permutations & Primes - DMOJ: Modern Online Judge](https://dmoj.ca/problem/dmopc21c5p5) - [A46 - Heuristic 1](https://atcoder.jp/contests/tessoku-book/tasks/tessoku_book_at) - 変形版 [A - ツーリストXの旅行計画](https://atcoder.jp/contests/rco-contest-2019-qual/tasks/rco_contest_2019_qual_a) - 厳密解 -...
- SRM 841 Div.1 1000 - 辞書順の条件がつくので考慮が必要 - https://yukicoder.me/problems/no/1069 - https://qiita.com/nariaki3551/items/821dc6ffdc552d3d5f22
- https://maspypy.com/slope-trick-3-slope-trick-%e3%81%ae%e5%87%b8%e5%85%b1%e5%bd%b9 - https://yukicoder.me/problems/no/2114/editorial
- 特徴量を突っ込んで答えを得たい、小さいケースは愚直にやって大きいケースは外挿したい - 動機： https://atcoder.jp/contests/arc151/tasks/arc151_f - 人の目で見て明らかに区分線形関数のときとか、偶奇で分ければそれぞれ線形関数、とかであれば原理的にはできるはず（？） - 特徴量全部盛りで特徴量-to-答えの mapping を作ると、小さいケースには存在しない（しかし難しいケースではない）ような特徴量の組み合わせが大きいケースで出てきたとき困るので、最小限の特徴量で答えが得られるような決定木を学習できるようにしておきたい - 使えそうな手法 - ID3 - CART - 本当はカテゴリ毎に線形関数を学習したい https://atcoder.jp/contests/abc271/tasks/abc271_h - MARS (Multivariate Adaptive Regression Splines) - 特徴量全部盛りでカテゴリ毎に線形関数を学習し、カテゴリ同士をマージできるか見れば良い？ - 各カテゴリが劣決定なとき愚直にやるとあまりうまくいかない気がする