AtCoder

こんにちは。milkcoffee です。 AtCoder で黄色になりました！！ ARC133 で念願の黄色になることができました。本当に嬉しいです。 嬉しいので青に落ちる前に色変記事を書いてしまおうと思います。 初めましての方は青になった時の色変記事から読んでみてください！ 入青！一年間やってきたこと - milkcoffeeのブログ ということで、青になるまでのことは既に書いてあるので、青→黄のことをメインで書きます。 精進内容 レート遷移とそのときの気持ち 水青反復期 青下位ゆったり期 レート爆上がり！→入黄失敗 入黄！！ 質問フォームへの回答 おわり 精進内容 AtCoder Prob…

ABC236Bの解説 atcoder.jp 解答コード https://atcoder.jp/contests/abc236/submissions/28778202 問題 各番号に4つの種類があるトランプについて，ある一つの番号だけが1種類欠損している状態を判別する問題です． 解説 欠損していない番号は4種類のカードがあり，欠損している番号だけ3枚になるので，そこを処理して判別するプログラムを記述します． まずは，標準入力を読み取って N = int(input()) A = list(map(int, input().split())) 4枚揃うかどうかを数えるカウンターとなるlistを用…

先週のABC235でRatingが1200台に到達し、ランクが緑色から水色になりました。 色が変わると記事を書く風習がどうやらあるらしいので、駄文ながら色変記事を書きます。 精進内容 勉強したもの コメント 最近の傾向について 問題への取り組み方について 今後の目標 おわりに 精進内容 書いたのが色変してから１週間後なので直後とは多少差がありますが、このような感じです。 だいたい400問近く解いています。そこそこ問題を解いてきているつもりですが、そんなにたくさん埋めているわけではないです。 コンテスト初参加が7月中旬なので、その前に少しだけ問題を解いています。当初はFまで解けるようになってから…

2022/1/22に開催されたAtCoder Regular Contest 133に参加しました。 atcoder.jp 先週のコンテストは所用で参加できなかったのですが、今週は土日ともRatedコンテストが続くということで、先週参加できなかった分今週は連勝して帳尻を合わせようかなという気持ちで臨むこととしました。 Rated参加します。この土日で連勝できるように頑張ります！AtCoder Regular Contest 133 - AtCoder https://t.co/gNov1Do6Xq— devgenjin77 (@devgenjin77) 2022年1月22日 今回の結果 で、結…

問題の要約 鉄道のとある路線にはN個の駅が存在し、始点から終点に向かってi(1<=i<=N)番目の駅の名前はSi。 普通列車は全ての駅に止まるが、急行列車は全ての駅に止まるとは限らない。 急行列車はM(M<=N)個の駅にのみ止まり、j(1<=j<=M)番目に止まる駅の名前はTj。 ただし、急行列車は始点と終点の両方に止まることが保証される。 N個の駅それぞれについて、その駅に急行列車が止まるかどうか判定せよ。制約 2<=M<=N<=10^5 Si(1<=i<=N)は英小文字のみからなる1文字以上10文字以下の文字列 Si≠Sj(i≠j)入力 N M S1 ... SN T1 ... TM考え方…

問題の要約 整数1,2,...,Nが書かれたカードが4枚ずつ、合計4N枚ある。 これらのカードをシャッフルしたのち1枚のカードを選んで抜き取り、残りの4N-1枚を束にして渡された。 渡された束のi(1<=i<=4N-1)枚目のカードには、整数Aiが書かれている。 抜き取られたカードに書かれていた整数を求めよ。制約 1<=N<=10^5 1<=Ai<=N(1<=i<=4N-1)入力 N A1 A2 ,,, A4N-1考え方 1,最初に整数1,2,...,Nが書かれたカードが4枚ずつあり、それから1枚のカードだけが抜き取られるのだから、抜き取られたカードは3枚になっている。 2,vectorで枚数…

問題の要約 英小文字からなる文字列Sが与えられる。 Sの先頭からs文字目とb文字目を入れ替えて得られる文字列を出力せよ。制約 2<=|S|<=10 1<=a<b<=|S|入力 S a b考え方 1,C++には値を入れ替えるswap関数があるのでそれを使う。 実際のプログラム#include<iostream>#include<string> using namespace std; int main(){ string S; cin >> S; int a,b; cin >> a >> b; swap(S[a-1],S[b-1]); cout << S << endl; return 0;}

https://atcoder.jp/contests/abc173/tasks/abc173_c AtCoder ProblemsのRecommendationでDifficulty: 653、Solve Probability: 41%でした。 bit全探索で解くことができました。 for loopごとにリストをコピーしたのですが、多次元リストの場合はdeepcopyでないといけないことを知りました。 import copy H, W, K = map(int, input().split()) C = [] for i in range(H): s = input() C.append(…

