問題 動的計画法を使う。 dpn配列に文字列の長さ、dp配列に文字列を格納する。配列の長さはマッチ棒の個数。 dpnを0から順番に調べ、初期値(-1)ではなく、追加したマッチ棒の個数の地点の長さが ①追加したい個所と同じ ・追加したい個所に、追加したい個所と…

問題 最大公約数を求めればよい。 ただし、AtCoderのpython3の実行環境は3.4.3のため、math.gcdが使えない。 そのため、fractions.gcdを使う。 from fractions import gcd n = int(input()) A = list(map(int, input().split())) ans = A[0] for a in A[1:]:…

問題 1人の場合は、その人が答えた食べ物の種類数が答え。 2人以上の場合は、1人目からN人目までの好きな食べ物の&をとればよい。 n, m = map(int, input().split()) ans = set(input().split()[1:]) for _ in range(n - 1): ans &= set(input().split()[1:])…

問題 bをaで割り切れたら、a + b を出力。 そうでなければ、b - a を出力 a, b = map(int, input().split()) print(a + b if b % a == 0 else b - a)

問題 分かりやすいように、AとBを設定。 A：裏切り者でないのに裏切り者だと判定 B：裏切り者に対し、裏切り者と判定 とすると、計算式は以下のようになる。 P, Q = map(float, input().split()) print(P * Q * 100 / (P * Q + (100 - P) * (100 - Q)))

問題 フィボナッチ数列 n = int(input()) ans = [1, 1] + [0] * 100 for i in range(2, n + 1): ans[i] = ans[i - 2] + ans[i - 1] print(ans[n])

問題 分かりやすいように変数を定義 R：赤が表示できる文字数 G：緑が表示できる文字数 B：青が表示できる文字数 上記より、カラーコードのイメージは #RRGGBB のようになるので、 「R * R * G * G * B * B」 を出力すればいい。 ans = 1 for s in (input() …

問題 3桁ごとに「,（カンマ）」をつけるだけ print(f"{int(input()):,}")

問題 解けなかった。 解答PDFを参考にすると、 となるので、配列をDPで更新していけば解けることが分かる。 import sys readline = sys.stdin.readline L = int(input()) dp = [0] * 5 for a in map(int, (readline() for _ in range(L))): back = a % 2 if …

問題 選べるパターンは２つ ①ビスケットを1枚増やす ②ビスケットA枚をB枚に交換する（２回分の操作） ②の場合は、得られるのは次の３パターン B - A < 2 この場合は①よりも少なくなるので①を選択 B - A == 2 この場合は①と同じになるので①を選択 B - A > 2 …

問題 一筆書きとして考えた。 すべての道を１回ずつ通ってすべての街を訪れることができるのは、N字型かコの字型の２パターンのみ（回転や反転したものは同一と考える）。 同じ道を２回以上通った場合は同じ町を３回訪れることになるので、その場合はNO。 そ…

問題 仮にk個選べるとすると、必要なnの数は(k * 2 - 1)個。 nがそれ以上ならばYES。 そうでなければNO。 n, k = map(int, input().split()) print("YES" if k * 2 - 1 <= n else "NO")

問題 解けなかった。 ヒープを使うのかと思い考えてみたが、解法が思いつかなかった。 解答PDFと動画を見て解き方を理解した。 まず、AよりもBが大きい場合は答えが存在しないため、-1を出力。 次に、配列A-Bの要素のパターンは３つ。 ①マイナス(minus) : A …

問題 YESのパターンは、余計な文字がkeyenceの後ろ、中、前の３つ。 ①keyence・・・ ②key・・・ence ③・・・keyence それを考慮すればいい。 pythonコード

問題 自分はsetを使ったが、sortでも解ける。 変数4つが、[1, 7, 9, 4] なら"YES"、そうでないならば、"NO"を出力する。 pythonコード

dp_h 動的計画法 壁以外のある地点(i, j)にいるとする。 そこにたどり着く経路の数は、(i - 1, j) + (i, j - 1) の合計をmodで割った余り。 迷路の周りを'#'で囲むとシンプルに解くことができる。 pythonコード

dp_f 蟻本の最長共通部分列問題の類題？ 最後に共通部分文字列を出力する必要があり、それに手間取った。 共通文字が存在するときはその要素の右下が1大きくなるので、逆に辿れば共通部分文字列の反転を得られる。それを反転して出力すればいい。 計算量がO(…

dp_e 動的計画法 蟻本p60の01ナップサック問題その他2の類題？ O(nW)では 1011 となり、配列が長すぎてしまうため、工夫。 重さではなく、価値の配列にすれば、O(nv)で 107となり、計算可能になる。 pythonでは間に合わなかったため、c++で提出した。 一応、…

dp_d 動的計画法 通常のナップサック問題。 重さが 105 なので、O(NW)では 107。 pythonでは間に合わなかったため、c++で提出した。 一応、pythonコード c++コード

dp_c 動的計画法 現時点をiとし、aについて考える。 現在のa[i]を最大にするには、 a[i]に１つ前のa以外(b、またはcのうち大きいほう)を合計すればいい。 b,cについても同様。 そして、最終的に最大なものを出力。

dp_b 動的計画法 前問のAの範囲が２つ前までだったのに対し、今回はKつ前までとなる。 問題自体は難しくないが、普通に解くと計算量がO(nk)となり、pythonでは間に合わない(numpy使って工夫しないかぎり)。 一応、pythonコード c++コード

dp_a 動的計画法 現在位置をiとすると、以下の①②のうち、小さいほうをdp[i]とする。 ①abs(h[i] - h[i - 1]) + dp[i - 1] ②abs(h[i] - h[i - 2]) + dp[i - 2] ※dp[1]の場合、2つ前はないので注意