千里の道も一歩から。えぬわいです。 qiita.com 続きです。 atcoder.jp おっしゃあこい。 再帰関数を書いて、観察。 そして、漸化式を導くぜ。 最初に、選んだものを全部リストに詰めて、次の呼び出しに渡すパターン。 これは言わずもがな、DP化できない。 …

自分がやりたいことは、自分が実行しない限り一生達成されることはない。えぬわいです。 qiita.com 続きです。 atcoder.jp 問題のURLです。 DPな日々。ちょっと慣れてきました。 ナップザック問題に、個数の制限がかかったような問題です。 限界重さと、選ぶ…

qiita.com 続き。 atcoder.jp 結論から言ってよくわかんなかった。 確率すごく苦手なので。 こういう日もあるかなぁという感じで流していきます。できなかった問題としてメモしてるので、また考察して行きたいと思ってます。普通に悔しかった。 よくわかんな…

qiita.com 続き。 atcoder.jp 初めのコード n = int(input()) p = [int(i) for i in input().split()] ans = set() v = 0 def rec(i): global v if i == n: ans.add(v) return v += p[i] rec(i+1) v -= p[i] rec(i+1) rec(0) print(len(ans)) 単純に、引数を…

qiita.com 続きです。 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_B&lang=jp 言わずもしれたナップザック問題。 動的計画法を考察してみる。なあなあだったので。今回は、蟻本を参考にしないで、思い出しながら、書いてみた。 N, M = …

qiita.com 続き。 codeforces.com 内定式で、ブログが途切れてしまったけど、やります。 途切れたなら、またやり直せばいいじゃない！！！ 問題概要 最初に N 個の数字とスコア 0 が与えられる。それを要素数が 0 にならないように、 2 分割していって、2 分…

qiita.com 続き。 atcoder.jp 実質リベンジみたいな。何を言っているのかは、わかる。実装はできないみたいな。まぁ、技術力不足なだけなんですけど() 以下、コードの説明。 i := T の 添字 j := i + 1 番目以降で、最も辞書的に小さい文字を探すための添字 …

qiita.com 続きです。 https://atcoder.jp/contests/abc083/tasks/arc088_a 倍々にしていけば取れる x, y = map(int, input().split()) ans = 0 while x <= y: ans += 1 x *= 2 print(ans) あ、やっぱ、mapとname使わんことにした。 https://atcoder.jp/cont…

qiita.com atcoder.jp 辞書順確認。 print('a' if input() != 'a' else -1) 以上。 ABC 009 C 辞書式順序ふたたび なんだけど、実装がくそ重いです。文字列系の問題まっっっっっっっったく全然好きじゃないので、モチベは低いし、理解できないしで進まない。…

qiita.com 続きです。 atcoder.jp 問題概要 '?'と英字小文字で構成される文字列Sと英字小文字のみで構成される文字列Tが与えられる。'?'を任意の文字とした時、SにTが含まれている(合致する)場合の辞書順最小のSを求めよ。かな？ 考えたこと Tには、Sの後ろ…

qiita.com DP問題で、泣いちゃった。 atcoder.jp LIS(Longest Increasing Subseaquence)という問題らしい。 pekempey.hatenablog.com この人のがめちゃめちゃわかりやすいかったです。 以下実装 """ LSI (最長部分増加列問題) """ import bisect def main():…

qiita.com 続き。 codeforces.com こどふぉの問題ですね。 普通にわからんかったので、色々調べました。 問題概要 数直線上に位置 x_i と 重み w_i を持つ点 N が与えられる。この点から、 どの 2 点を選んでも|x_i - x_j| >= w_i + w_jを満たすグラフの最大…

https://qiita.com/drken/items/e77685614f3c6bf86f44 続きです。 区間スケジューリングの問題がメインです。 区間スケジューリングは、個々の区間に、少なくとも 1 つ垂直に棒が刺さっている状態にするには、最小で何本必要ですかという問題らしい。けんち…

qiita.com 続き。 atcoder.jp コインの貪欲法の問題。 def main(): n = 1000 - int(input()) ans = 0 while n > 0: for i in [500, 100, 50, 10, 5, 1]: if n >= i: n -= i ans += 1 break print(ans) if __name__ == '__main__': main() これで通った。 次…

https://qiita.com/drken/items/e77685614f3c6bf86f44 の続き。 https://atcoder.jp/contests/abc054/tasks/abc054_c 問題概要 自己ループ、多重辺がないグラフが与えられる。頂点番号 1 から全ての頂点をたどるパスは何通りあるか？ 考えた解法 dfsで全探索…

