日本語によるプログラミングコンテスト
Cみたいな考察によってなんとかなる問題を解けるようになりたいです。(1946->1956) scrapbox.io scrapbox.io
2023/3/11に開催されたAtCoder Beginner Contest 294に参加しました。 atcoder.jp 先週のARCでは０完爆死という結果で、レート大暴落を喰らってしまいました。今回はなんとか水パフォ以上取って、レートを戻せるように頑張ろうという感じで臨みます。 Rated参加します。先週のARCで爆死した分を取り戻すべく、水パフォ目標で頑張ります✊AtCoder Beginner Contest 294 - AtCoder https://t.co/n05PLDCUdB— devgenjin77 (@devgenjin77) 2023年3月19日 今回の結果 なんとか５…
問題 atcoder.jp 問題概要 括弧を含む四則演算の式が与えられるので、答えを整数で出力する。ただし、式は画像で与えられる。 式の画像は、Courier Primeというフォントの各文字に対して回転、縦横の拡大（縮小）、せん断変形、平行移動を行って生成される。さらに、確率で画素を反転させるノイズが生成される。 3*3-4（問題ページより引用） この問題について 2014年2月に開催されたJAPLJさんのお誕生日コンテストで出題された問題。 AtCoderで開催されるお誕生日コンテストではいわゆるギャグ寄りの問題が出題される傾向にある（というよりこのコンテストが原点？）が、この問題はその中…
https://atcoder.jp/contests/abc294/tasks/abc294_dBTreeSetを使えば簡単で、呼ばれていない人のsetと呼ばれたけど受付に行っていない人のsetを作ればよいです。 ただ、 let e = not_called.iter().next().unwrap(); not_called.remove(e); だとcannot borrowと怒られてしまいますが、 let e = not_called.iter().next().unwrap(); let f = *e; not_called.remove(&f); とすればfにコピーされて通ります。…
最近、会社のSlackにある競プロチャンネルにジョインしたのもあって、久しぶりに競プロ熱が戻ってきたので参加している。 昨日行われたABC294に参加したのでその感想とか。 なお、問題の意図や解き方を解説するものではなく個人の感想です。またABC294のネタバレになるのでこれから挑戦される方は注意。 A - Filter / B - ASCII Art A - Filter B - ASCII Art 簡単なので特になし。 ACした回答 問題A 提出 #39849428 - AtCoder Beginner Contest 294 問題B 提出 #39854564 - AtCoder Begi…
https://atcoder.jp/contests/abc293/tasks/abc293_dグラフを作って隣接ノードが2つずつあればループになっています。 ただ、問題なのはノードが2つの連結成分です。1と2を連結すると、 {1: [2], 2: [1]}となりますが、反対側を結んだ時に強引に、 {1: [2, 2], 2: [1, 1]}と隣接ノードを加えるとうまくいきます。 // Tying Rope #![allow(non_snake_case)] use std::collections::{HashSet, HashMap}; //////////////////// libr…
ABC292 問題 提出 2023/03/18, 2023/03/19 このセット、Fが数学問題だったからかなりパフォ貰えそうで、（リハビリ終えた上で）リアタイで解きたかったなぁ〜という気持ちに！ と一瞬思ったが、Rubyで書いていたらE問題で絶対ペナってただろうから、そんなことないか😐 引き続き精進頑張る🔥 A 自然に解いても1行なの嬉しい！笑 B case, when 自分では最近書いてなかった気がするから久々の登場 C 約数の個数を先にカウントしておけば良い めっちゃ見覚えのあるやつだ〜 この計算量が意外と少なくて済むの懐かしい……！ D map!(&:uniq!) と、 map!(&:…
ARC133C \(\equiv\)は\(mod\ K\)とする． 必要条件や，上限の見積もりを考える． 判定問題最大の前に，簡単のため判定問題を考える． 行列において掛かれた値の和は， 行方向と列方向それぞれで集計すれば， \(\sum_{i \in H} A_{i} \equiv \sum_{j \in W} B_{j}\) が分かるので，これが必要条件． これは十分条件でもある． 実際，左上の行列を\(0\)で埋めておいて， 一番下の行と一番右の列で帳尻を合わせることを考えると， 一意に決まる． 一番右下のマスの埋め方に問題がないことは， \(\sum_{i \in H} A_{i} \…
ARC132C まず，愚直なDPを考えると， \(dp_{i,s} := \) \([0,i)\) まで,使った数のset \(s \in 2^{N}\). これは TLE, MLE. 改良を考える． \(i \in N\) は減らすのが難しいので， \(s \in 2^{N}\) を減らすことを考える． 与えられた条件から，任意の \(i \in N\) に対して， \(- d \leq p_{i} - i \leq d\). よって， \(p_{i}\) の候補は \(2d+1\) 通りに絞れる． したがって，状態が \(O(2^{2d+1})\). 遷移は \(O(N)\). 使っている…
ARC135C 最終形の性質から考える． 操作を1回以上施した場合，帰納的に ある \(k \in N\) があって，任意の \(i \in N\) に対して \(a_{i}\) は \(a_{i} \oplus a_{k}\) の形． これは， \((x \oplus y) \oplus (z \oplus y) = x \oplus z\) であることから確かめられる． すなわち，操作を1回以上した場合は，操作を1回した場合に帰着できる． よって，操作は0 または 1回と仮定してよい． 実装操作を全探索する． for \(x \in \{0\} \cup a \) as set に対して，…
AtCoder Beginner Contestの過去問から、その提出コードの解答例です。 AtCoderとは、コンテストを通じて、プログラミングやアルゴリズムを学習するサービスです。 atcoder.jp プログラミングコンテストとは、「与えられた問題をいかに素早く、正確に」解くことができるかを競うものです。 「競技プログラミング」を略して、「競プロ」などと呼ばれています。 #C - Merge Sequences atcoder.jp僕が作成、提出したコードは、以下のとおりです。 /* AtCoder Problems in C++ #C - Merge Sequences https:/…
尺取法（Two Pointer Techinique）テンプレート auto tpt=[&](auto& seq, auto sf, auto& res)->void seq: 入力列全体 sf: 入力列の先頭要素 (seq.front()) res: 結果 auto tpt=[&](auto& seq, auto sf, auto& res)->void { deque<decltype(sf)> sub; ここで初期化をする; for(auto& e:seq) { 右手関連の処理; sub.push_front(e); while(!sub.empty()&&条件を満たさない間くり返す) …
どうも、お久しぶりです。汁と申します。 今まではふざけた記事だったり将棋記事を主に書いて来ましたが、今回は違った記事になります。 まず今回お話しするpaizaというサイトについて、 paizaとは、ほぼ無料で学習できるpaizaラーニングや新卒向けの就活サイトであるpaiza新卒など、多くのサービスを提供しているサイトです。 今回お話しするのはそのpaizaさんにある「スキルチェック」というサービスについてです。 このスキルチェックにおいて最高ランクであるSを先月に取れたので、せっかくだし自分語りをさせていただきたくこの記事を書いています。 プログラミング歴 筆者は情報系の専門学校に通っており…
ちょっと悩んでしまったが、良い感じにきれいに解けた。 解法 一般に、、とする。 によって構成される格子の1マスに注目して、これがいくつの長方形に含まれるかを考えると、これは となる。(縦の辺については、左側は通り、右側は通り、横の辺については、上側は通り、下側は通りあるので、上のような式になる) よって、求めるべき答えは、 となる。は独立しているので、簡単に式変形できる。 左右のカッコの中身は見ての通り、愚直に計算することでそれぞれで計算できるため、全体でで答えを出すことができる。 実装例は以下の通り。 Submission #39974478 - AtCoder Beginner Conte…
はじめに Toyota Programming Contest 2023 Springの決勝に参加させていただきました。 JOI、ICPC意外のオンサイトは初めてでとても楽しかったので記録として残しておきます。 予選A うおーーーブザービートで7完したありがとうございました!— KowerKoint2010 (@KowerKoint2010) 2023年2月4日 普段のABCよりARC寄りの重いセットと書かれていて、ARCが苦手な僕は不安でした。 Fで詰まって焦ったんですが、なんとか7完できたので国内51位という結構な成績で予選を通過しました。 普段より面白いセットでした。 予選B kotam…
atcoder.jp メモ pythonの.indexを使った解法を投げたらTLEして詰まってしまった 110の単調性を利用する、みたいなのができなくて反省・・・。
JOIG 2022/2023の春季トレーニングに参加しました。 問題のネタバレありです。 ~Day -1 直近１年の精進はこんな感じ。↓ Heatmap 気が向いた時にABCに出ていた。特に最近はほとんどパソコンに触れられておらず春合宿に参加するかどうかもかなり悩んだが、色々な人と交流できる機会だと思って参加することにした。 3月に無駄に忙しいスケジュールを組んでしまい、春合宿開始前から既に体力的に限界。腕慣らしのために久々に出たABCでは３完という素晴らしい成績()を残した。 Day0（表彰式＆交流会） 駅さえ間違えなければ大丈夫だと思っていたらその後思いっきり迷った。安田講堂は東大生でもな…
いわゆるJOI2023春合宿というやつで情報オリンピックの代表を決めるやつです。 3問5時間のセットを4セット全部走りました。 春合宿の参加者はライブラリや検索が禁止なので自分もそれに則ってやりました。 ただ環境はいつも使ってる VSCode 等を使いました。 問題概要はこちらから (まだ出ていないので出たら追記する) Day 1 A currencies, B festival2, C passport, 24:00:00 start 0:29:10 C 0 問題文を勘違いしていて実装したので当然 $0$ 点 1:12:01 A 100 銀貨を使う枚数が少ない関門から貪欲に銀貨を使えば金貨の…
競技プログラミングを開始して4年半、青になってからは2年半でようやく黄色になることが出来ました。 本当は次のARCで青落ちしてまた戻ってこれたらこの記事を書こうと思っていたのですが、時間が経過するごとに色々書きたいことを忘れそうなので忘れないうちに書くことにしました。 青〜黄になるまでにやったこと 大体時系列順に並んでいると思います。 CF バチャ 記憶が正しければ青になりたての頃に CF div2, ECR バチャをそこそこ高頻度でやっていました。 結論から言うと実力向上には間違いなく役に立ったのですが、upsolveをしっかりしないまま次のバチャを始めたりしていて効率の悪い精進になってしま…
初めに atcoder.jp 解けなかったので 敗因 := と の集合が等しくなるような最小の := と の集合が等しくなるような最大の みたいなものを考えて, set の比較が O(1) でできると信じていたので裏切られて TLE. (WA はなぜか分からない) atcoder.jp 解法 サイズだけ考える→重複を抜いたもので考える atcoder.jp 終わりに いろいろな別解があるっぽい(User解説がたくさんあったので) 目を通してみて, お勉強するかも?
初めに atcoder.jp 解けなかったので 敗因 典型1 最大/最小から K 番目の要素は答えで二分探索する←知ってた 典型2 ふたつの組み合わせの数え上げは, 片方を固定してみる←知ってた 典型3(?) 砂糖/食塩水の問題はある濃度に達するまでの砂糖の量とかをみるといい←知らなかった 解法 「 x % 以上の溶液が K 個以上あるような最大の x を求める」問題に言い換える. これは「 x % 以上の溶液はいくらあるか?」という問題を用いて二分探索できる. 全ての溶液に対して, 「 x %にするための砂糖の量との差」を求めておいてソートしておくことで, 片方を固定したときに二分探索を用い…
こういうO(1)で気合導出、みたいな問題はめちゃくちゃ苦手… 解法 早い話、ありうる部分列を列挙して重複を除去すれば答えが出る。制約が大きいので重複の仕方が爆発してダメそうに見えるが、重複している数字が1個しかないので、重複の仕方を上手く見つけて場合分けすれば計算できる。 重複している数字をと置いてで数列を区切り、それぞれ左から区間をとする。 それぞれの区間から1個も使わないときと1個以上使うときをに対応させると、 の4つの組が重複していることに気づける。 なので、それぞれのに対してから以上4つの場合の数を引けば答えが出る。 については、のときにだけを引けばよい。 については、からそれぞれ個を…
自己紹介 先日AtCoder黄色になりました、shinchan(@Sophia_maki)です。最近そふぃあとも名乗り始めました。 目次 自己紹介 予選 Qual A Qual B 東京行き 準備とか 前々日 前日 当日 本番まで 本番 イベント 大宴会 翌日 今後 予選 Qual A 「ふぁ！？3/18？？？TOEIC前日やんけ！前日なら大丈夫やな！うん！」 といいながらレジりました。3完でした(カス)。 Qual B 5完でした。イベント通過は確信しました。 決勝逆ボーダーだとわかり発狂しました。 後日、繰り上がりメールが来ました。2/27にメールが来たのですが、2/28にメールが来た人に…
qiita.com
note.com
engineer-lab.findy-code.io
qiita.com
www.slideshare.net
qiita.com
chokudai.hatenablog.com
qiita.com
qiita.com
