AtCoder

https://atcoder.jp/contests/abc304/tasks/abc304_fこれは、包除原理ですね。 題意を満たすシフトの数をF(M)とすると、N = 12で考えると、M=6とM=4はそれぞれF(6)とF(4)がありますが、両方にF(2)個分共通のシフトが含まれることが分かるので、結局トータルでは F(6) + F(4) - F(2) となります。 一般に、 ここで、はメビウス関数です。このように包除原理を使えば簡単なのですが、Pythonと同じように書くと負数の剰余が負になるというトラップが出てきますね。 // Shift Table #![allow(non_snak…

・問題 atcoder.jp ・参考 AtCoder AGC 033 A - Darker and Darker (緑色, 300 点) - けんちょんの競プロ精進記録 ・考えたこと：DFSかBFSを使うことは分かったが具体的なやり方は思いつかなかった。上の記事を参考にして、スタートを'#'としてbfsをする。'#'からの距離distが最大のものが答えとすれば良いということが分かった。・注意点：pypyで提出してください。 ・実装例： from collections import deque H,W=map(int,input().split()) field=[] for _ in ran…

https://atcoder.jp/contests/abc304/tasks/abc304_eUnionFindを作って、K個の条件はrootに直してペアをHashSetにして、クエリもrootに直してHashSetにあるかどうかを調べます。 RustではUnionFindをコーディングするのが大変ですね。parentも整数してやれば易しくなります。あと、手元では通ったusize::MAXがAtCoderでは見つかりませんでした。 // Good Graph #![allow(non_snake_case)] use std::cmp::max; use std::collections:…

・問題： atcoder.jp ・参考： https://atcoder.jp/contests/abc304/submissions/41948730 https://atcoder.jp/contests/abc304/submissions/41961121 ・説明 a,bの線でケーキを切るのでa,bの格子(切り分けられたケーキ)の中でいちごの位置を二分探索してそれをtにいれる。 c(辞書型で{key、value}と1つの要素に2つの値を持つ)を作ってcのkeyにtがすでにあったらc[t](cのvalue)に++、それ以外はc[t]=1 cのvalue(場所毎のいちごの数)のうち最大、最…

2023/6/3に開催された、東京海上日動プログラミングコンテスト2023(AtCoder Beginner Contest 304)に参加しました。 atcoder.jp 先週のARCでは、２完獲得したものの、茶パフォで惨敗。今回は、その負け分を取り戻すべく、頑張ろうという気持ちで臨みます。 Rated参加します。先週のARCの負け分を取り戻せる様に頑張ります。東京海上日動プログラミングコンテスト2023（AtCoder Beginner Contest 304） - AtCoder https://t.co/p9wIIKR6ql— devgenjin77 (@devgenjin77) 20…

