前回示した解法（貪欲法）の証明をしたいと思う。 解法のポイントは、箱の方は小さい方から埋めていき、ブロックは大きい方から使っていくという点である。 箱を小さい方から埋めるのは、大きい箱を埋めるのに小さいブロックを先に使ってしまって後で困らな…
問題概要 n2個の数が与えられる。 それらの数をちょうど一度ずつ使って、上下左右に対称な正方行列を作れるか判定し、作れるならばそのような行列を出力せよ。 いろはすの解法 まず、行列が作れるとして、そのような行列では同じ数がいくつずつ必要なのかを…
今日の一句 桁DP 000に 気をつけろ 問題： C - 755 （解説） 上記の問題を桁DPで解こうとしたら、探している数値の桁数が上限値のより少ないパターン（N=3600に対する735とか）を見落としていた。気をつけよう。
今日も元気に反省しよう!! ということで、今回の反省会は昨日のCodeforces Global Round1についてである。 結果は2完で、A,B問題を最初の40分ぐらいで解いたのだが、その後C問題に残り全ての時間を費やしても全く解けなかった。 なので、今回のテーマはそのC…
先日、こんな記事を書いた。 拡張ユークリッドの互除法を自己流で実装してみた。 - いろはすの競プロ反省会 これだけではあまりに不親切なので、ここに書いたコードの解説をしていこうと思う。 ※上の記事に書いたコードは自己流で書いたものなので、蟻本に載…
今日の反省。 最近、問題の意味を勘違いして時間溶かすパターンが多い気がする。 表題に上げたこの問題（ABC 089: C – March）がその最たる例である。 この問題文を読んで、いろはすはこう考えた。 まず、重要なのは'M','A','R','C','H'それぞれの文字を頭文…
蟻本のやつがあまりに難しくて理解できなかったのと、何か使いにくそうだったので自分で実装してみた。 こっちのほうが素直で分かりやすいと思う。 #include<cstdio> #include<bits/stdc++.h> using namespace std; typedef pair<int,int> P; //solution of xa+yb=gcd(a,b) P extgcd(int a, i</int,int></bits/stdc++.h></cstdio>…
与えられたテストケース群についての、２つのプログラムの出力が同じかどうかをチェックするシェルスクリプトを書きました。 パラメータの値が小さいところで愚直解と一致するかどうか調べたいときなどに有用です。 出力が違った場合、そのときの入力と、２…
結論から言えば、自分の中ではかなり力が出せたコンテストだったと思う。 少し手間取ったところもあったがA~Cまではほぼ順調にACし、残り５０分強を残してD問題に進むことが出来た。 時間としてはかなりあったが、やはり今の自分の実力では最後のD問題を通す…
今日の反省はこの問題。 https://atcoder.jp/contests/abc075/tasks/abc075_c まあ色々反省点はあるのだが、一番大きな反省点は時間だろう。 解くのに１時間１７分もかかってしまった。ABC-C問題にこれは掛かりすぎだろう。 何故こんなに掛かってしまったか…
今月の進捗
ABC 049 D 連結が解けたのが嬉しかったので解説してみた(ちなみに43分かかった)。 Union-Find木を使う問題である。 タイトルからして、「ああ、グラフの連結成分求める問題か。Union-Find使えば楽勝じゃん」とか思って取り掛かった。 ・・・・・・甘かった。…
蟻本を読みながらけんちょんさんの記事に載っている問題を毎日解いているが、LISの項でこの問題が分からず、やむを得ず他の人の解答を見たときに学んだことが多かったのでメモ。 ・upper_boundではなくlower_boundを使う ・答えの探し方(lower_bound使う) ・…
蟻本を読んでいたら、クラスカル法の正当性の証明が省略されていたので、自分で証明を構築してみた。 誰かの役に立つといいな。 ちなみにTeXで書く元気はなかった。汚くてごめんなさい。 クラスカル法の正当性の証明 連結な無向グラフG上のクラスカル法を考…
何番煎じか分からないけどやってみた。 （蟻本だとクラスや構造体にまとめてなくてとっ散らかってたため） #include<bits/stdc++.h> using namespace std; struct union_find{ vector<int> par; vector<int> rank; union_find(int n){ rank = vector<int>(n,0); for(int i=0; i</int></int></int></bits/stdc++.h>
