UCHIDA Masatoshi uchidama
uchidama
/ abc217_e.py
Last active
September 6, 2021 13:17
AtCoder Beginner Contest 217 [ E - Sorting Queries ] https://atcoder.jp/contests/abc217/tasks/abc217_e
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| ''' | |
| [問題] | |
| https://atcoder.jp/contests/abc217/tasks/abc217_e | |
| [参考] | |
| https://atcoder.jp/contests/abc217/editorial/2577 | |
| 公式解説のロジックをPythonにコンバート | |
| PythonのQueueモジュールの使い方【初心者向け】 | |
| https://techacademy.jp/magazine/18995 |
uchidama
/ abc217_d.py
Last active
September 4, 2021 16:36
AtCoder Beginner Contest 217 [ D - Cutting Woods ] https://atcoder.jp/contests/abc217/tasks/abc217_d
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| import sys | |
| import bisect | |
| import array | |
| input = sys.stdin.readline | |
| L, Q = map(int, input().split()) | |
| # arrayのほうが、listより追加処理が速いようだ。約1/3軽量 | |
| A = array.array('I', [0, L]) |
uchidama
/ abc163_d.py
Created
August 15, 2021 09:50
AtCoder Beginner Contest 163 [ D - Sum of Large Numbers ] https://atcoder.jp/contests/abc163/tasks/abc163_d
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| ''' | |
| [問題] | |
| https://atcoder.jp/contests/abc163/tasks/abc163_d | |
| [解説] | |
| https://youtu.be/HVuSp_IhNZA?t=5554 | |
| なるほど感 | |
| https://atcoder.jp/contests/abc163/submissions/24993818 | |
| ''' |
uchidama
/ edpc_l.py
Created
August 10, 2021 15:39
Educational DP Contest / DP まとめコンテスト [ L - Deque ] https://atcoder.jp/contests/dp/tasks/dp_l
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| ''' | |
| [問題] | |
| https://atcoder.jp/contests/dp/tasks/dp_l | |
| [解説] | |
| https://kyopro-friends.hatenablog.com/entry/2019/01/12/231000 | |
| dp[i][j]=(区間[i,j]が残ってるときの「次の手番の人の得点－そうじゃない方の人の得点」) | |
| とすればよさそうだね。実装はメモ化再帰が簡単かな。 | |
| 計算量はO(N^2) |
uchidama
/ abc213_d.py
Created
August 8, 2021 16:08
AtCoder Beginner Contest 213 [ D - Takahashi Tour ] https://atcoder.jp/contests/abc213/tasks/abc213_d
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| ''' | |
| [問題] | |
| https://atcoder.jp/contests/abc213/tasks/abc213_d | |
| [結果] | |
| PyPy3(7.3.0) AC 1169ms | |
| Python(3.8.2) AC 1151ms | |
| ''' | |
| import sys |
uchidama
/ abc162_d.py
Created
August 7, 2021 14:44
AtCoder Beginner Contest 162 [ D - RGB Triplets ] https://atcoder.jp/contests/abc162/tasks/abc162_d
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| ''' | |
| [問題] | |
| https://atcoder.jp/contests/abc162/tasks/abc162_d | |
| [解法] | |
| AtCoder Beginner Contest 143 [ D - Triangles ]をPythonで解く | |
| https://uchidama.hatenablog.com/entry/2021/08/06/150713 | |
| この問題に似てる。 | |
| 1 <= N <= 4000 |
uchidama
/ abc143_d2.py
Last active
August 6, 2021 08:10
AtCoder Beginner Contest 143 [ D - Triangles ] 想定解 https://atcoder.jp/contests/abc143/tasks/abc143_d
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| ''' | |
| [問題] | |
| https://atcoder.jp/contests/abc143/tasks/abc143_d | |
| [解説] | |
| https://youtu.be/3U_N7zelnMM?t=2984 | |
| https://img.atcoder.jp/abc143/editorial.pdf | |
| a, bを総当たり(2 * 10^3)^2 で 4 * 10^6 |
uchidama
/ abc143_d1.py
Last active
August 6, 2021 05:00
AtCoder Beginner Contest 143 [ D - Triangles ] numpy + njit AC Code, https://atcoder.jp/contests/abc143/tasks/abc143_d
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| ''' | |
| [問題] | |
| https://atcoder.jp/contests/abc143/tasks/abc143_d | |
| [解説] | |
| https://atcoder.jp/contests/abc143/editorial/652 | |
| O(N^3)解法を、やってみる | |
| numpy + njitを使わないと、計算速度間に合わない。 | |
| これでTLE回避できるのかー。 |
uchidama
/ abc144_d.py
Created
August 5, 2021 04:55
AtCoder Beginner Contest 144 [ D - Water Bottle ] https://atcoder.jp/contests/abc144/tasks/abc144_d
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| ''' | |
| [問題] | |
| https://atcoder.jp/contests/abc144/tasks/abc144_d | |
| 数学問題 | |
| [解説] | |
| https://blog.hamayanhamayan.com/entry/2019/10/27/233430 | |
| https://img.atcoder.jp/abc144/editorial.pdf | |
| ''' |
uchidama
/ edpc_k.py
Created
August 4, 2021 08:09
Educational DP Contest / DP まとめコンテスト [ K - Stones ] https://atcoder.jp/contests/dp/tasks/dp_k
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| ''' | |
| [問題] | |
| https://atcoder.jp/contests/dp/tasks/dp_k | |
| [解説] | |
| https://blog.hamayanhamayan.com/entry/2019/01/09/002200 | |
| dp[k] := k個の石からなる山で先手が勝ち状態か(=1なら勝ち状態） | |
| 後退解析の基本は「遷移先がすべて勝ち状態なら負け状態。遷移先に1つでも負け状態があれば勝ち状態」である。 | |
| あるdp[k]について、遷移先は100通りあるので、このすべてを見て、負け状態が1つでもあれば勝ち状態にする。 | |
| 注意すべきなのは、遷移することができない（遷移先が無い）場合は、操作を行えないということなので負け状態とすること。 |