Human Resource Machine
ここ最近「Human Resource Machine」というスマホゲーをやっていて、ついこの間クリアしました。プログラミングの要素をうまいことゲームに落とし込んでいて、おもしろかったです。後半はソートとか出てきて割とガチでプログラミング組まなきゃいけなくて、プログラミング経験がないとちょっと難しいかもしれません。（短手数クリアはプログラマでも難しい...！)
またストーリーもあります。主人公は新入社員として入社して、１問クリアすることに１年経過する設定になってるんですが、全部で40問近くあるので最後のほうにはビジュアルも変わっておじさん(or おばさん)になります。だんだん頭が薄くなっていったりして、それが非常に哀愁を誘います…。
約40年、一途にお仕事をつづけた結果、主人公がどうなるのか…気になる方はやってみてください。
Tenka1 Programmer Beginner Contest
tenka1-2019-beginner.contest.atcoder.jp
2完。40分遅れで始めたとはいえCが解けなかったのが悔しい。。左が白、右が黒の並びになればいいところまではわかったけど、ロジックに穴がありWA食らいました。もうちょいサンプル欲しかったなぁという負け惜しみ。
Cは左側が白、右側が黒というように分かれればよくて、[0, i)までを白領域、[i, N)までを黒領域(i == 0なら全部黒、i == Nなら全部白)とすると、「白領域の黒の数と黒領域の白の数の和」がひっくり返せばいい数になるので、あとはiを[0, N]まで動かして最小値を探索すればok。前回使った累積和が出てきたけど見事に活用できなかったな。
N = int(input()) S = input() cum_sum_b = [0] cum_sum_w = [0] sum_b = 0 sum_w = 0 for i, s in enumerate(S): if s == '#': sum_b += 1 else: sum_w += 1 cum_sum_b.append(sum_b) cum_sum_w.append(sum_w) ans = N for i in range(0, N + 1): count = cum_sum_b[i] + cum_sum_w[N] - cum_sum_w[i] ans = min(ans, count) print(ans)
Pythonで、多分こんな雰囲気。
Dは解説聞かないと正直解ける気しなかったです。
解き方は解説動画に任せて式の立て方としては、
i = 0...N, j = 0...{a0...aNの総和s}として、
R == j で残りはGorBで塗る組み合わせの数(dp0)と、R == jで残りはGで塗る組み合わせの数(dp1)をそれぞれDPで出し、
dp0からR>=sの時の組み合わせの数、dp1からR==G==s/2の時の組み合わせの数がわかるので、そこから答えを求める
という感じのよう。
import math N = int(input()) a = [int(input()) for _ in range(N)] s = sum(a) # Calculate counts of (R >= s / 2) dp = [[0 for _ in range(s + 1)] for _ in range(N + 1)] for i in range(N + 1): for j in range(s + 1): if i == 0: dp[i][j] = 1 if j == 0 else 0 else: dp[i][j] = dp[i - 1][j] * 2 + (dp[i - 1][j - a[i - 1]] if j >= a[i - 1] else 0) c0 = sum(dp[N][math.ceil(s / 2):]) # Calculate counts of (R == s / 2 and G == s / 2) dp = [[0 for _ in range(s // 2 + 1)] for _ in range(N + 1)] for i in range(N + 1): for j in range(s // 2 + 1): if i == 0: dp[i][j] = 1 if j == 0 else 0 else: dp[i][j] = dp[i - 1][j] + (dp[i - 1][j - a[i - 1]] if j >= a[i - 1] else 0) c1 = dp[N][s // 2] if s % 2 == 0 else 0 ans = (3 ** N - 3 * c0 + 3 * c1) % 998244353 print(ans)
ただこれだとTLEするPythonには辛い仕様で、通すにはnumpy芸が必要なよう。
import math import numpy as np N = int(input()) a = np.array([int(input()) for _ in range(N)]) s = np.sum(a) dp0 = np.zeros((N + 1, s + 1), dtype=np.int64) dp0[0, 0] = 1 dp1 = np.zeros((N + 1, s // 2 + 1), dtype=np.int64) dp1[0, 0] = 1 mod = 998244353 for i, x in enumerate(a): dp0[i + 1, :] += dp0[i, :] * 2 % mod dp0[i + 1, x:] += dp0[i, :-x] % mod dp1[i + 1, :] += dp1[i, :] % mod dp1[i + 1, x:] += dp1[i, :-x] % mod # Counts of (R >= s / 2) c0 = int(np.sum(dp0[N][math.ceil(s / 2):])) # Counts of (R == s / 2 and G == s / 2) c1 = int(dp1[N][s // 2]) if s % 2 == 0 else 0 ans = (3 ** N - 3 * c0 + 3 * c1) % mod print(ans)
こんな感じにすればいけそう。マイナスのインデックスが慣れないですが、リストの長さ-xと同じですね。
numpyも慣れないといけないけど、なかなかむずい。。
ABC124
3完。Dのテストケースで1個だけWA出て死亡。。変に分岐複雑にしちゃったからどこかミスってるんだろうけど結局どこかわからなかったです。ウボァ
ある数列があって、その[l, r)の区間の和を求めたい場合は累積和(Cumulative sum)を使う。
nums = [1, 2, 3, 4, 5] # 適当な数列 cum_sums = [0] for i in range(len(nums)): cum_sums.append(cum_sums[i] + nums[i]) l = 1 r = 4 ans = cum_sums[r] - cum_sums[l] print(ans) # => 9 (2 + 3 + 4)
Pythonだとこんな雰囲気。
HELLO, DESIGN
前の記事で企画書を10分で書けという内容の本を読みましたが、もう少し具体的に商品を作る上での設計のノウハウみたいなのを知りたいと思い、「HELLO, DESIGN」という本を読んでみました。帯に「デザインはみんなのものだ」と書かれてますが、この本も前回の本と同様、特別な能力がなくてもできるんだというスタンスで書かれてそうなのが気に入って選びました。
ＨＥＬＬＯ，ＤＥＳＩＧＮ 日本人とデザイン (NewsPicks Book)
- 作者: 石川俊祐
- 出版社/メーカー: 幻冬舎
- 発売日: 2019/03/05
- メディア: Kindle版
- この商品を含むブログを見る
前回の「企画」の定義と同様、この本も「デザイン」を「課題の解決のために行うこと」のように定義しており、自分の認識が補われるような感じで素直に読み進めることができました。前の本に比べると、より会社やチームで動くときのノウハウや必要なマインドが説明されていて、これはこれでためになりました。
これまで企画やデザインって自分の中で正解がわからないし、ロジカルに組み立てられる基準とかがなくて、確信がないからあまり意見も出しづらいというのがあったんですが、そのあたりが少し晴れた気がします。本はなんでもいいと思うんですが、エンジニアもこのあたり、かじっておいて損はなさそうだと思いました。