ABC304E クエリ問題で，一つのクエリにつき高速に求める． 良いグラフの定義通りだと，全ての\(i \in K\)に対して調べることになるが， クエリでは1本しか辺を追加しないので，変化は少ない． クエリ毎に共通して使える部分が多くあるので，そこを前処理しておく． 良いグラフか判定する際，連結成分毎に考えれば良い． 各連結成分ごとに\(x_{i}, y_{i}\)が含まれているかが重要で， それ以外はグラフの形は影響しない．クエリで調べたいことは，異なる連結成分2つが与えられたとき， それを結んで良いかどうか．これを前処理する． あとは\(O(N), O(Nlog N)\)(または\(N\…

atcoder.jp・説明：dequeを使って実装する。dequeに0人目(1人目)を入れて、感染した人をif d>=math.sqrt(dx*dx+dy*dy):の条件分岐でdequeに入れていく。 これをwhileでdequeが空になるまでやる。また感染しているかどうかはflagで管理する(例えばflag[i]=1だとi番目の人は感染している)。・実装： import math from collections import deque n,d=map(int,input().split()) xy=[list(map(int,input().split())) for _ in rang…

2023/5/25 (木) 7:30起床. あさかつARC. A: D[i]=#{(B,C)|B*C<=i} を累積和使って求めて置いて, Σ(D[K/A]) をする. B: x=A/2 を全探索 C: 答えで二分探索 D: Qが奇数なら1回愚直に操作してQ:偶数にする. 操作を2回まとめると単にrotateになるので計何回rotateするか計算する. E: xを右にずらしたときに答えが増える間右にずらす その後は先週出れなかった一限のオンライン講義. これは数学の講義を英語で受けてみようという趣旨のもので元は留学生向けの講義であるが, 誰でも受けられる. 代数学, 幾何, 解析の3パートに分…

E - K-colinear Line atcoder.jp 今日のことをなにか話そうと思ったけれど、主にこの問題を朝から考えていたってことぐらいです。 朝からずっとこの問題に取り組んでました。 全然解けなくて泣きそうでした。 泣きはしないけど苦手な問題です。 ガチの数学っぽい問題です。

とてもいい感じの BFS の練習問題！ 問題へのリンク 問題概要 "atcoder" の並び替えである文字列 が与えられます。 文字列 に対して「隣接する 2 要素を swap する」という操作を繰り返すことで、"atcoder" となるようにしたいとします。 最小何回の操作で実現できるかを求めてください。 制約 は "atcoder" の並び替えによって得られる文字列 解法 この問題がグラフの問題になると言ったら驚く人もいるかもしれないですね。しかし、一見グラフの問題に見えなくても、グラフを用いて考察することが有効な場面はたくさんあります。 今回も、 頂点："atcoder" を並び替えて得…

atcoder.jp巨大なマス目から、(R,C) を選び、R行 または C列 のマス目の総和の問題です。 あらかじめ、各行の総和と各列の総和を計算しておくと、問題の値は、 と求められます。 ほとんどのマス目は 0 であることから、0以外の値のある行と列のみをリストアップします。 行・列を総和が大きい順に並び変えて、 の最大値を求めていきます。 列方向に探索するときに、 の値がそれまでの最大値以下であれば、それ以降の列は調べる必要が無くスキップすることができます。 また、(R,C)マスの値をすぐに取り出せるように、(R,C)をキーとする辞書型としておきます。 コード例 (Julia) funct…

atcoder.jp動的計画法で、サイコロを 回振ったあとに地点 にいる確率を とします。 さらに1回サイコロを振ることによって地点 のいずれかに確率で到達します。(地点が N より大きくなる時は、N に置き換えます。) このことから、 … と確率の加算を行います。これをループ処理することで、 回後にゴールに到達している確率が求められます。高橋君と青木君について、この確率を求めます。 この確率は累積確率なので、その差分が高橋君が 回目に初めてゴールに到達する確率になります。 このとき、青木君がゴールに到達していない確率は 1 から累積確率を引いた値で、これらの確率の積で高橋君が回目にゴールに到…

はじめましてpodowです。誰が僕のブログを見るのかわかりませんがとりあえず開設してみました。 何したらいいかわからないのでとりあえず自己紹介します。 性別:男 年齢:15歳 趣味:コーディング、試験、youtube コーディングを始めたのが3年前くらいです。最近AtCoderを初めましたが、もともとアルゴリズムが好きなのもあってハマってます(まだ練習問題しかやってませんが)。 試験に関してはまだHTML5レベル1とITパスポートしかやってませんが、知らなかった知識が入ってくるのが楽しくてハマりました。今は基本情報の勉強中です。基本的には授業の休み時間や移動中などの暇な時に勉強しています。 y…

atcoder.jp 一日一問。 基本的に過去問のA、B問題からやっている。 でも、今日選んだ問題は難しかったと思う。 正直わからなかった。だから、解説とほかの人の提出済みの答え見て将来、さっさとできるようになれたらいいなくらいの気持ちで、今は継続を主眼に行っている。 Find snuke の注目点 この問題の注目すべき点は、起点となる文字から八方向にそれぞれ値をとりに行く方法だ。実際思いつく人はすごいな、と感じた。

今日は2つAtCoderのABCのE問題を解きました。 昨日は1問も解けなかったので今日は2問解きたいなあと思ってました。 だいたい1日に1問、ABCの水diffの問題を解くことを目標にしてます。 平均してだいたいそれくらいできたらなあ、と。 なんとなく守れてる気がする。 偉いね！ 難しいのによくやっている。

前回 (ARC157) から約 3 ヶ月で ARC の writer をやったので，また感想とか元ネタみたいな当たり障りの無い話を綴っておこうかと思います．まだ問題を見ていない方は，ぜひご覧になっていただいて，できれば 1 問でも取り組んでいただけるととても嬉しいです．（定型文） 明日、対戦よろしくお願いしますhttps://t.co/ENZ8CYmgSj pic.twitter.com/Rwf6k2ASmu — ⚫️Y.Y.⚪️ (@ygussany) 2023年5月27日 ARC161 おつでした～今回は証明セットです、解説を書くのがしんどかった… — ⚫️Y.Y.⚪️ (@ygussan…