ARC 097 D Equals (python)

atcoder.jpけんちょんさんのガイドに沿って解き進めています。 union find の問題。 交換する数字そのものが与えられるので、どことどこを交換したらいいかを効率的に調べる必要があります。 まず、数字から位置を求める配列を作りました。 例えば、上の様な…

3N Numbers

priority_queueの問題を解いてみた。atcoder.jpこの問題を言い換えると、真ん中のN個の数字に仕切りを置いて、その左側を最大化、右側を最小化するようにN個ずつ選んで、左の和から右の和を引けばよいことになる。 ただし、仕切りのパターンがN+1個あり、そ…

ABC 178 初5完!

初5完して、パフォーマンスは1174でした。 近いように見えて遠い緑。速く緑に行きたい! パパッと行くためには、全完必要。時間切れになってしまったFはこのサイトがわかりやすい。 tiramistercp.hatenablog.com

3. Longest Substring Without Repeating Characters

問題:Given a string s, find the length of the longest substring without repeating characters.Input: s = "abcabcbb" Output: 3 Explanation: The answer is "abc", with the length of 3. 文字列の中から、連続する文字列で重複がない最長の長さを求…

ABC141D priority heap

priority heapを使うと、最大値の取得がlogNで可能に。 ランダムな値の挿入もlogNで可能。 import sys import heapq stdin = sys.stdin n,m = map(int, stdin.readline().split()) # heap は通常、最小値がrootのヒープを作成する。最大値を取得するために、…

ABC177E パイソンで

import sys from math import gcd stdin = sys.stdin # 標準入力 n = int(input()) an = list(map(int, stdin.readline().split())) # mまでの最小の素因数リスト つまり、8ならば2、17ならば17 # この数が分かれば、素因数分解の際に何で割ればいいか分かる…

ABC177

ABCDの4完で、パフォーマンス814でした。 緑がかすかに見えてきた。

pythonのsortの公式ドキュメントを読んでみた。

要点 sortの方がsortedよりも速い。 キーをラムダで指定するより、itemgetterの方が速い itemgetterでは、二段階でのソート条件を指定できる。 パイソンでは、Timsortを使っているらしい。参考 from operator import itemgetter sorted(student_tuples, key=…

GitHub で初めてのHPを公開

まずは、Create a new repositoryから、新しいレポジトリーを作成。 名前は、ユーザーネーム.github.io.git とした。作成したレポジトリーアドレスを、自分のパソコンにクローン。 コマンドプロントから、git clone https://github.com/username/username.gi…

ABC 176

また少しレーティングは上昇。今日はA-Cの三問解けましたが、緑以上になるためにはやはり、4問5問解かないとダメそうです。時間内には解けませんでしたが、今回はD問題、E問題もそんなに難しくなかったです。 今日の学びは、E - Bomberから。 if 〇〇 in lis…

ABC175

C問題まで解いて、少し上がりました。

for/else

for 文の最後にelse節を書くと、ループが最後まで回った後、else節が実行される。 今までは、if節で、iが最後になった時と書いていたけど、知ってればちょいちょい便利! 早速使ってみた。atcoder.jp n = int(input()) ls = [int(input())] for _ in range(n…

区間スケジューリング問題を考える

区間スケジュール問題では、後ろの値でソートして、前側から順に決定していくが、その答えが本当に最適解なのか考えてみた。上段の図を、アルゴリズムから決定したものとして、それが最適解でなかったと仮定する。その場合、両端のバーの中に2個のバーが含ま…

全BIT探索 061ABC C - たくさんの数式

s = input().rstrip() n = len(s) def value(m): num = s[0] ans = 0 for i in range(1, n): t = (m >> (i - 1)) & 1 if t == 1: ans += int(num) num = s[i] else: num = num + s[i] ans += int(num) return ans count = 0 for i in range(2 ** (n - 1)): c…

Data Science: R Basics受講してみた

統計でRを使いたいと思っていたので、前から気になっていたData Science: R Basicsを受講開始しました。セクション4までありますが、1を終えた感想は、 RやRStudioのインストールから教えてくれる。 使い方は基本から教えてくれ、分かりやすい。 Data Camp…

AtCoder茶色になりました。

AtCoder茶色になりました。 ついに灰色脱出! 本日、ABD問題を解いて、茶色になれました。 Cはオイラーの定理で制約があるのか!全然しらなかった。 Eも冷静に二分探索すれば解ける問題でした。 次は4問解きたい!

edxでCS50受講しました!

こんな感じの認定書もらいました。 内容は、C言語の基本、パイソン、SQLがカバーされていて、毎回ぎりぎりなんとかなる程度の難易度の課題が出され、提出して正解しないと修了できません。正直時間はかかりましたが、コンピューターサイエンスの未経験でもこ…

東京海上日動 プログラミングコンテスト2020 C問題解けず…

東京海上日動 プログラミングコンテスト2020、2完して少しレートが上がりました。3問目は、プログラム自体は書けたのですが、タイムアウトしてしまいました。終わった後も検討したのですが、改善せず。誰か教えてください!! 問題文 数直線上に電球が NN …

ABC 169 4完しました。

ABCDの4完をして、パフォーマンス966。10級に昇級しました。 Cが最後までなぜか通らなくて、Decimalを使って解決しました。 import decimald = decimal.Decimal('1.1') 素因数復習! n= int(input())factors=[]for i in range(2, int(n**(0.5))+2): if…

AtCoderコンテスト2回目

NOMURAプログラミングコンテスト2020でABを完答して、レートが88に上がりました! C問題は、最後に解法(ノードの上限に制約があること)を思いついたのですが、時間切れ。 明日もあるので、頑張ります!

うぉー、ついに自力で解けないB問題に遭遇。ABC 128 B

最後に残していたB問題。う、解けない… リストinリストのソートです。 B - Guidebook / 実行時間制限: 2 sec / メモリ制限: 1024 MB 配点 : 200200 点 問題文 あなたは美味しいレストランを紹介する本を書くことにしました。 あなたは NN 個のレストラン、レ…

はじめてlambda使ってみた!ABC 138 B

問題文 NN 個の整数の列 A1,…,ANA1,…,AN が与えられます。 これらの逆数の総和の逆数 11A1+…+1AN11A1+…+1AN を求めてください。 制約 1≤N≤1001≤N≤100 1≤Ai≤10001≤Ai≤1000 入力 入力は以下の形式で標準入力から与えられる。 NN A1A1 A2A2 …… ANAN 出力 11A1+……

Trick or Treat

問題文 ある街に、NN 人のすぬけ君(すぬけ君 11 、すぬけ君 22 、 ...、 すぬけ君 NN )が住んでいます。 この街には、 KK 種類のお菓子(お菓子 11 、 お菓子 22 、....、お菓子 KK )が売られています。お菓子 ii を持っているのは、すぬけ君 Ai,1,Ai,2,⋯,Ai,…

AtCoder コンテストに初参加!

ここ数日で、ABCのA問題はすらすら書けるようになってきました。コンテストに参加してみよう!って思って見てみると、今週はABCは開催されない模様。 ただ、AGCが開催されることを発見し、すかさず参加してみました。 結果は、 ずーん。 激むずい。ABC-A問…