AtCoder

・問題 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(場所毎のいちごの数)のうち最大、最…

https://atcoder.jp/contests/abc304/tasks/abc304_d二分木を作って、イチゴが一つになるかもう分割できなくなるまで分割します。 Rustで二分木を作るのは大変ですね。 // A Piece of Cake #![allow(non_snake_case)] use std::cmp::{min, max}; //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -> T { let mut line = String::new(); std:…

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（AtCoder Beginner Contest 304）に参加しました。 結果 A,B,C,D,Eの5問正解でした。 D問題を提出した辺りからジャッジが詰まっていたみたいで結果が全然分からなかった。 おかげで正解しているかどうかわからないのでやり辛かった。 まだDDoS仕掛けられているのかなあ E問題まで解けたのにUnratedなのは残念 A - First Player 円卓に人が座っているので最年少の人を始点に全員分の名前を順番に出力する問題。 ループ処理と数値の大小比較ができれば解ける問題だと思う。 1回目のループ処理で最年少の人が何番目に…

更新日時 2023/06/07/07:07 Qiita Trends Daily 1位 ※前日9位 初心者,機械学習,AI,新人プログラマ応援,ChatGPT Qiita Trends Daily 2位 ※前日2位 ポエム,新人教育,コミュニケーション,チームビルディング Qiita Trends Daily 3位 ※前日5位 ShellScript,Linux,UNIX,macOS,シェル芸 Qiita Trends Daily 4位 [New] Android,設計,JetpackCompose Qiita Trends Daily 5位 [New] WWDC,WWDC23,WWDC202…

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

はじめに kureha といいます。この度 AtCoder にて入黄を果たしました。本記事はその記念に書いたものとなります。 自己紹介 ・ハンドルネーム : kureha ・年齢 : 20 + n 歳 ・職業 ? : 大学生 ・競プロ歴 : 約 2 年 ・使用言語 : C / C++ AtCoder 入黄 見出しの通り、AtCoder 入黄を果たしました。 黄色に到達するまでのコンテスト参加回数は 53 回、期間は約 1 年ほどとなります。競プロ全体で見ても黄色コーダーの中で見ても短い方だと思います。 初めてのコンテスト参加が競プロの始まりだったわけではなく、以前から過去問には挑んでいました。…

問題 F - Wine Thief 解法 数列は 0-indexed とする。 $\displaystyle \mathcal{B} _ {i, p} = \left\lbrace (B _ 0, \ldots, B _ {i - 1}) \in \lbrace 0, 1\rbrace ^ i \mid B _ j + B _ {j + 1} \neq 2 \ (\forall j\in\lbrace 0,1,\ldots, i-2\rbrace) \land B _ {i - 1} = p \right\rbrace$ とする。これは、ラフに言えば、前 $i$ 個のワインに対する盗む(=1)…

はい。 AtCoder Beginner Contest 070 なんともないかも。 A - Meal Delivery https://github.com/clarinet758/atcoder/blob/main/abc/b051_075/b071/a1.cpp 絶対値をとって比較。 B - Not Found https://github.com/clarinet758/atcoder/blob/main/abc/b051_075/b071/b1.cpp -'a'でカウントして適当に調べました。 C - Make a Rectangle https://github.com/clari…

■M - Candies(EDPCM) https://atcoder.jp/contests/dp/tasks/dp_m [x^k]Π(1-x^(a+1))/(1-x)■D - Binomial Coefficient is Fun(ARC110D) https://atcoder.jp/contests/arc110/tasks/arc110_d f_i=ΣBinom(b,a_i)x^bとして 求めるものは [x^m]1/(1-x)*Πf_iであり f_iを睨みつけると負の二項係数を思い出すので f_i=x^a_i/(1-x)^(a_i+1)がわかり [x^m]1/(1-x)*Πf_i =…

要素がu32型のvecの総和を求める際、いつもはfor式を使い、sum()を使わないのだが、ちょっとかっこつけて使ってみたら失敗したという話です。 和を取るとき、オーバーフローするというのはよくあるのだが、sum()にをつけてもダメだった、結果をキャストするだけらしい。今日はこれでハマった。 そもそも、N=109、A[i]=109 (0≦i<N)みたいな、よくある設定がありますが、あれは符号なし32bit整数型(unsigned int/u32)で計算すると桁あふれすることを狙っている場合があります。 今回の計算の場合以下のように見積もると、32bitでは足りない値が出てきました。そこで最後の…

はい。 AtCoder Beginner Contest 070 なんともないかも。 A - Palindromic Number https://github.com/clarinet758/atcoder/blob/main/abc/b051_075/b070/a1.cpp 1桁目と3桁目を見る。 B - Two Switches https://github.com/clarinet758/atcoder/blob/main/abc/b051_075/b070/b1.cpp 始まりが遅いのと終りが早いの。あと時間が重複してるとこがあるか。 C - Multiple Clocks http…

atcoder.jp 期待値の求め方 マスの数は個で、ここから 個 の選び方は、 通りです。 選んだマスの位置を とすると、スコアは となります。スコアが になる選び方が 通りあるとすると、スコアの期待値は と計算されます。ここから を求めることを考えていきます。 場合の数の計算 縦 マス、横マスの固定範囲内で マスの選び方は 通りですが、これにはスコアが より小さな選び方も含んでいます。 そこで外側の4辺について、辺上に選んだマスがある場合(〇)とひとつも無い場合(×)で分類します。これによってマスの選び方を 種類に分類できます。求めたいのは、①の場合の数です。選び方全体 辺A のマスを選ば…