AOJ0516: Maximum Sum(累積和, しゃくとり法)
Maximum Sum | Aizu Online Judge
累積和としゃくとり法を知らなかったのでメモ。計算量を考えずに全探索までしていたので書いておく。 最悪 O(n2) で最大 n = 100000 だから全探索はダメ(指数記号が出せない…)。
続きを読むAOJ0030: Sum of Integers
Sum of Integers | Aizu Online Judge
深さ優先探索の問題。C++ で書いたものを Python に翻訳して分かった気になるアレ。
#!/usr/bin/env python def dfs(pos, t, sum): global cnt if t == n: if sum == s: cnt += 1 return if pos > 9: return dfs(pos+1, t, sum) dfs(pos+1, t+1, sum + pos) while True: n, s = map(int, raw_input().split()) if n==0 and s==0: break cnt = 0 dfs(0, 0, 0) print cnt
蟻本の DFS の説明の理解に時間がかかったし、遷移の仕方が直感的にわからないから演習を詰むしかなさそう。
DP でも解けるらしいけどもっとわからん。
アイカツ!が遊べるお店の全国地図をGoogleMapで公開した
追記(2016/06/02)
この記事は古いです。2016/06 現在、以下の地図は「スターズ!」には非対応となっています。スクリプトも動きません。
ここで、別の見やすいマップを見つけたので勝手にリンクしておきます。
(追記終了)
追記(2017/01/22)
地図とスクリプトを更新しました。スターズに対応しています。
(追記終了)
作ったもの
アイカツ公式のあそべるお店ページでは個々の店舗の情報しか分からないため、GoogleMap に店舗情報をプロットしたものを公開した。GoogleMap に適用させるために、店名と住所を取得して CSV に出力するスクリプトを Python で書いたので、Github に置いておく。以下ソース。
続きを読むテスト
test