日本語によるプログラミングコンテスト
・問題： 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:…
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（AtCoder Beginner Contest 304）に参加しました。 結果 A,B,C,D,Eの5問正解でした。 D問題を提出した辺りからジャッジが詰まっていたみたいで結果が全然分からなかった。 おかげで正解しているかどうかわからないのでやり辛かった。 まだDDoS仕掛けられているのかなあ E問題まで解けたのにUnratedなのは残念 A - First Player 円卓に人が座っているので最年少の人を始点に全員分の名前を順番に出力する問題。 ループ処理と数値の大小比較ができれば解ける問題だと思う。 1回目のループ処理で最年少の人が何番目に…
https://atcoder.jp/contests/math-and-algorithm/tasks/panasonic2020_bHWが偶数と奇数で変わりますが、HかWが1のときは身動きが取れないので特殊ですね。 // Bishop #![allow(non_snake_case)] //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -> T { let mut line = String::new(); std::io::stdin().read_line(&mut lin…
いろんな種類の問題がある回でした。(1854->1922) scrapbox.io scrapbox.io scrapbox.io scrapbox.io
https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_bb奇数だと市松模様を考えれば存在しないことは明らかで、偶数だとパスが簡単に分かりますね。 // Move on Squares 2 #![allow(non_snake_case)] //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -> T { let mut line = String::new(); std::io::stdin()…
・問題： atcoder.jp ・参考文献： スタックとキューを極める！ 〜 考え方と使い所を特集 〜 - Qiita ・説明：幅優先探索を使ってとく。詳しくは参考文献を参照。プログラムの説明は'#'の数(kabe)とスタートを含むゴールまでの最短距離(dist[gx][gy]+1)を全体(H*W)から引いた値になる。これを素直に実装すればよい。 ・実装例： from collections import deque H,W=map(int,input().split()) field=[] for _ in range(H): field.append(list(input())) sx=0…
要素が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 のマスを選ば…
atcoder.jp安いほうから順に 個を選ぶことを考えてみます。 各種類を1つだけ買った時の価格を集合に加えます。 集合の中から一番安い価格を取り出します。 その価格に、さらに1つ追加で買うときの価格をに加えます。 は同じ値の重複を許さないようにして、から一番安い価格を取り出し、一つ追加した価格を加えることを繰り返したとき、回目に取り出した価格が求める答えです。 コード例 (Julia) using DataStructures function solve() # 入力 readInts() = parse.(Int,split(readline())) readInt() = parse…
atcoder.jp正の整数に対して なら なら を何回繰り返すと になるかという問題です。この操作を1回ずつ行うと、たとえばのとき回程度になるため時間がかかりすぎます。そこで、 の場合、 を で割った商と余りを求めます。 回の操作で、 になるので、 であれば次に と に対する操作を考えます。であれば、 回の操作後にと等しくなります。 コード例 (Julia) function solve() # 入力 readInts() = parse.(Int,split(readline())) readInt() = parse(Int,readline()) A,B = readInts() if…
学習と生活の記録。いわゆる日記。 先月はこちら。 haruguchi-yuma.hatenablog.com 5月は大きなイベント(RubyKaigi)などがあって、前後で結構行動が違うかも。 おしごと RubyKaigi前後で変わらずやってるのはコードを書くこと(それはそう)。 Template Method パターンで設計したコードをリファクタリングする作業をしていてレビューを通して勉強になることがたくさんあった気がする。たとえば、メソッド呼び出しで何度も同じデータを生成しているときはインスタンス変数でメモ化するだとか、知ってはいるけど自分が実践的にできてないようなことが補強されたイメージ…
AtCoder Beginner Contest 304 atcoder.jp 昨日はコンテストのジャッジが詰まり、コンテストが強制的なunratedになりました。 AtCoderは今攻撃されていて前はサイトを落とされ、今回はジャッジを詰まらされ（今回もDDoSなのか？）、憂き目に遭ってます。 みんなもネガティブなコメントが増えているときこそAtCoder社はがんばってほしい……こういう逆境に立たされてもがんばってくださいと思ってます。
経緯 いつもボードゲームや謎解きをして遊んでいるグループでSECCON Beginners CTF 2023にチームで参加する人を募集していたので参加してみた。 CTF初心者チームだったが、全員（元）競技プログラマなのでチームメイトが強かった。ちなみに調べたら誰も今年AtCoderに出てなかった。 僕はreversingカテゴリの問題をずっとやっていた。 バイナリの知識がほとんどなく、調べながらやっていたら自力で2(+1)問解けたので、考えたことを書く。 Half 問題概要 バイナリファイルが与えられる。 解法 とりあえずバイナリエディタが必要な雰囲気を感じたのでStirlingをダウンロード…
honto.jp 競技プログラミングにはいろいろな形式があって、なかでも人気のあるもののひとつにヒューリスティックコンテストがあります。与えられた入力データに対してそのスコアの高さを競うもので、1週間から数か月という期間に何度もプログラムを改善・提出し続けることからマラソンマッチと呼ばれることがあります。自分は競技プログラミングのひとつであるアルゴリズムコンテスには取り組んでいたものの、このヒューリスティックコンテストについては未経験。アルゴリズムコンテストは入力データに対して正解を求める速さを競うというもので、その性質上、この2つのコンテストで求められる知識には違いがあります。ヒューリスティ…
まだ、初心者だが遊びでAtCoderを一日一問している。 今日そこで、知っているけどあまり使わなかったgsubメソッドについて gsub 処理 gsubメソッドは指定した文字列を、特定の文字列に置き換えるメソッド。 引数 p "aaabbb".gsub("a", "A") #=> "AAAbbb" "既存の文字列".gsub("変更したい文字","変更後の文字列") ブロック p 'abcabc'.gsub(/[bc]/) {|s| s.upcase } #=> "aBCaBC" "既存の文字列".gsub("変更したい文字") { |"抽出された文字"| "文字に対する処理" } 以上！
執筆時レート：水色 問題文→https://atcoder.jp/contests/abc304/tasks/abc304_f 公式解説→https://atcoder.jp/contests/abc304/editorial/6511 目次 問題 制約 方針 計算量 実装 問題 高橋君と青木君は 日間アルバイトをする． 高橋君のシフト表は文字列 で与えられ， が#ならば 日目に出勤，. ならば 日目に欠勤する． 一方，青木君は以下の手順でシフト表を作成する． でない の正の約数 をとる． 日目から 日目までの勤怠を決める． の順に 日目の勤怠が 日目の勤怠と一致するように 日目の勤怠を決める…
問題の元ネタはこちら。 ABC の F 問題で、約数系包除原理の問題が出るような時代になったみたいです。 atcoder.jp 約数系包除原理で検索すると、見つかる有名どころの解説記事はここらへんでしょうか。本記事ではあまり包除原理自体の説明には踏み込まないので、仕組みを知りたい方はこちらの記事に飛ぶのがおすすめです。 qiita.com 以下、ABC304F の AC コード を少しだけ書き換えたものを置いておきます。 約数包除系問題の解答コードの雛型として利用することを想定しています。 from itertools import combinations import math def d…
解説AC https://atcoder.jp/contests/arc154/submissions/41983611 本質 逆順テク SSS（単純部分列）の判定はtwo-pointers的な累積テクでO(N) 一箇所に集めて分配 詳細 「Sの先頭の文字を任意の箇所に挿入できる⇒Sの後半の文字列がTの部分列」が一致できる条件になる。先頭の文字を一箇所に集めて分配するイメージを持つと先頭の文字しか移動できないので後半が不変という性質になり、それを判定すれば良いので逆順テクを使って処理すれば楽になって嬉しいかもしれないという気持ちになる。SSSの判定はtwo-pointers的な累積処理で判定で…
qiita.com
note.com
findy-code.io
qiita.com
www.slideshare.net
qiita.com
chokudai.hatenablog.com
qiita.com
qiita.com
