AtCoder

皆さんARC117お疲れ様でした！！ いつも通り？２完速解きコンテストでしたね...自分のコンテスト結果はこんな感じです！！ ARC117-B のコンテスト結果昨日の色変と言い、今日のコンテストと言い速解きでパフォが出てしまっているので今後が怖いです！！！そんな中で、今日はタイトルにもある通り、B問題のエスパーの仕方を紹介したいと思います！！目次はこちら！！ 問題 エスパーの仕方 1. set 取れますやん 2. sort 出来ちゃうんですよねーー 3. デカイ数字はとりま素因数分解！！！ 4. 何が足りない！？ 5. 160って何者？？？ Pythonコード 最後に こんな記事書いたら炎上し…

問題 atcoder.jp 解き方 木構造で何かしらの最大を求める問題は木dpっぽさを感じたので、この方針で突っ込んだ。 自分の子が持つべき情報は、何冊もらった時にどれだけのやる気を得ることができるかのテーブル。 この情報があれば、普通のdpの遷移と同じようにやれる。 つまり、 dp[v][i] := vを根とする部分木に i 冊配った時のやる気の総和の最大値 と定義する。 dp[v].size() = m として全頂点でdpをすると、遷移的にO(NM^2)になって間に合わないので、二乗の木dpというテクニックを使って高速化。 これは 木と計算量 前編 〜O(N^2)とO(NK)の木DP〜 -…