qiita.com 続きです。 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0503 問題概要 大きさが小さい順にカップが積まれている皿が 3 つあり、隣の皿に、うつしていって(カップの大きさが小さい→大きいの動かし方はだめ)、最も左か最も右に移す…

qiita.com 続き。 atcoder.jp むずくてワロタ。 問題概要 壁'#', 平地'.', スタート's', ゴール'g' で構成されたH*Wのマス内で、スタートからゴールまで、壁を2回まで壊していいから、平地を通って行けるか。 考えたこと(間違い) s から g までに到達する経…

今日はやらない予定だったんですけど、昨日のが不完全燃焼だったの思い出して悶々としてしまったので。 qiita.com 続きです。 atcoder.jp リンクです。 問題概要 H*Wのマスに白マス'.'と黒マス'#'がある。1ターンで、黒マスを中心とする十字に塗り潰すことが…

qiita.com 続き。 atcoder.jp ねむみ。 from collections import deque def main(): h, w = [int(i) for i in input().split()] f = [] c_of_sharp = 0 for i in range(h): line = list(input()) for c in line: if c == '#': c_of_sharp += 1 f.append(line…

qiita.com の続きです。 atcoder.jp BFSの続き。 迷路には、'X'と'.'と1~9までの数字が埋まっており、スタートからマスを進んで、1~9を順番に取っていき、その時の最小手数を求めてねという問題。 from collections import deque BIG = 1000000 def main(): …

qiita.com DFSとBFSの問題。 愚直な実装でいける。 import sys sys.setrecursionlimit(1000000) def rec(y, x, f): f[y][x] = '0' for dy, dx in [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]: if 0 <= y+dy < len(f) and 0 <= …

qiita.com の続きです。 問題は、与えらたグラフが、木を何個持つか答える問題。 最初に考えたWAのやつ。単方向。 """ 木である場合は、含まれる頂点を 1 度開始しか通らない """ visited = [] tree = [] def rec(i, mark): global visited visited[i] = Tru…

qiita.com qiitaの初級編の問題。 ATC 001 A 深さ優先探索 深さ優先は、そのまんま import sys sys.setrecursionlimit(10000000) f = [] h, w = 0, 0 def rec(y, x): if f[y][x] == 'g': return True f[y][x] = '#' ans = False for dy, dx in [[1, 0], [-1,…

はい、昨日完成できなかった問題。 布団に入ったあと、すぐに浮かんだ解答。 寝ようと思ったあとに、考えたり、思いつくのやめたい。 昨日より、すっきりしたし、簡単だと思った。 bit全探索で、頂点の組み合わせを出す。その後、それらの頂点が、互いに繋が…

けんちょんさんがまとめてくれてるqiitaのAtCoder精選問題集の問題(初級)。 高橋くんとお肉は、そんなに難しくなかった。樹形図的に2のN乗の全探索で、肉を2つの鉄板に振り分けていく問題。こういうパターンもあるのかという気持ちになった。 t = [] n = 0 d…

今日の競プロ。 train ticket は、与えられた4桁の数字の各桁を順番そのままに、引くか足すかして、=7ができるか問う問題。簡単な全探索でeval使って瞬殺。 def main(): abcd = list(input()) flag = False for op1 in ['+', '-']: for op2 in ['+', '-']: f…

出れなかったんだけど、AtCoderの解説動画が結構参考になったので、pythonで書く 数え上げ系すごく苦手なので、戒め兼補足。解説動画が少しわかりにくかったので。 問題概略。 ON/OFFスイッチが N 個と電球が M 個ある。それぞれのスイッチは複数の電球とラ…

i 番目の要素だけを除いた全体のGCDを求めるという愚直な案を書いて当然TLEだったので供養。 def gcd(x, y): xx = 0; yy = 0 if x >= y: xx = x; yy = y else: xx = y; yy = x while yy > 0: xx, yy = yy, xx%yy return xx def main(): n = int(input()) a =…

区間DPらしい。 蟻本の練習問題。 基本的なDPって書いてあったのに、できなかったけど() 普通に文字列周りの問題が壊滅的にできないと思った。全然できんし。 これがわかってたらという事柄をあげる 全探索の方向 最小条件のクリア eagletmt.github.io 解答…

蟻本の練習問題として載ってるPOJの問題3176。 簡単なDPの解答。 大雑把にO(n2)で収まるぐらいの計算量で解いた。以下、解答 #include <cstdio> #include <algorithm> using namespace std; #define MAX_A 500 int n, a[MAX_A][MAX_A], dp[MAX_A+1][MAX_A+1]; int solve(int n) </algorithm></cstdio>…