https://atcoder.jp/contests/abc158/tasks/abc158_d AtCoder ProblemsのRecommendationでDifficulty: 610、Solve Probability: 46%でした。 クエリごとに単純な文字連結をするとTLEになってしまったため追加する文字列をリストで持っておき最後に連結しました。 解説にあるようにdequeを使っても良かったです。 S = input() Q = int(input()) # 文字列の順序が反転してないかどうか flag = True # 先頭に追加する文字のリスト first = [] # 末…

https://atcoder.jp/contests/abc178/tasks/abc178_c AtCoder ProblemsのRecommendationでDifficulty: 653、Solve Probability: 41%でした。 検索したところ異なるn個のものから重複を許してr個並べるのはn**r通りあるとわかり、各集合が何通りあるかを調べて答えを求めました。 MOD = 10 ** 9 + 7 N = int(input()) print((10 ** N % MOD - (9 ** N % MOD * 2 - 8 ** N % MOD)) % MOD )

https://atcoder.jp/contests/abc126/tasks/abc126_c AtCoder ProblemsのRecommendationでDifficulty: 638、Solve Probability: 42%でした。 Kを2で割っていき、サイコロの目がある以上ある値未満の場合のコインを降る回数を求め、確率を計算していきました。 import bisect N, K = map(int, input().split()) # Kを2で割って小数点を切り上げたもののリスト # (Kになるまでコインを降る回数ごとにその最小のサイコロの目の値のリスト) l = [] #…

はじめに 緑色になった時のスキル 緑色から水色になるために効果的だったもの 勉強法 灰~水diff埋め ゆきこの算数タグ埋め EDPC埋め アルゴリズム セグメント木、遅延セグメント木 解説を見るタイミング 印象に残っている問題 最後に はじめに 11月20日のABCで無事入水できたので、いつか誰かの役に立てばいいなと思い入水記事を書かせていただきます。 seiyu0225さんのトヨタシステムズプログラミングコンテスト2021(AtCoder Beginner Contest 228)での成績：1162位パフォーマンス：1352相当レーティング：1193→1210 (+17) :)入水しました…

https://atcoder.jp/contests/abc130/tasks/abc130_c AtCoder ProblemsのRecommendationでDifficulty: 626、Solve Probability: 44%でした。 実際に図を描いてみたところ、長方形はどの一点からでも面積を二等分にする線が引け、長方形の真ん中の点からは面積を二等分にする線が複数引けるようです。 W, H, x, y = map(int, input().split()) ans1 = W * H / 2 if x == W / 2 and y == H / 2: print(ans1, 1) …

第八回 アルゴリズム実技検定 (PAST) L - K番目の絶対値 を解いた。 問題: https://atcoder.jp/contests/past202109-open/tasks/past202109_l 「連続した空でない部分列の総和」は累積和の 2 点の差で求める。 2 点の全探索は O(N^2) で N <= 3*10^5 からこれは間に合わない。すべてのスコアを求めて K 番目を求めることはできない。 こういう場合はスコアを二分探索してみる。スコア x を決め打ちしたときに x よりも小さいスコアの個数が K 個未満と以上で二分探索すれば K 個以上の側が答えになる。 ……ここ…

1.方針まず、並べて実験してみる。すると、長方形の畳をA枚並べると、正方形の畳の敷き方は一通りに定まることがわかる。長方形の畳の並べ方は、左上の1メートル四方のスペースから順に敷き詰めていくと考えると、各スペース毎に「横向きに敷く」「縦向きに敷く」「何も敷かない」の3通りある計算量は3**16だが、再帰が途中で打ち切られるパターンもあるので、間に合いそう。2.ソースコード コードの途中でresを初期化しておかないと、resの値が累積的に計算されるので注意。 イメージとしては、再帰の底の値だけを拾ってくるイメージ。 h, w, a, b = map(int, input().split()) u…

今日はいまいち調子が悪く、あんまり進捗ありませんでした。 とりあえず、昨日積み残していた競プロ典型90問の問9をACしました。 atcoder.jp この問題は全探索による解法は浮かんで、でも だから無理だなぁ、と思いました。ただ、とりあえず書けることが大事だとも思ったので、思うように書いてみてTLEは出せました。 制約的に、おそらく三重ループの最後を対数時間に落とせれば全体として になって通るなぁ、と考えました。2点は全探索で良いので、注目している1点から引ける線分のうち、注目している線分（ベクトル）と正反対に近いものを対数時間で見つけられれば良いんだけどなぁ…と思いながら、方法が分からず解…