No Caffeine, No Life

プログラミング(主にPython)

ABC 052 D Walk and Teleport: パズル

そんなに難しく考えなくていい。 2地点間で、歩くほうがいいのかテレポートしたほうがいいのか判断し、足しあげればよい。

ABC 052 C Factors of Factorial: 素数

まず素数のリストを作る(isPrime) その後、各素数について何回割れるかを記録していく (dic) 最後は、約数の数を求める公式にしたがって掛け算すればよい。

ABC 053 D : Card Eater: パズル

これはとても面白い問題だと思った。 与えられた数列の中で、異なる整数の列をできるだけ多く残すにはどうしたらよいか。結局、だぶっている枚数が奇数か偶数か場合わけすればよい。

ABC 053 C X: Yet Another Die Game: パズル

5か6が出ることが最適なので、与えられた数に対し11で何回割り切れるか、足りない部分5か6いずれかで補えるかを考えればよい。

ABC 054 B Template Matching: 盤面の表現

素直に二次元の盤面を表現する。(二次元は1次元に落とし込む):

ABC 054 B Template Matching: any 関数の使い方

any 関数の意味はコチラ:http://blog1.erp2py.com/2011/12/python-any-all.html これを用いた解答例がこちら:

数学パズル Q34 飛車と角の利き:再帰・配列による盤面の表現

