comodo

主にAtCoderの振り返りとか自分用のメモ

comodo

主にAtCoderの振り返りとか自分用のメモ

  • よく使う(自分用)

整数問題解法

このnoteは、AtCoder 版！マスター・オブ・整数 (素因数分解編)を読んでコード部分を抜き出したりしてまとめたもので、自分の勉強のためのみに書いたものです。 書き間違いなどあるかもしれませんが読む場合には自己責任でお願いします。 ・素数判定C++ bool is_prime(long long N) { if (N == 1) return false; for (long long i = 2; i * i <= N; i++) { if (N % i

comodo

    • zone2021 B問題

      B - 友好の印 この問題で必要な予備知識3つ 1. 直線の方程式は y = ax + b で表される。 2. a は変化の割合で、a = (yの増加量) / (xの増加量) と表される。 3. b は切片で、1. の式を変形すると b = y - ax と表される。 ・初期値座標 (0, 0) と座標(D, H) を結ぶ直線を考えると、a = (H - 0) / (D - 0) = H/D , より y = H/D * x となる。 当たり前ですが、遮蔽物が0個

      comodo

      • Python dequeを使ってみる

        PAST第6回 - E をPythonのListを使って解いたらTLEしてしまったので、Listより速いらしいというdequeを初めて使ってみた記録です ※自分用のメモです 参考にしたページ ・まずは宣言 from collections import dequeque = deque() ・先頭と末尾への追加 # 先頭que.appendleft(1)que.appendleft(0)# 末尾que.append(2)que.append(3)que.appen

        comodo

        • ABC199 C問題考察

          C - IPFL Ti = 1,2 の2種類のクエリが与えられますが、Ti = 2 の場合に毎回前後を入れ替えるという操作をすると時間がかかりすぎてしまうようです。 (具体的な計算時間については詳しくは知らないのですが) ちなみに、前後を入れ替えるという操作はC++,Pythonでそれぞれ以下のように書けますね。 // C++// s.length() == 2*ns = s.substr(n) + s.substr(0,n) # Python# len(s) = 2

          comodo

        整数問題解法

        comodo

        マガジン

        • よく使う(自分用)
          2本

        記事

          ABC198 A,B解説

          A - Div N個のお菓子を一列に並べて、どこかに仕切りを入れて左側をAくんが貰う、右側をBくんが貰う、という図を思い浮かべます。 N=4のとき、以下の図のようになります。 今回の問題では「両者とも1個以上得る」という制約があるので「|oooo」や「oooo|」といった位置に仕切りが来ることはありません。 N個並んでいるときに、仕切りを入れる位置として考えられるのはN-1箇所なので、答えはN-1になります。 (もし、問題の制約で「0個以上もらう」と書いている場合は

          comodo

          ABC198 A,B解説

          comodo

          隣接リスト(C++,Python)

          入力例1行目は頂点数n,辺の本数mが与えられる。次のm行の入力で、辺Eiが頂点Aiと頂点Biを結んでいるという情報が与えられる。 C++ # include <iostream># include <list>using namespace std;int main(){ int n,m; cin >> n >> m; list<list<int>> e; for(int i=0;i<n;i++){ list<int> tmp; e.push_back(tmp)

          comodo

          隣接リスト(C++,Python)

          comodo

          C++ メモ

          リストの実装 # 2021/03/15# include <iostream># include <list>using namespace std;int main(void){ list<int> x; for(int i=0;i<10;i++){ x.push_back(i*3); } for(auto i = x.begin(); i != x.end(); i++){ cout << *i << endl;

          comodo

          C++ メモ

          comodo

          ABC195(2021/03/14) 振り返り

          A - Health M Death 余りの演算子使えますか？ってだけ。 B - Many Oranges よくわからなかったからとりあえず提出してみたけどWA。 入力例2を見ると、2種類のみかんの組み合わせを考えて解くの...？みたいに思ってしまってだいぶ時間ロスしてしまった。 Cを先に解いてから考え直したらぎりぎりACできたから、以下その説明。 例えば、入力例「A=300、B=333、W=1」の場合だと、 1000gを構成するのが1つのみかんだと1つあたりの

          comodo

          ABC195(2021/03/14) 振り返り

          comodo

          Python メモ

          ・無限大と負の無限大# float型の無限大の値x = float('inf')# 負の無限大x = -float('inf') ・Counter() クラスの使い方from collections import Counterx = [3,4,4,5,6,3]c = Counter(x)print(c)for a,b in c.items(): print(' %d : %d' % (a,b)) # Counter({3: 2, 4: 2, 5: 1, 6: 1})#

          comodo

          Python メモ

          comodo

          ABC194(2021/03/06) 振り返り

          A - I Scream else ifで条件分岐を書き並べるだけ？思った通り書いてみた。 B - Job Assignment 入力で、min(Ai+Bi)を解として一旦保存しとく。そこから、min(Ai,Bj)(i!=j)の中で最小のものを探して解と比較したいけど、どうやって...? って思ったけど、先週のABCで「困ったら全探索！！」ってなったのを思い出して(先週は素直に全探索しておけばよかったところを無駄に色々考えて反省してる)、とりあえず全探索してみたら普通

          comodo

          ABC194(2021/03/06) 振り返り

          comodo

          2021/03/03 今日の進捗

          アルゴリズム実技検定の電子書籍版を買ったので、最近読み進めています。 競プロ始めたての人向けの解説が多くて、すごく読みやすいです。 全探索とか、自分がわかってる部分はスラスラ読み進めて、問題のグラフ理論へ。 隣接行列の実装方法はわかっていたけど、隣接リストの実装はしたことが無かったので、隣接リストを使いながら、テキストに載っていた、PAST第3回のE問題を実装してみた。 問題リンク 頂点の値を書き換えていく問題。こういうのって、最後に全頂点の情報を出力するのかと思っ

          comodo

          2021/03/03 今日の進捗

          comodo

          ABC193(2021/02/27)振り返り

          A問題、B問題 難なく実装。 C問題 テストケースが、100000→99634だったから、a^bで表せない数を見つけるより、表せる数366個を見つけるほうが速そうだと推測(ここまでは合ってた)。 2 , 2^2 , 2^3 , ... , 3 3^2 , 3^3 , ... と数えていくが、4 , 4^2 , 4^3 , ... は 2^2 , 2^4 , 2^6 , ... と被るから除外したほうが良さそう。 つまり、平方数を除外する。 と思って書いてみたけど、

          comodo

          ABC193(2021/02/27)振り返り

          comodo