100-200-300(1)-400-500-0で1ペナ5完1500点。 A - Brick 割り算の問題で、の商が答えとなる。余りは切り捨ててよい。計算量は、。 B - Blocks on Grid ブロックに対してできる操作は、「ブロックを取り除く」のみである。この操作でブロックの個数が増えるこ…

※この記事は苫小牧高専アドベントカレンダー2020 10日目の記事です。adventar.org9日目の記事はまだ上がっていないようです。高専という感じがして好きですよ。 というわけで10日目はみみねこが担当します。Twitterをやっているので是非フォローしてください…

300-400-500-0(2)-0-0でノーペナ3完1200点。 A - Hands この問題の構造は、各階→頂点、廊下・階段→辺として重み付きグラフに落とし込める。このグラフの2頂点間の最短路問題を解けばよい。例えば、ダイクストラ法で実装すれば頂点数、辺数より計算量はとなる…

100-200-300-0-0(1)-600(1)で1ペナ4完1200点。 A - Determinant 行列は丸括弧で与えないとダメなんじゃないの？と思いつつ解いた。ちなみに丸括弧にはいろいろな意味があるので、紛らわしさをなくすために行列は角括弧で表すことがあるらしい。ためになった…

300(1)-400-500-0-0-0で1ペナ3完1200点。 A - Sum and Product を満たす正整数の組は個あり、これらの組全てに対してかどうか判定すると、計算量で解ける。しかし今回は制約がと厳しいので、もっと効率の良い解法が必要となる。を満たす正整数の組はの約数の…

ABCに出るのは久々でした。100-200-300-400-500-0(2)で0ペナ5完1500点。 A - ReLU 問題文の通りの値を返す関数を実装する。入力された値によって出力される値が異なるので、条件分岐を用いて書けばよい。計算量は、。 B - Billiards 入試数学とかでよく見る…

略称はABLらしい。明日から使えるムダ知識をあなたに100-200-300(1)-0-0-0で1ペナ3完600点。 A - Repeat ACL ACLという文字列を回だけ出力する。は5パターンしかないのでif文を用いて5通りの分岐を記述すると解ける。また、ループを用いると問題文の処理をそ…

※AtCoderとACLを非難する記事ではありません。 実力もないのに数学力だけで水色に這い上がって生きてきた僕は今回のABLで茶パフォを出しました。原因はACLに含まれているものを中心としたデータ構造の性質の理解と、その応用例に関する知識不足です。つまり…

「愚直にやると遅いから高速化する！」の考えは大事。100-200(1)-300-400-500-0で1ペナ5完1500点。 A - Plural Form 文字列を複数形に変換する。文字列の末尾がsかそうでないかで処理が変わる。具体的な処理の流れとしては、入出力を除くと「文字列の末尾の…

具合が悪いのでさらっと書きます100-200-0-400-0(3)-0でノーペナ3完700点。 A - Not 1なら0を、0なら1を出力する。if文で実装できるし、排他的論理和でエレガントに書くこともできる。 B - Product Max 全通り試すと間に合わない。（B問題にしては厳しいね？…

100-200-300-400-500(1)-0で1ペナ5完1500点。 A - Don't be late 先週も同じような問題文見たな...（既視感）2つの解法を紹介する。どちらも、「問題文で与えられたすべての変数を同時に見ない」のが特徴的。解法1：分後の待ち合わせ時刻に間に合うためには…

100-200-300-400(2)-500-0で2ペナ5完1500点。 A - Takoyaki 分間に個のたこ焼きを作れるので、実際に1分ずつシュミレーションしていけばよい。現在焼いたたこ焼きの個数を変数で管理して、分経つごとに個増やしていき、初めて個を超えた時の時間を出力する。…

100-200-300-400-500-0で0ペナ5完1500点。 A - Air Conditioner が以上かどうかで条件分岐したいので、if文を用いて実装する。計算量は。 B - Distance 個ある点それぞれについて、「原点からの距離が以下か？」という質問に答える。原点からの距離が以下で…

100-200-300-400-0-0 で4完1000点。早解きで良いパフォが付いてもあまりうれしくない。 A A - Kyu in AtCoder if文で条件分岐を書いてもいいが、8通りもの分岐を手打ちするのは面倒だし時間がかかる。ここで、レーティングが200変わるごとに級が1減るという…

（タイトル間違ってたのを修正。ABCではない。） NoSub。Cから解くと決めていて、Cが解けなかった。 A atcoder.jp 以上以下の範囲にある整数のうち、の倍数であるようなものの個数はで求められる。累積和的な考えを使うと、答えはである。 また、普通にルー…

100(1)-200-300-400-500(2)-600で3ペナ全完2100点、時間はペナルティ込みで98:33。 A atcoder.jp A問題を舐めていて、n%1000を出力してWA。サンプルの重要性を知る。 1000円ずつ払うと考えて、実際にループを使って1000円ずつ引いていった。こういう処理は割…

Twitterに垂れ流すと遡るのが大変なのでブログに書くことにした100-200-300-0(1)-0-0 で3完600点。All Submissions - AtCoder Beginner Contest 172 A atcoder.jp 式をそのまま書く。足し算よりかけ算の方が優先順位が高いのでa + a*a + a*a*aみたいに愚直に…

わがままをかなえるシリーズ以下、競プロでの使用を想定しています。 C++をベースに書いていますが、データ構造についての話なので他の言語でも通用すると思います。 priority_queueで出来ること priority_queueは、その名の通り優先順位付きキューで、追加…

オンライン授業ってリアルタイムで出席する必要ある？(愚痴) 事の発端 以下は競プロの話である。.clang_formatによる自動フォーマットの設定を弄っていて、 AllowShortFunctionsOnASingleLine: All とかの設定をすることで、短い関数をそのまま改行せず1行で…

2020/05/10 17:57 追記：shuffleがshufflになっていたのを訂正 シャッフルアルゴリズムとしてはかなり有名な部類だそう。Fisher-Yatesってなんて読むんだろう。 設定、目標、制約等 長さの順列をランダムに並び変えたい。効率の良い方法を見つける。 ただし…

競技プログラミングでdfsとかする時に、配列をグローバルで宣言すれば引数にいちいち含めなくても良くなるので楽だと思った。しかし、グローバルで宣言したvectorは要素数(長さ)をあらかじめ決めておく必要があるっぽい。困った 要求 以下のように入力が与え…