izumo’s diary

主に競プロの精進記録

CODE THANKS FESTIVAL 2018(Parallel)

競プロ

残念ながらCODE FESTIVALの本戦には参加できなかったのでオープンコンテストに参加しました。300点以下しか解けずA, B, C, Dの4完でした。

使用言語: C++

A - Two Problems

問題

配点が B \leq D なので1, 2問目を解く場合、2問目を解く場合、1問目を解く場合について時間内に解き終わるか調べる。

続きを読む

AtCoder Beginner Contest 112

競プロ

水色として臨む初めてのABCでした。unratedなので気楽にできると思っていたら気楽にしすぎて大量にWAをくらいました（苦笑）。結果はA, B, Dの3完でした。

使用言語: C++

A - Programming Education

問題
Nで場合分けして出力。入力もNによって変わることに注意する。

続きを読む

AtCoderで水色になりました

競プロ

先日のABC109にて水色になることができたので、競プロを始めてから今までしてきたことについて記憶を頼りに書いていきます。個人差が大きいのでこんな人もいるんだな程度に読んでもらえればと思います。

続きを読む

AtCoder Beginner Contest 103

競プロ

最近忙しくてブログを書くのはおよそ二か月ぶりになります。一か月ほど前のABC100にて緑になりました。Yay!

f:id:izumo27:20180722124852p:plain

今回はABC103の参加記です。結果はA, B, C, Dの全完で青パフォでした。
使用言語: C++

続きを読む

二項係数 (nCr) の計算方法

アルゴリズム 競プロ

AtCoder Grand Contest 025 にて _n \mathrm{C} _r\ \bmod\ p を使う問題が出題されました。いい機会だと思ったので i!,\ \left(i!\right)^{-1},\ _n \mathrm{C} _r\ \bmod\ p の高速な実装をしてみました。

使用言語: C++

1. なぜ逆元 \left(i!\right)^{-1} が必要なのか

_n \mathrm{C} _r=\frac{n!}{r!\times(n-r)!}
なので、n!,\ r!,\ (n-r)! が分かればO(1) で _n \mathrm{C} _r が求まります。よって事前に階乗を計算しておけばよいことが分かります。

続きを読む

AtCoder Beginner Contest 098

競プロ

だいぶ間が空きましたが今回はABC098の参加記です。結果はA, B, Cの3完で緑パフォでした。ちなみに前回のAGCはno-submissionで逃げました。（は？）
使用言語: C++

A - Add Sub Mul

問題

A-B, A\times{B}の大きい方とA+Bを比較すれば3つの中で最大のものが分かる。

続きを読む