競技プログラミング 竸プロ精進記 ABC021 B 嘘つきの高橋くん Python 3
問題：一見グラフを使う経路問題で難しそうに見えるのですが、実際にはサンプルケースの中で紹介されているNG事例を一つずつ言われた通りに対処すれば簡単に解ける問題です。すなわち、経路として与えられる数列の中にダブりがないこと。そしてもう一つが出...
アルゴリズム
競技プログラミング 競技プログラミング ABC136 C Build Stairs Python 3
問題：与えられた数列の各要素に対して、そのままにするか、数を１減らすか選択していき、うまく単調に増加する階段を作ることができるか判定する問題。一手ずつ見落としなくシミュレーションすれば解ける問題。コード例左側から順番に確認していきます。N=...
競技プログラミング ABC115 Christmas Eve Python 3
問題：ランダムに並んだN個の整数列の内から、K個の整数を選び、選んだ整数の中での最大値と最小値との間の差が最小になる値を回答する問題。N,Kともに10^5オーダーなので、まともに組み合わせを全探索していてはとても間に合いません。しかし数列を...
競技プログラミング Pythonで実装するユークリッドの互除法 最大公約数の計算
最大公約数：ユークリッドの互除法整数A,B間の最大公約数(Greatest Common Divisor : GCD)は「ユークリッドの互除法」で求めることができます。下記はpythonでの実装例です。a,b=map(int,input()...
競技プログラミング Pythonで実装するエラトステネスの篩：素数の高速列挙
エラトステネスの篩ある正の整数N以下の素数を高速で求めるアルゴリズムです。計算量はO(NloglogN)となります。python 3でのコード例。N=int(input())A=list(range(2,N+1))p=list()while...
競技プログラミング 競技プログラミング なぜ問題が解けないのか？
何故問題が解けないのか 競技プログラミングを2020年4月に始めて、2か月半くらい経ちました。ほぼ毎週末行われる、Atcoder Beginner's Contest (ABC)のほか、週1回職場のソフトウェア部隊のバーチャルコンテストに混...