内容 CFのRound #590 Div3のD問題、Distinct Characters Queriesをpythonで解きました。 問題 文字列S(アルファベット小文字)とQ個のクエリが与えられる。 クエリは二種類あって、 (1 x y) -> 文字列のx番目の文字を、yに書き換える。 (2 l r) -> 文字列の[l…

内容 ABC137 E問題Coins Respawnをpythonで解きました。 問題 atcoder.jp 考えたこと 問題見た感じ、辺のコストを(-cost+P)にして、負の辺がある最短経路問題じゃんと思った。 負の重みの辺があるので、ダイクストラは使えなくて、 ベルマンフォード を使う…

内容 Educational Codeforces Round 69 A "DIY Wodden Ladder"を解きました。 python3 問題 本文 K段のはしごを作りたい。 K段のはしごは、 長さK+1以上の棒２本(はしごのbase) 長さ１以上の棒 k本(はしごのstep) で構成される baseの2本は違う長さで良いし…

内容 Educational Codeforces Round 69 DIv2 B "Pillars" を解きました。 python3 問題 本文 N本の柱がある。(1~N)これらは、横一列に並んでいる。 それぞれの柱には、半径 r_iの円盤が乗っている。 円盤は隣の柱に移動することができる。 円盤の移動には、…

内容 ABC 134 C(300点) "Exception Handling"を解きました。 問題 https://atcoder.jp/contests/abc134/tasks/abc134_c 考えたこと 自分より左の区間のmaxと、自分より右の区間のmaxを比べて大きい方を出せばいい。 ポイント 左から見ていく場合の最大値と、…

内容 ABC 134 D(400点) "Preparing Boxes"を解きました。 pypyで提出(pythonだとTLEしてしまったため) 問題 https://atcoder.jp/contests/abc134/tasks/abc134_d 考えたこと iの箱に入れると、iの約数の箱に影響が出る。 玉を入れると、自分より大きい数の箱…

Intro Educational Codeforces Round67(Div2)のAをpython で解きました。 codeforces.com A: Stickers and Toys 問題文 おもちゃ屋でチョコエッグが売ってて、中にはおもちゃが入っている。 チョコエッグの中身は３種類ある。 sticker のみが一つ入っている …

Abst ARC089のB問題 (500点) Checkerをpythonで解きました。 pypyで提出しました。 問題 queryとして、2Dのgridで、点の座標と色(黒orしろ)が与えられる gridを幅Kの正方形で白黒のチェック模様に塗る queryの座標と色の組み合わせを満たす個数を最大にする…

Abst ABC 131 C問題 Anti-Division (300点)をpythonで解きました。 問題 [A,B]の整数のうち、CでもDでも割り切れないものの個数を求める。 atcoder.jp 方針 [A,B]の個数という問題なので、 [0,B]の個数から [0,A-1]の個数を引く ことで答えを求める。 CでもD…

Intro ARC077 D問題 「11」(600点) をpythonで解きました! Point 逆元を使った組み合わせの計算 問題 1~nの数字からなる長さn+1の数列が与えられる。 (1~nの数字の中で、一つだけ２回出てくる数字があって、それいがいは1回しか出てこない) k=1...n+1につい…

Abstract ABC 122 D問題(400点) 「We like AGC」 を解きました。 python こんな人にオススメ 数え上げの練習がしたい dpの練習 problem 以下の条件を満たす文字列を AGC文字列 とする。 A,G,C,T の４文字でできている "AGC"という文字列を含まない 任意の文…

概要 Atcoderで開催されてた、M-SOLUTIONS プロコンオープン D問題(500点)の解説記事です。 python でときました。 問題 入力 頂点数Nの木が与えられる。 N個の自然数 内容 木の頂点に与えられた数字を当てはめていく。 edge(a,b)があった時に、そのスコアを…

概要 ABC 128 C問題のswitchesをpythonでときました。 問題 atcoder.jp 解法 スイッチの付け方を全探索する。 ポイント bitを使ってスイッチのon-offの状態を表して、全探索する。 回答 # python template for atcoder1 import sys sys.setrecursionlimit(10…

概要 ABC 128 D問題の "equeue" をpythonで解いたのでその解説。 (D問題のequeneで繋げて、Dequeueですね。解いてから気づきました。) 問題 atcoder.jp 入力 N: リストの長さ K: 操作できる回数 V :整数のリスト(負の値もある) 内容 整数のリストが与えられ…

概要 ICPC 国内予選2010年のc問題を解きました。 judge.u-aizu.ac.jp pythonで時やりたかったけど、TLEな感じだたったので、 c++でやりました。 概要 x(x+1)(x+2)/6で表される数があって、 それを正四面体数と呼ぶ。 正四面体数をいくつか選んでその和が入力…

概要 ICPC 2017 C問題の 「A Garden with Ponds」 を解きました。(python) 問題ページ judge.u-aizu.ac.jp 回答方針 池となる長方形を、 4重ループで全探索 して、その中で池の容量が最大のものを選ぶ。 回答 池の長方形を 4重ループで全探索 する。 池の中…

abst 今回は、bitDPの練習でyukicoderの「走れ!サブローくん」をpythonでときました。 No.134 走れ！サブロー君 - yukicoder 解法 bitDPでの巡回セールスマン問題 ポイントは DP配列を二次元 にして、dp[すでに下ろした荷物][最後に訪問した場所]とすること…

概要 AGC033 B問題(600) LRUD Gameの解説をしたいと思います。 言語 python 問題 atcoder.jp 解法1 (嘘貪欲) 僕は、コンテスト中に嘘貪欲でACしてしまいました。 （自分の回答) https://atcoder.jp/contests/agc033/submissions/5262993 内容 先手が落とす方…