競プロでやりがちなミス集

自分がよくやりがちなミスをまとめてみました。 このようにまとめておくことで、 よくやるミスをやらかさないよう注意深くなる 解法は合っているはずなのに何故かWAする、といった場合に疑うべき場所が明確になる という効果を期待しています。D言語特有の仕…

No.752 mod数列

No.752 mod数列 - yukicoder 問題 数列 が与えられる。個のクエリに対して を求めよ。 制約 解法 まずおなじみの累積和テクニックの考え方からが成り立つので、任意のに対してを求めるにはどうすればよいか?を考えることにします。ここで程度までであれば単…

C - Modulo Summation / ABC103

問題 を求めよ。https://beta.atcoder.jp/contests/abc103/tasks/abc103_c 解法 まず任意のについて、であることから、の上限はであることはすぐに分かります。そして、サンプルなどを見ているとmを上手くとればをこの上限に一致させることが出来るのではな…

Pythonで競プロを始めるという選択肢

久しぶりにブログを更新します。今回は解説記事ではなく自分語り系の記事です。twitterを見ていたら「pythonで競プロをやるってどうなの?」みたいな話が出ていたので、私も元python競プロerとして考えを述べてみたいと思います。(もともとこのブログのタイ…

A - Uncommon/みんプロ2018本戦

問題概要 集合が与えられる。 各整数k = 1, 2, ..., Mについて、kと互いに素であるAの要素の個数を求めよ。 制約 解法 愚直にやると少なくともO(N*M)かかってしまうのでまとめて数え上げるなどの高速化が必要になります。kを固定したときに、kとa_iが互いに…

B - だんだん強く

https://beta.atcoder.jp/contests/dwacon2018-final-open/tasks/dwacon2018_final_bニコ生の公式解説でちらっと触れていた解法が凄くスマートだったので復習を兼ねて書いておきます。 解法 与えられた[v_1, v_2, ..., v_n]を(K+1)倍に拡張した次のような配…

No.643 Two Operations No.2

No.643 Two Operations No.2 - yukicoder 考察 xとyの比を取って、p = x/yと置くとx=yにするということはp=1にするということと同値であることが分かります。 (ただし、y=0のときはp=∞であると考えることにします。また(x, y) = (0, 0)は少し特殊なので無い…

No.642 Two Operations No.1

No.642 Two Operations No.1 - yukicoder 考察 とりあえず整数を頂点、操作を辺としてグラフにしてみると以下のような感じになります。頂点数はNで辺の数は2Nなので、N 最短距離(最小操作回数)が求められますが、今回はN 頂点iへの最短距離をdist(i)と書く…

ABC056/D - No Need

https://beta.atcoder.jp/contests/abc056/tasks/arc070_b 考察 要素の順番は関係無いので、考えやすくするためにとりあえずa_iは昇順ソートされているものだとします。まず、「カードiが必要であること」とはどういうことかと考えてみると、条件の否定を考…

競技プログラミング初めて1年経ちました

競技プログラミング(競プロ)を初めて1年くらい経ったので、1つの区切りとして競プロについて得られた知見や感想を書いておきます。 強くなる方法とか競プロお役立ちテクニックとかそういう話は一切書いてません。 パソコンのプロじゃなくても出来る 何か…

Educational Codeforces Round 26

久しぶりにブログを書きます。 4完でした。D問題のDPを通せたのは個人的になかなか成長したのではないかと思える回でした。 A. Text Volume 問題概要 いくつかの単語で構成される文が与えられる。 各単語の音量はその単語に含まれる大文字の数で決まり、そ…

Educational Codeforces Round 23

参加しました、3完でした。Cはもうちょっと早く解けたかったな、という感想ですがなかなか難しいものです。 Dは結構考えたんですが全然分からず、解説見て勉強になりました。典型問題らしいです。A.o B.o C.xoそういえば今回はpythonじゃなくて個人的に流行…

Codeforces Round #412 (rated, Div. 2, base on VK Cup 2017 Round 3)

参加しました。今回はあのtouristが作問ということだそうです。 touristは競プロが一番強い人ですね。こどふぉやAtcoderでも1位にいるので意識していなくても覚えてしまいます。結果はABCの3完でした。Cは割と解けてる人が少な目で、これを解けたのは嬉しか…

Codeforces Round #411 (Div. 2)

参加しました、結果は4完でした。 いつもと比べて割と出来がよかったですね、ただ全体的に良かったみたいですが。A.o B.o C.o D.o

GCJ Qual.2017 - B

GCJのRound1が全て終わりました。私はR1B, R1Cに参加しましたが、どちらも1000位以内には入れず、残念ながらここで敗退となりました。 来年まで競プロをやっていたら、次はR2に進出してみたいですね。それで今回はQualification RoundのB問題についての記事…

GCJ Qual.2017 - A

Google Code Jam Qualification Round 2017 に参加しました。 結果は A.Large, B.Large, C.Small2 まで通って50点でした。 予選は27時間とかなり長く、しかも25点以上取れれば予選通過だから時間に追われることなくゆっくり考えることができてよかったです。…

Codeforces Round #408 (Div. 2)

久しぶりのブログ更新です ほんとはyahooのみんプロとか、GCJとか、そういう優先度の高そうなものを投稿すべきかもしれませんがとりあえず昨日やったcodeforcesについて書きますA.o B.xo C.xhttp://codeforces.com/contest/796公式解説 http://codeforces.co…

RCO presents 日本橋ハーフマラソン 本戦の感想

参加しました。オンサイトコンテストに参加するのは初めてでした。 結果は28位と微妙なポジションでした。Aは10位となかなかよかったのですが、Bが自明解を超えられず43位とほぼビリだったのが痛かったです。 初のオンサイトコンテストということで緊張し、…

みんなのプロコン

参加しました、結果は3完でした 自分の実力からすると妥当なところだと思いますが、Cをミスすることなくしっかり通せたのは良かったと思いますA.o B.o C.o D.x「みんなのプロコン」 - 「みんなのプロコン」 | AtCoder

RCO presents 日本橋ハーフマラソン 予選

参加しました、結果からいうと予選通過で本選に出場することが決まりました オンサイトコンテストに出場することは初めてなのでとても嬉しいですA.783413 B.9605RCO presents 日本橋ハーフマラソン 予選 - RCO presents 日本橋ハーフマラソン 予選 | AtCoder

Codeforces Round #402 (Div. 2)

参加しました、3完でした 配点が 500 — 1000 — 1000 — 1500 — 2000 — 2500 だったので3完でもあまり良くないというか妥当な感じの成績ですね 今回は全体的に1問解くのに時間がかかりすぎたかなと思ってますA.o B.o C.xohttp://codeforces.com/contest/779…

Mujin Programming Challenge 2017

参加しました、Bの完全点のみでした 見学権が手に入る200位以内を目標にしていましたが、それは惜しくも届かずでしたMujin Programming Challenge 2017 - Mujin Programming Challenge 2017 | AtCoder

yukicoder contest 157

参加しました、結果は3完 あまり芳しくなかったですねA.o B.o C.o D.- E.x

Codeforces Round #401 (Div. 2)

参加しました、3完でした 私にしては良く出来た回だったかなと思いますA.o B.o C.xxohttp://codeforces.com/contest/777公式解説 Problem analysis of Codeforces Round #401 (Div. 2) - Codeforces

ICM Technex 2017 and Codeforces Round #400 (Div. 1 + Div. 2, combined)

2完でした、C,Dは取り組んではみたものの解けませんでしたA.o B.o C.- D.-http://codeforces.com/contest/776 公式解説 ICM Technex 2017 and Codeforces Round #400 (Div. 1 + Div. 2, combined) Editorial - Codeforces

Divide by Zero 2017 and Codeforces Round #399 (Div. 1 + Div. 2, combined)

参加しました、結果は2完 http://codeforces.com/contest/768A.o B.o C.xBがいつもより難しかった気がします 公式解説 Editorial Divide by Zero and Codeforces Round #399 (Div. 1+2, combined) - Codeforces

Chokudai Contest 003

参加しました。普段の競技プログラミングとはちょっと違う形式でマラソンという種目らしいです。 (恐らく)最適解が誰にも分からない状況でいかにして最適解に近づけていくか、ということを競う種目って感じでしょうか。 実験的なコンテストらしいのでレー…

AtCoder Regular Contest 069

参加しました、2完でした。 結果自体は決して悪くないのですが、いろいろミスしたり何なりでいまいちかも。C.o D.o今回もコードとちょっとしたコメントだけ。

Codeforces Round #398 (Div. 2)

参加しました、結果は1完でした とにかくBがとても難しかったというか複雑だったというか。 どっかで見切りをつけて次の問題を見てみるべきだったかも、とも思いました。 Aもいつものレベルに比べて難しく、2回もWAしてしまった。問題を正しく理解できてな…

Codeforces Round #397 by Kaspersky Lab and Barcelona Bootcamp (Div. 1 + Div. 2 combined)

参加しました、4完でした codeforcesで4完できたのは初めてでした いつもより長く3時間あったから、というのもありますがちょっと嬉しかったですA.o B.o C.x(hacked)o D.o E.xxhttp://codeforces.com/contest/765公式解説 Codeforces Round #397 Editoria…