D - String Equivalence

パナソニックプログラミングコンテストのD問題。 https://atcoder.jp/contests/panasonic2020/tasks/panasonic2020_d |s| = |t|である この意味は、オートマトンの記号で、sとtが同じ長さの文字列であることを示す。 再帰の場合 def solve(): N = int(input()) # ord("a") Unicode コードポイントを返す codepoint »

排他的論理和(XOR)が家のスイッチ

一回きたらon、またきたらoffって、普通のものって感じがするんだけど、仕組みを考えると難しい。 で、pythonでうまいこと実装するとこうなる switch = 0 # 1になる switch ^= 1 # 0になる switch ^= 1 どこから押しても明かりがついていると消えて、消えているとつくスイッチってよくあるけど、多分この仕組が使われている。 »

再帰

pypyはpythonよりも再帰が遅い。なぜかはわからないけど、そういうものと覚える。DFSなどでよく使われる。 よくあるのは「1からnの整数の和を返すプログラム」で、 def sum(n): if n < 1: return n return n + sum(n-1) s = sum(100) print("1から100の合計は", s, »

pythonとPyPy

今度はプログラミングコンテストをきっかけにpythonを使ってみている。 めちゃくちゃシンプルですごく好き。 禅を意識しているみたい。 プログラマが持つべき心構え (The Zen of Python)にまとまっている。 ~/D/g/p/python ❯❯❯ python >>>> import this The Zen of Python, by Tim »

spanner Read-Write Transactionの冪等性について

spannerのRead-Write Transactionは失敗した時にライブラリレベルで自動的にリトライされる。(golangの場合) リトライが走るともう一度BeginTransactionからやり直して、一からトランザクションを始めることになるため、トランザクションで実行している部分が冪等性を担保できているかどうかを確認する必要がある。 bad 実際にはありえないケースだが、例えばiを0で宣言して1を加算してinsertしたいケースがあるとする。 下記のようなパターンでは、ReadWriteTransactionがabort等によって再実行された際にiが再加算される。 冪等になっていないので、iが1にならない(リトライされるごとに2,3,4と増えていく)ことがある。 func write(ctx context.Context, w io.Writer, »

c++ + vscode

プログラミングコンテストの解説コードは圧倒的にc++が多い。 し、ちょうどいい機会なのでc++を使うことにした。 環境設定 基本的には、C/C++を入れて、Using Clang in Visual Studio Codeの通りにやればデバックまでできる。 だけど、catalinaの場合はうまくデバックが動かないので、ちょっと手間がいる。Can't debug on macOS Catalina (LLDB) #3829で議論されているけれど、 »

ABC156_D - Bouquet

abc156はC問題まですぐにできたけど、Dにずっと引っかかってしまった・・・ 回答を見てもわけがわからないので、わからない要素を分解していく。 繰り返し二乗法 繰り返し二乗法というのも重要なトピックである。 この記事が一番わかりやすかった。 累乗は、愚直に計算すれば計算数はO(n)となるが、これをO(logN)まで抑えることができる。 logってなんだ・・・ log 計算量オーダーの求め方を総整理!が良かった。 でもその前に対数について ”aを何乗したらbになるか”を表す数として定義される。 例えば、最もかんたんなlognとなるアルゴリズムは、下記の様なものになる。 for (int »

add two numbers

golangで60 questions to solveを説いてみるシリーズ。 今回の問題はAdd Two Numbers。 Add Two Numbers まずは自分の限界。 package AddTwoNumbers import ( "strconv" ) type ListNode struct { Val int Next *ListNode } func addTwoNumbers(l1 *ListNode, »

two sum

golangで60 questions to solveを説いてみるシリーズ。 今回の問題はtwosum。 two sum 最初の1問。 これって各言語ごとの回答とか、みんなの回答とか見れないのかな。 ここに転がってた。 Brute Force func twoSum(nums []int, target int) []int { for ni, i := range nums { for »

The Mastermind

高かったし話題の本だったから躊躇したけど、興味深かったので買った。 日本題は魔王。 原題は『The Mastermind』で、このほうが天才であり、首謀者である、というニュアンスをよく表していると思う。 サイバー麻薬王が築き上げた恐るべき犯罪帝国の全貌とは?それは、数億ドル規模の米オンライン薬局事業からはじまった。海を渡る北朝鮮の覚醒剤とコロンビアのコカイン、金の延べ棒がうなる香港の隠れ家、イランとの武器取引、ソマリアの傭兵軍団、フィリピンの暗殺者たち、アメリカ政府でも破れない高度な暗号化プログラム―。すべての背後で糸を引く「魔王」の正体は?犯罪ノンフィクションの新時代を告げる一冊。 どんなドキュメンタリーか、についてはたくさんの記事が出ているし、bitcoinとの色々についてはビットコインの開発者「 »