D言語: recurrence の練習

import std.experimental.all; void main() { // 初項 1, 公差 2 auto a = recurrence!((a, n) => a[n-1] + 2)(1); writeln(a.take(10)); //=> [1, 3, 5, 7, 9, 11, 13, 15, 17, 19] // 初項 3, 公比 2 auto b = recurrence!((a, n) => a[n-1] * 2)(3); writ…

D言語: foreach の変数展開の仕組みが分からない

import std.experimental.all; void main() { foreach (a; [10, 20, 30]) writeln(a); } と書くと、配列の中身が foreach の変数 a に代入されて以下のように出力されます。 10 20 30 次に foreach の変数をひとつ追加します。 すると、その追加した変数には…

D言語: 2, 3, 5, 7... のシーケンスを作る

D 言語で、2, 3, 5, 7... のシーケンスを作る方法です。 素数をふるいにかけるとき 2 で割り切れるか 3, 5, 7... で割り切れるか を試しますが、これらを分離せずにひとつのシーケンスとして扱えると便利ですね。 import std.experimental.all; void main() …

隣り合う要素でグループ分け

0 と 1 からなる配列があります。 たとえば [0, 1, 1, 0, 0, 1, 0, 0] の配列を [[0], [1, 1], [0, 0], [1], [0, 0]] のように 0 と 1 とでグループ分けする関数が必要になったので作ってみました。 def group(xs) return [] if xs.empty? g = [] buf = [xs[…

Ruby で三角数の無限シーケンスを作る

まずは Enumerator で三角数を具体的に生成してみよう。 def triangles Enumerator.new do |y| sum = 0 1.step {|i| sum += i y << sum } end end p triangles.take(10) #=> [1, 3, 6, 10, 15, 21, 28, 36, 45, 55] 三角数を生成するところをもっと抽象化し…

SageMath でフィボナッチ数の練習

sage: def fib(n): ....: if n == 0: return 0 ....: m = matrix([[1, 1], [1, 0]]) ** n ....: return m[0, 1] ....: sage: [fib(i) for i in range(20)] [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181] 参考 行列…

Python で多次元リストを作る

Python で 2 次元リストを作るには、リスト内包表記を使って以下のように書くことが出来ます。 >>> rows, cols = 2, 3 >>> [[0] * cols for _ in range(rows)] [[0, 0, 0], [0, 0, 0]] 2 次元まではいいのですが、3 次元以上になるとリスト内包表記で書くの…

curry, uncurry

Prelude> :t curry curry :: ((a, b) -> c) -> a -> b -> c Prelude> :t uncurry uncurry :: (a -> b -> c) -> (a, b) -> c Prelude> add (a, b) = a + b Prelude> curry add 2 3 5 Prelude> mul a b = a * b Prelude> uncurry mul (2, 3) 6 curry はタプル…

AtCoder など競プロで学んだこと

これはCompetitive Programming Advent Calendar 2017の 17 日目の記事です。 AtCoder のレートは緑です。最近ようやく水色に届きました。そんな筆者ですが、AtCoder など競プロで学んだ内容をいくつか紹介したいと思います。 long に収まらない整数の余りを…

「カウント・スリー」問題を解いてみました

桁 DP + 二分探索で解きました。 リンク togetter.com

VSCode で Markdown のみ行末の空白を削除しない

settings.json で以下のように設定します。 すると、Markdown のみ行末の空白が削除されなくなります。 "files.trimTrailingWhitespace": true, "[markdown]": { "files.trimTrailingWhitespace": false } 参考 https://github.com/editorconfig/editorconfi…

再帰に対する考え方を教えてくれた練習問題

確か『LISP I』だったと思うけど、次のような練習問題があった。 2 つの引数をとり、その 2 つの値の合計を返す関数を書け。ただし + は使わずに 1+ と 1- を使って。 なお、2 つの引数は正の整数と仮定してよい。 答えをみたら「なあんだ」と思えるが、その…

数値文字参照を文字に変換するPythonスクリプト

import re def conv(s): cs = [] for e in re.findall("&#x([0-9a-fA-F]+);", s): cs.append(chr(int(e, 16))) return "".join(cs) def main(): s = "&#x30D5;&#x30A1;&#x30A4;&#x30EB;&#x307E;&#x305F;&#x306F;&#x30A2;&#x30BB;&#x30F3;&#x30D6;&#x30EA;" p…

自然数から平方数を取り除いた数列の N 番目を求める

A000037 - OEIS の式を使って求めます。 ; https://oeis.org/A000037 (define (f n) (+ n (exact-integer-sqrt (+ n (exact-integer-sqrt n))))) 実行結果です。 % gosh -l ./not-square-numbers.scm gosh> (map f (iota 100 1)) (2 3 5 6 7 8 10 11 12 13 1…

バットとボールの問題を SageMath で解く

問題:バットとボールはセットで1ドル10セントします。バットはボールより1ドル高いです。ボールはいくらですか? http://karapaia.com/archives/52047106.html $ sage ┌────────────────────────────────────────────────────────────────────┐ │ SageMath …

1158と四則演算で10を作る問題

1, 1, 5, 8 と四則演算で10を作る問題をやってみました。

Gaucheで小町算にチャレンジ

Makoto HiroiさんのMemorandum(2013年1月5日)で小町算の問題が紹介されていました。 M.Hiroi's Home Page / Memorandum ●パズルでプログラミング パズルの世界では、1 から 9 までの数字を 1 個ずつすべて使った数字を「小町数」といいます。 たとえば、1234…

RubyのBinDataが便利!

RubyのBinDataが便利!バイナリ構造が宣言的に書ける。Javaクラスファイルのconstant_poolを解析してppしただけのプログラムだが2-30分でできてしまった。これにはほとんど感動してしまった。gist.github.com/3408774#binsummer— Shiina san!さん (@shinaisa…

深さ優先探索によるトポロジカルソート

Lua

トポロジカルソートのアルゴリズムは、『プログラマのうちあけ話―続・プログラム設計の着想』を読んで学びました。この本では次の方法により、トポロジカルソートします。 入力辺がないノードをキュー q に入れる while (q に要素が含まれる): node = q.pop(…

池袋バイナリ勉強会(9)に参加しました

12月2日(日)に開催された池袋バイナリ勉強会(9)に参加しました。PDP-11のバイナリ解析に取り組んでいます。a.outの逆アセンブル、およびインタプリタの作成に取り組んでいます。 目標: hello.c を実行するインタプリタの作成 % cat hello.c main() { write(1…

SRM563 div2 easy FoxAndHandleEasy

SRM

文字列Sがあり、その文字列Sの任意の位置に同じ文字列Sを挿入する。そうして作られる文字列をSのexpansionと呼ぶとする。文字列S, Tが与えられたとき、TがSのexpansionかどうかを求める問題。 コンテスト中に書いたコードは以下。std::stringの文字列の削除…

池袋バイナリ勉強会(8)に参加しました

11月25日(日)に開催された池袋バイナリ勉強会(8)に参加しました。PDP-11のバイナリ解析に取り組んでいます。a.outを逆アセンブルする自作スクリプトを作成しながら、平行してそれを実行するインタプリタを作ろうとしている段階です。 逆アセンブラの作成 以…

池袋バイナリ勉強会(5)に参加しました

10月21日(日)に開催された池袋バイナリ勉強会(5)に参加しました。PDP-11の実行ファイル(a.out形式)の解析に取り組んでいます。 以下、取り組んだ内容のメモです(書かれている内容には間違いがあるかも知れません)。 前回までの復習 前回までの勉強会で学んだ…

池袋バイナリ勉強会(2)に参加してきました

9月23日(日)に池袋バイナリ勉強会(2)に参加してきました。 MonoDevelopでHello world! MonoDevelopとGTK#を用いて、ボタンをクリックしたらメッセージダイアログを表示するGUIプログラムを書きました。 MonoDevelopをインストールします。MonoDevelopからダ…

Codeforces 110B - B. Lucky String

110B - B. Lucky String calc :: Int -> String calc n = take n $ cycle "abcd" main = do s <- getLine putStrLn $ calc $ read s

Processing, プロジェクト名と同じ名前のクラスは定義できない。

プロジェクト名(.pdeファイル名)と同じ名前のクラスを定義しようとすると、以下のエラーメッセージが表示されました。 The nested type Test cannot hide an enclosing type

Processingで正三角形を描画する

Processingで正三角形を描画しようと思い、コードを書き始めたけど、すぐに手が止まってしまった。triangle()を使って、3点の座標位置を指定すれば三角形を描画できる。だけど、3点の座標位置はどう決めたら良いのだろうか?そもそも正三角形とはどういう形…

primesパッケージをインストール

primesパッケージをインストールします。 cabal install primes http://hackage.haskell.org/package/primes Prelude Data.Numbers.Primes> take 30 primes [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113] …

Codeforces 37A - A. Towers

37A - A. Towers import Data.List calc :: [Int] -> (Int, Int) calc xs = (maximum [count x xs | x <- xs], length $ nub xs) where count a xs = sum [1 | x <- xs, x == a] main = do s <- getLine t <- getLine let (x, y) = calc $ map read $ words …

Codeforces 122B - B. Lucky Substring

122B - B. Lucky Substring calc :: String -> Int calc s | n4+n7 == 0 = -1 | otherwise = if n4 >= n7 then 4 else 7 where n4 = sum [1 | c <- s, c == '4'] n7 = sum [1 | c <- s, c == '7'] main = do s <- getLine print $ calc s