テキスト通りに考える。 盤面は9x9のマス目なので、両端を含めて11x11で用意。 境界を1 (使用済み)、移動できる箇所を0(未使用)で記述。 飛車か角を置いた時も使用済みと考える。 移動したマス目は、1次元の配列に収める。(10* x + yとおくことで、2桁の数…

数学パズル Q36 「0」と「7」の回文数:2進数

テキスト通りのロジックで書いた場合:

数学パズル Q31 最短経路の計算: 再帰

通常の再帰による解答例:

数学パズル Q35 運命の出会いは何通り?:再帰(経路の探索)

ヒント通りに普通の再帰を用いた場合:

数学パズル Q09 つりあわない男女:経路の問題

順番にやってくる男女を2つのグループに分けた時に、男女同数のグループができないような順番が何通りあるか、という問題。 男女の順番を2次元配列上の経路の問題として解く。

数学パズル Q20 受難のファサードの魔法陣: 動的計画法

ふつうに解くだけなら全探索: 動的計画法を用いた解答例: gistcc44687dc2bc88299b0819f5d8ea8450

数学パズル Q19 友達の友達は友達?:合成数の考え方

この問題はとても面白いと思う。ヒント通りに、7個の数値が互いの素の素数でどのように書けるかを考え、あとはどういう組み合わせが最小かしらみつぶしに探せばよい。

数学パズル Q18 ショートケーキの日: 再帰

再帰を用いた解答例:

数学パズル Q22 絡まない糸電話: 動的計画法

動的計画法を用いた解答例:

数学パズル Q23 ブラックジャックで大儲け!?: メモ化再帰(深さ優先探索)

通常の再帰(深さ優先探索)での解答例: メモ化して高速化した例:

数学パズル Q08 優秀な掃除ロボット: 再帰(深さ優先探索)

通常の再帰(深さ優先探索)の解答例:

数学パズル Q68 隣り合わないのがマナー?: メモ化再帰

通常の再帰を使った解答例: 高速化するために、メモ化再帰を用いた解答例: テキストにあるとおり、条件を配列に落とし込む際に「番兵」という考え方を遣っている(WALLというところ)。番兵については、下記を参考: http://blog.codebook-10000.com/entry…

数学パズル Q24 完璧に打ち抜くストラックアウト: メモ化再帰とビット演算

いわゆる「2抜き」を許した場合のストラックアウト。 テキストにあるような、配列を用いて打ち抜く場合を列挙したやり方だと(しょうもないことに)Pythonでうまく書けなかったので、ここでは、打ち抜く場合のそれぞれをビット列で表現しています。(例:0b…

数学パズル Q38 7セグメントコードの反転:ビット演算

まず全探索をする解答例: これだと10!分の探索をしていることもありかなり時間がかかる(自分の手元では40秒ほど)。 10!の探索には変わりないが、0-9のセグメントの変化をあらかじめテーブルに保存しておき、利用することを考える。この場合、文字列を扱…

数学パズル Q41 美しい?IPアドレス: ビット表現で遊ぶ

2進数で対称になる数、を考えると16ビットの数を反転し、追加して32ビットの数を得ることを考える。これを10進数に変換したときに、0-9の数を1個ずつ使っていればよい。 その場合の解答例: 実際には16ビットではなくて8ビットで十分。その場合は…

数学パズル Q21 排他的論理和で作る三角形: ビット演算の練習

ビット演算になれるための練習。 各行を配列で表現した場合の解答例: 各行は、 k行目を1ビット左にシフトしたものをk+1行目とする k行目とk+1行目をXORしたものが正しいk+1行目となる ことに注目する。例を挙げると、 6段目:110011 これを1ビット左にシ…

数学パズル Q54 同じ数字で挟み撃ち: メモ化再帰(とビット演算)

普通の再帰(深さ優先探索)での解答例(小さい数から順に): 次に、比較のために、大きい数から順に再帰(深さ優先探索)で解く場合の解答例: 最後に、より高速にすべくビット演算を用いた場合の解答例: ビット演算については、下記が参考になる: https…

数学パズル Q53 いたずらされたお菓子: メモ化再帰

メモ化再帰による解答例:

数学パズル Q15 階段で立ち話: 動的計画法とメモ化再帰

プログラマ脳を鍛える数学パズル シンプルで高速なコードが書けるようになる70問 作者: 増井敏克 出版社/メーカー: 翔泳社 発売日: 2015/10/16 メディア: Kindle版 この商品を含むブログ (6件) を見る この本にある問題をPythonで解いてみます。 ただの再帰…

ABC008D問題 金塊ゲーム:メモ化再帰

問題はこちら: D: 金塊ゲーム - AtCoder Beginner Contest 008 | AtCoder メモ化再帰での解答例はこちら:

Aizu Online Judge: 動的計画法もしくはメモ化再帰

問題はこちら: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_B&lang=jp 動的計画法の解説はこちら: 動的計画法(ナップサック問題) – アルゴリズム講習会 動的計画法での解答: メモ化再帰での解答:

Aizu Online Judge: 総当たり

総当たり: 総当たり、全探索、ブルートフォース…個人的にはこういう類のものこそ最もコンピュータに向いている問題だと思うし、マシンの性能を試す意味でも大事なカテゴリーの問題だと思う。けれども、コンピュータのリソースは無尽蔵にあるわけではないの…

Aizu Online Judge: 割り当て (探索の応用:最適解の計算)

探索の応用:最適解の計算 気づかないといけないことは、 各トラックは、与えられた荷物をその順番通りにしか積めない 求める最大貨物量の最小値は、与えられた荷物リストのなかの最大値以上、その総和以下になる 次にすることは、 求める最小値は、区間(荷…

Aizu Online Judge: 辞書

辞書: リストよりも集合を使うと速いという話(?)

Aizu Online Judge: 二分探索(バイナリーサーチ)

二分探索: 二分探索(バイナリーサーチ)のアルゴリズムはしごく直観的でわかりやすい。しかし、この問題についてだけいえば、単に集合の積集合を取るだけで答えが出てしまう。 bisectというライブラリもあるのだけれど、とりあえず今回は省略。

Aizu Online Judge: 面積計算

模式断面図の面積 | アルゴリズムとデータ構造 | Aizu Online Judge この問題はやや難しい、と『 プログラミングコンテスト攻略のためのアルゴリズムとデータ構造 』に書いてある。確かに、ちょっと考えにくい、というか、キューやスタックがよくわかってい…

Aizu Online Judge: 双方向連結リスト(dequeの使い方)

双方向連結リスト: 以下の命令を受けつける双方向連結リストを実装してください。 - insert x: 連結リストの先頭にキー x を持つ要素を継ぎ足す - delete x: キー x を持つ最初の要素を連結リストから削除する - deleteFirst: リストの先頭の要素を削除する…

Aizu Online Judge: キュー

キュー: 名前 namei と必要な処理時間 timei を持つ n 個のプロセスが順番に一列に並んでいます。ラウンドロビンスケジューリングと呼ばれる処理方法では、CPU がプロセスを順番に処理します。各プロセスは最大 q ms(これをクオンタムと呼びます)だけ処理…

Aizu Online Judge: スタック(逆ポーランド記法)

スタック(逆ポーランド記法): 逆ポーランド記法は、演算子をオペランドの後に記述する数式やプログラムを記述する記法です。例えば、一般的な中間記法で記述された数式 (1+2)*(5+4) は、逆ポーランド記法では 1 2 + 5 4 + * と記述されます。逆ポーランド…

Aizu Online Judge: バブルソートと選択ソート

バブルソート: バブルソートはその名前が表すように、泡(Bubble)が水面に上がっていくように配列の要素が動いていきます。数列 A を読み込み、バブルソートで昇順に並び変え出力するプログラムを作成してください。また、バブルソートで行われた要素の交換…

Python3: Atcoder Beginner Contest 13

参照:http://abc013.contest.atcoder.jp/ A 高橋君はとても英語が苦手で、アルファベットもまだ覚えきれていません。そこで、高橋君のために、入力として与えられたアルファベットが A から数えて何番目のアルファベットかを求めるプログラムを作成してくだ…

Python3: 素数まわりの話

素数の判定法:

Python3: リストの使い方(文字列編)

1つのアルファベットが描かれた n 枚のカードの山をシャッフルします。1回のシャッフルでは、下から h 枚のカードをまとめて取り出し、それを残ったカードの山の上に積み上げます。カードの山は以下のように1つの文字列で与えられます。abcdeefab最初の文字…

Python3: if文の書き方

たとえばこんな問題: 2つの整数 a, b を読み込んで、a と b の大小関係を出力するプログラムを作成して下さい。入力は空白で区切られた2つの整数 a, b から構成されています。a より b の方が大きければa < ba より b の方が小さければ、a > ba と b が等…

Python3: 出力の仕方

空白区切りで複数の数値の出力 コンマ区切りで複数の数値の出力 たとえば、こんな問題: 秒単位の時間 SS が与えられるので、hh:mm:ss の形式へ変換して出力してください。ここで、hh は時間、mm は 60 未満の分、ss は 60 未満の秒とします。hh、mm、ss を …

Python3: 標準入力の受け取り方

1行に1つの文字列場合 1行に1つの数値(整数もしくは浮動小数点数)の場合 1行に複数の数値(整数もしくは浮動小数点数)の場合 複数行の入力

Pythonで回文

Code IQ からの問題: 2進数や16進数はよく使うエンジニア。でも、n進数と言われたら… ここでは指定された値を基数とするように変換してみます。 複数の基数が指定されたとき、そのいずれでも回文数となるような数を求めます。 ※回文数とは左から読んでも右…

Pythonで始めるプログラミング入門

Pythonで始めるプログラミング入門 作者: 大和田勇人,金盛克俊 出版社/メーカー: コロナ社 発売日: 2015/09 メディア: 単行本 この商品を含むブログを見る Pythonの入門書はいろいろあるし、ネットだけでも十分な解説が(入門者向けには)されていると思う。…

CodeIQ: 「7」の数を数えよう

CodeIQで次のような問題が出題されていた: 1からnまで連続する正の整数があります。 それらの中に、「7」がいくつあるかを数えてください。 【例】 n = 99とすると、 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31…

test (Project Euler Problem 13)

// // Test (Sample python code for Project Euler Problem13) gist.github.com