問題はこちら 問題概要 解説 提出プログラム 感想 問題概要 を満たす整数の組全てについて の総和を求めよ．解説 形式的冪級数で解きます．とすると よってとしてが答え．を偶奇で分けると したがってBostan–Moriのアルゴリズムを用いたり，線形漸化式に直して行列累乗したりするとライブラリとか除くと実装はこれだけ int main() { int t;cin >> t; while(t--) { ll n;cin >> n; FormalPowerSeries<MOD,true> f({1}); for (int i = 0; i < 16; i++) f *= {1,-1}; for (i…

第二回日本最強プログラマー学生選手権(jsc2021) のC問題を解説しつつ、 恥ずかしいミスをしてしまったので、自戒をこめてここに残しておきます。atcoder.jp 問題の概要 AとBが与えられて、となるxとyの最大公約数の最大値を求める問題です。 なので、AからBの範囲で全ての組み合わせでgcdを求めようとすると、 組み合わせを考えようとした段階で計算量は億を簡単に超えるのでアウトです。 考え方 発想を転換して、答えとなる最大公約数をCと固定して、これがAからBの範囲で2つの数で割り切れればOKとします。 サラリと書いてますけど、ここに至るのにけっこう時間がかかったのも反省。。。最大公約…

ABC100 B問題 Ringo's Favorite Numbers のズルい解き方を解説します。atcoder.jpDとNが与えられて、100 で ちょうど D 回割りきれる正の整数のうち、N番目に小さい数を求める問題です。 Dは0か1か2、Nはの整数です。 サンプルを見ていくと式が浮かびました。 の時、100で割り切れない数は1, 2, 3, 4, 5, 6となっていて、5番目に小さい数は5。 の時、100で1回割り切れる数は100, 200, 300, 400, 500, なので11番目に小さい数は1100。 なので答えはということが推測できます。 ただし、気をつけないといけないのはの…

昨日の続きということで、今日はEとF問題。これらは完全にアルゴリズムを思いつかず解けなかった。どういう発想が必要だったのか考察してみる。 E - Traveler 「同じ色のボールをどういう順番でとるかがカギだな」「各色について、取り方は高々2通りしかないな」というところまでは至ったものの、そこで行き詰ってしまった。 この問題の場合、i色目までを取った段階で考えられる状態は2通りしかないので、その2通りについてi色目までを取り終える最短時間を帰納的に求めることでO(N)時間で解が求まるのだが、「各色について2通り→全部で通り」という考え方をしてしまったので、そこで行き詰ってしまった。要は「過去…

そもそも回転の列挙が難しい．以下，厳密性を欠くので注意．問題はこちら 問題概要 解説 提出プログラム 感想 問題概要正六面体のつの面に正整数を書き込んだとき，正整数の和がとなるような物の数を求めよ．ただし，正六面体を回転して一致する書き込み方は区別しない．解説 和がとなるようなものはまだしも，回転一致を区別しないのは難しそう．回転一致を除去した数え上げは蟻本とかに書いてあったように「ポリアの数え上げ定理」とか言うのを用いればよさそう．以下の資料がわかりやすかったので参考にしました．http://dopal.cs.uec.ac.jp/okamotoy/lect/2014/dme/lect07.p…

https://atcoder.jp/contests/agc007/submissions/21896735 の公式が成り立つ理由 結論から言うと が答えになる。 に比べて の制約が非常に緩いことから、ある程度の余裕を持たせて昇順数列 a を考えたほうが良いのかな、という気持ちになる。 公式のように例えば M=30000 の等差で昇順・降順の a と b を作って加算してみると全ての合計が同じになる。ここで a に の だけ順番に加算していくと元々全ての合計が同じだったため の合計が p の順番になってくれる。このとき M が N に比べて十分に大きければ a の昇順が崩れることもない。 感…

前書き AtCoder Beginner Contest 116・118・122・123 A・B問題を解きました。 A問題 難易度：灰 時間：3分 atcoder.jp A,B,C=map(int,input().split()) print(int(A*B/2)) B問題 難易度：灰 時間：25分 atcoder.jpまず問題を正しく理解するのに8分ほどかかってしまったので反省。 奇数→ 3*A+1、偶数→ A / 2の計算をしながら、Aは変化します。 1度代入された値に再度代入されるに、ループを終了します。Am = An (m > n) となった時 => 1度代入された値に再度代入されるA…

今日のコミット。 rust-atcoder 1 commit abc019 a, b, c, d ABC019 D 問題自体は簡単なのになぜか入出力が動かなくて WA 水まわりのトラブルでバタバタしている。

本日二つ目の投稿。二つやると結構大変だけど昨日忘れた自分が悪いですねはい() 一言で言えばこんな記事を見つけましたと言う話。 qiita.com 初級編〜上級編とあるが、現在茶コーダーで水を目指す自分として役に立ちそうなのはこれ。具体的に何をやったら良いか、どのくらいのレベルになれば水色になれるかが非常に具体的に書いてあり、今後の方針が立てやすい。 いくつか読んでわかったことを↓ ここに書いてある水色になるために抑えるべきSTLの機能、アルゴリズムは9割方習得したものである。ということはそれらを運用する力がまだまだ足りていないということ。恐らくここから水色までは、新たなアルゴリズムを学ぶよりは…

昨日書き忘れましたねはい。ので今日二日分書きます。 まずは先日の最強学生プログラマー選手権(だっけ？)のE,F問題を軽く振り返って。まずF問題は座標圧縮が必要になってきそうなので明日学習しようと思う。ちょうど良さげな問題も見つけた。 atcoder.jp んで問題のE。解説読んだ時からこりゃ実装がえらい難しそうだな…と思ったのだが、案の定自力での実装は難しかったので、解説のところにあった解答コードを読み解いて学習することにした。確か黄レベルだったと思うから今の段階で自力で解ける必要も必ずしもないと思っているし(まずは水レベル以下を確実に解けるようにしたい)。 そこでいくつか気づいたことを↓ 問…

kenkoooo.hatenablog.com kenkoooo.hatenablog.com kenkoooo.hatenablog.com kenkoooo.hatenablog.com kenkoooo.hatenablog.com kenkoooo.hatenablog.com仕事と家さがしばかりで終わってしまった。来週はそれ以外を頑張りたい。 AtCoder AC数: 1565->1576 (+11) 橙diff: 73->74 (+1) 黄diff: 148->151 (+3) Project Euler 109 英語 無 睡眠

こんにちは。 水色になった露草です。正直、始めた当初の目標だったので嬉しい！ 「露草」という名前も、水色の一つで、twitterを開設した時の意気込みが反映さています（2020年内到達が目標だったので、4ヶ月ほど遅れたのは目を瞑りましょう） さて、今回の記事はサイレントアップロードです。あまりにも侵襲性が高い内容であるので大々的に執筆したことは言わないでおこうと思います。 思い悩んだ未来の自分が、自分のプログを開いた時のためのメッセージ的なものを精神的に余裕がある時期に書き連ねたものです。なので、自己満足的・本来発信すべき内容なのかもわからない内容、口調になっているのはご容赦ください。ただ、誰…

みなさんこんにちは．お久しぶりです． 競プロ er の中では，よくインドという風な呼ばれ方をすることで有名な？CodeChef について説明していこうと思います． CodeChef は AtCoder と同様有志コンテストと公式の rated コンテストが分かれています． 主に，公式の rated コンテストについて説明していこうと思います． 公式コンテストは現在主に毎月 4 回行われており， Starters Challenge Cook-off Lunchtime があります．これに加えて，数回 rated が加わる月もあります． よく，インドはカスだという印象があるかもしれませんが，公式…

記事名の「でんか」は僕の出身地である、香川県の方言(「さぬき弁」という)です。それも結構強めのさぬき弁です。 ざっくり言うと、東京での「じゃん」、関西での「やん」にあたります。 (東京)さっき食べてたじゃん (関西)さっき食べてたやん (香川)さっき食べとったでん という感じです。 これを話したら「おでんくんみたい」と言われたことがあります。おでんくんみたいではなくない？ さて、AtCoderのルールのページを見ると、言語に"Racket"が追加されていました。

AtCoder Regular Contest 117で黄パフォ!! A - God Sequence (200点) B - ARC Wrecker (400点) C - Tricolor Pyramid (600点) D - Miracle Tree (600点): 未提出 E - Zero-Sum Ranges 2 (900点、実行時間制限: 5 sec): 未提出 F - Gateau (900点、実行時間制限: 3 sec): 未提出 結果、感想 A - God Sequence (200点) のとき とすれば条件を満たします。 のとき とすれば条件を満たします。 のとき正負の役割を入…