競技プログラミング

AtCoder Beginner Contest 139 A,B,C,D 反省会

提出一覧へのリンク やっと緑色になれました 今回の ABC139 でようやく緑色になれました。D までは 20 分くらいで (WA しつつも) ぽんぽん進めた一方、E はグラフっぽさを感じつつも貪欲で TLE を抜けられなかったので、現時点では、知識が備わってきたので…

第一回日本最強プログラマー学生選手権-予選- A,B 反省会

提出へのリンク 実際に時間内に提出したのは A だけでした。 A は全部調べれば良いです。 B は途中までは色々工夫して調べていましたが、高々 2000 個の数列なので 数列内での転倒数と、 数列を 2 組並べたときの、後ろの数列から見た前の数列に対する転倒数…

AtCoder Beginner Contest 119 A - Still TBD

問題へのリンク 解説で学びがあった。 2019/04/30 というような、数字の桁数とセパレータまでフォーマットが決まっているような文字列が入力される場合には、セパレータを char で受けることで stoi などの関数を使わなくても数字部分を直接 int などで受け…

CODE FESTIVAL 2017 Final A - AKIBA

提出へのリンク A を挿入すべき位置を予め調べて決め打ちして挿入し、最終的にできた文字列が AKIHABARA と一致するか見るコードにした。 余り綺麗ではなく、実際解説を読むと AKIHABARA から A を抜いた文字列を全列挙してどれかと一致するか見ればよい。こ…

AtCoder Beginner Contest 106 D - AtCoder Express 2

提出へのリンク セグメント木でやろうとして90分くらい使ったらもう眠いしわからんしで解説読んだらシンプルな累積和でよかった。就寝。 歯を磨いてたら解説の図が頭の中でどうも引っかかって、正方形ではなくてその左上半分ではないかという気がする。L_i <…

AtCoder Beginner Contest 073 D - joisino's travel

提出へのリンク 全頂点が最大200個なのでワーシャルフロイド法を使うことができる。立ち寄る頂点の順番についても最大8個なので next_permutation が使える。便利〜〜〜〜。 ハイライト warshall_floyd(); int ans = LINF; do { int tmp = 0; REP(i,R-1) tmp…

AtCoder Beginner Contest 082 B - Two Anagrams

提出へのリンク string s,t; cin >> s >> t; sort(ALL(s)); sort(ALL(t),greater<char>()); if (s</char>

ABC137 A,B,C,D 反省会 -- priority_queue と料理

提出一覧へのリンク A: max 2 回やったけど initializer-list 使えば解説のとおり 1 回で済むね B: i < -1000000 || i > 1000000 だったら除外しなきゃとかやったんだけどいま制約条件みたら 0 <= X <= 100 だったわ C: 最初は sort して multiset<string> に放り込</string>…

ABC131-E スター/ウニというグラフ

提出へのリンク 1からそれ以外への頂点すべてに辺を生やしたグラフをスターやウニというらしい。考えた人頭いいな。ウニは頂点間距離の調節がしやすくて応用が効きそう。 構成可能かどうかの判定は、連結でなければいけないという条件から、ありえる頂点対の…

ABC136 A,B,C,D 反省会

提出へのリンク やったねACだよ A: #define int long long してたので max(c - (a - b), 0LL) のようにリテラルつける必要があった B: 桁数えるのに手間取っちゃって to_string(i).length() % 2 != 0 で全探索した C: for 文手書きすると i が N になってた…

ABC131-D ソートを考慮した vector<pair<int,int>> を作る

提出へのリンク 締切が遠いものから着手して他の締切をブッチしてしまってはしょうがないので、締切が近いものから手を付ける。 vector<pair<締切,所要時間>> を作り、素直に std::sort する(ABC128-Bでもやったように)。 締切が同じタスクがあれば、同じタスク同士ではどうい</pair<締切,所要時間>…

ABC135-D DP 精進しよう / stack の大きさ

提出へのリンク 30分ほど考えてもTLEしない方針すら立たなかったため、解説を読んだ。が、眠い頭ではなかなかわからなかったのでとりあえず写経し、8ケースでバグったので最速正解者のコードに合わせて修正したら通った。 解法は動的計画法で、文字列を左か…

ABC135-C

問題へのリンク 前から食っていけばいいのでは?と実装したらWA。 じゃあ後ろから食っていけばいいのでは?と実装したらWA。 解説読んでも前から食えとしか書いていない。 long long にしたら通った。109 を 3 回足すだけで int からあふれてしまうので、そ…

ABC135-AB

ABC135 へのリンク A: 相異なる整数同士の和が偶数(解説では偶奇が等しい)ならば、整数それぞれからある同じ整数を引いた絶対値が等しくなる B: std::vector は erase とかするとインデックスがずれて面倒なことになるから素直に v[i] で代入したほうがい…

ABC117 C問題 反省会

Streamline これです。簡単なはずなんだけど解けなかったので反省がてら図解します。 問題設定 数直線上にM個のターゲット座標がある 上図のように、数直線上に M 個の座標があって、それらを N 個のコマですべて訪れたい。はじめにコマを置くのは手数に入れ…