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回目のループ処理で最年少の人が何番目に…

5月の目標は以下でした。結論から言うと、6つの目標中3つ達成で、50%の達成率です。1つずつ達成状況を確認します。 5月の目標・統計検定1級合格に向けて勉強を継続する(コミュニティに入ったので、そこの課題を継続する)・統計検定1級の過去問を1回解いて、難易度を把握する・AtCoder ABC2回以上参加(土曜日の夜があくようになったので)・キャッシュフロー整理(自動送金などの設定含める) — takus (@takus4649) 2023年5月9日 追加で2点・7つの習慣読了・フィットネス2回目行く — takus (@takus4649) 2023年5月10日 統計検定1級合格に向けて勉強を…

とてもいい感じの 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 から累積確率を引いた値で、これらの確率の積で高橋君が回目にゴールに到…

atcoder.jp各クエリで を数とみなした値を更新していきます。 クエリ1は、値を10倍してを加えます。 クエリ2は、先頭の数字にをかけた値を引きます。 このクエリのために、追加する数字を配列に記録することと、をあらかじめ計算しておきます。 それぞれの値は、mod 998244353 での値とします。 クエリ3は、更新している値をそのまま出力するだけです。 コード例 (Julia) _MOD = 998244353 function solve() # 入力 readInts() = parse.(Int,split(readline())) readInt() = parse(Int,r…

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…

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