2019-03-01から1ヶ月間の記事一覧
基本的にやることはICPC 国内予選2007D 崖登り AOJ1150 - intさわだんのBlack Historyとおんなじ 幅優先探索でゴリ押す #include <bits/stdc++.h> #include <map> #define chmin(a, b) ((a)=min((a), (b))) #define chmax(a, b) ((a)=max((a), (b))) #define fs first #define sc</map></bits/stdc++.h>…
解法:幅優先探索。右足でたどり着いたときの最小時間と左足の時の最小時間を分けて考える。この手の問題は得意なので秒で通した。(実際は分で通した。tupleとqueueのコンボが最強であることを知った。(自分が現役だったころはtupleなかった気がする。最近…
解法:深さ優先探索でゴリ押す 特に難しいところはない。計算量も気にしない。 #include <bits/stdc++.h> #include <map> #define chmin(a, b) ((a)=min((a), (b))) #define chmax(a, b) ((a)=max((a), (b))) #define fs first #define sc second #define eb emplace_back using </map></bits/stdc++.h>…
解法:Union-Findでそれぞれのcell同士つながってるかをわかるようにし、つながってないcall間で必要なcorridorの長さの最小値を求めそのcorridorを採用する。という処理をすべてのcellがつながるまで繰り返す。小数の扱いが闇だった。printf使えば小数点以…
やるだけ。解法はICPC 国内予選2015C ICPC 計算機 AOJ1602 - intさわだんのBlack Historyと完全に同じ #include <bits/stdc++.h> #include <map> #define chmin(a, b) ((a)=min((a), (b))) #define chmax(a, b) ((a)=max((a), (b))) #define fs first #define sc second #define </map></bits/stdc++.h>…
初心者なので幾何の問題に慣れてなくて焦ったけどかなりすんなりできた。解説一応しますが説明がすこし面倒なのと解説が必要なほど難しい問題ではないと思うのでかなり簡潔にします 建物のx座標の値はありがたいことに整数なので(これが小数だと面倒)x座標…
いわれたとおりにやるだけ。特に難しいことはない。 最後priority_queueを使えば楽に答えを求められる。(まあソートでもいいけど) #include <bits/stdc++.h> #include <map> #define chmin(a, b) ((a)=min((a), (b))) #define chmax(a, b) ((a)=max((a), (b))) #define fs firs</map></bits/stdc++.h>…
シミュレーションやるだけ. (ドット)の多いところから計算すればよい #include <bits/stdc++.h> #include <map> #define chmin(a, b) ((a)=min((a), (b))) #define chmax(a, b) ((a)=max((a), (b))) #define fs first #define sc second #define eb emplace_back using namespa</map></bits/stdc++.h>…
イキってDPで解いたら実装重くて痛い目にあった 集中してやったのでバグは起きなかった。dp[i][j][0] : 場所i,jをスタート地点にした時の数字の桁の最大数 dp[i][j][1~] : 最大の時の数字の列これを i = h-1, j = w-1 (一番右下のブロック)から i=0,j=0 …
解法: 探すもととなる折れ線を方向を変えた8パターンに分けて保存しておく(for文一つで実装できるがめんどくさかったためfor文8個使って泥臭く解いた) あとはその8パターンのうち一つでも一致するパターンがあるか地道に確認するだけ。 #include <bits/stdc++.h> #define</bits/stdc++.h>…
かなり初歩的なDPやるだけ。 #include <bits/stdc++.h> #define chmin(a, b) ((a)=min((a), (b))) #define chmax(a, b) ((a)=max((a), (b))) #define fs first #define sc second #define eb emplace_back using namespace std; typedef long long ll; typedef pair<int, int> P; type</int,></bits/stdc++.h>…
シミュレーションやるだけ。折るたびに原点の座標を更新していけばよい。実装も重くないので楽。 #include <bits/stdc++.h> #define chmin(a, b) ((a)=min((a), (b))) #define chmax(a, b) ((a)=max((a), (b))) #define fs first #define sc second #define eb emplace_back</bits/stdc++.h>…
やるだけ。シミュレーション。実装もそこまで重くなかった。 #include <bits/stdc++.h> #define chmin(a, b) ((a)=min((a), (b))) #define chmax(a, b) ((a)=max((a), (b))) #define fs first #define sc second #define eb emplace_back using namespace std; typedef long</bits/stdc++.h>…
解法:しゃくとり法(?)(しゃくとりほうがどんなものなのかはっきり覚えてないけどたしかそう #include <bits/stdc++.h> #include <map> #define chmin(a, b) ((a)=min((a), (b))) #define chmax(a, b) ((a)=max((a), (b))) #define fs first #define sc second #define eb em</map></bits/stdc++.h>…
やるだけ。簡単すぎる。難易度100の実装重めのやつのほうが明らかにめんどい(個人差 #include <bits/stdc++.h> #define chmin(a, b) ((a)=min((a), (b))) #define chmax(a, b) ((a)=max((a), (b))) #define fs first #define sc second #define eb emplace_back using name</bits/stdc++.h>…
こういうただ実装するだけの問題あまり好きではない。 vectorをつかってステップごとに要素の番号が+5されるようにした(vectorの途中の要素を消すのが無限にバグりそうだったため #include <bits/stdc++.h> #define chmin(a, b) ((a)=min((a), (b))) #define chmax(a, b) (</bits/stdc++.h>…
解法:いわれた通りやるだけ。シミュレーション vector<P>を使って生徒ごとの使用時間を記録しておくと楽場合分けは以下のとおりやった #include <bits/stdc++.h> #define chmin(a, b) ((a)=min((a), (b))) #define chmax(a, b) ((a)=max((a), (b))) #define fs first #de</bits/stdc++.h>…
解法:月曜土曜素数でエラトステネスをやる。 問題文の日本語を読解するのがvery hard。そのほかはeasy。 #include <bits/stdc++.h> #include <map> #define chmin(a, b) ((a)=min((a), (b))) #define chmax(a, b) ((a)=max((a), (b))) #define fs first #define sc second #defi</map></bits/stdc++.h>…
解法:幅優先探索やるだけ。 #include <bits/stdc++.h> #include <map> #define chmin(a, b) ((a)=min((a), (b))) #define chmax(a, b) ((a)=max((a), (b))) #define fs first #define sc second #define eb emplace_back using namespace std; typedef long long ll; typedef pa</map></bits/stdc++.h>…
やるだけmap<char,int>が使えれば楽なのだがやり方よくわからなかったので断念して配列でやった。(しかたなくmap<string,int>も試してみたが闇だった。 #include <bits/stdc++.h> #include <map> #define chmin(a, b) ((a)=min((a), (b))) #define chmax(a, b) ((a)=max((a)</map></bits/stdc++.h>…
エラトステネスやるだけようやく競プロの感覚取り戻してきてやるだけ問題は秒でできるようになってきた。 #include <bits/stdc++.h> #define chmin(a, b) ((a)=min((a), (b))) #define chmax(a, b) ((a)=max((a), (b))) #define fs first #define sc second #define eb empl</bits/stdc++.h>…
2014/10/3に下書きとして保存されていてなぜか公開されていなかったのでこのタイミングで公開する。たぶん全部解いてから公開しようとしていたんだと思う。同じ問題に二つの記事がある場合はpart2と書いています。 第6回日本情報オリンピック 本選 最大の和 …
シミュレーションやるだけ。setを使うと楽。 #include <bits/stdc++.h> #define chmin(a, b) ((a)=min((a), (b))) #define chmax(a, b) ((a)=max((a), (b))) #define fs first #define sc second #define eb emplace_back using namespace std; typedef long long ll; typed</bits/stdc++.h>…
やるだけ #include <bits/stdc++.h> #define chmin(a, b) ((a)=min((a), (b))) #define chmax(a, b) ((a)=max((a), (b))) #define fs first #define sc second #define eb emplace_back using namespace std; typedef long long ll; typedef pair<int, int> P; typedef tuple<int, int, int> T; const</int,></int,></bits/stdc++.h>…
解法:エラトステネス、累積和 やるだけ。難易度-5 #include <bits/stdc++.h> #define chmin(a, b) ((a)=min((a), (b))) #define chmax(a, b) ((a)=max((a), (b))) #define fs first #define sc second #define eb emplace_back using namespace std; typedef long long ll;</bits/stdc++.h>…
解法:やるだけ list使おうと思ったがイテレーターの動きがおかしくやめる→しかたなくbool配列を使ってlistっぽくする→最近のC++でgetsが使えなくなってて泣く→ググってgetlineを見つけてAC #include <bits/stdc++.h> #include <stdio.h> #define chmin(a, b) ((a)=min((a), (b))) #d</stdio.h></bits/stdc++.h>…
解法:幅優先探索やるだけ。 if(check[q.fs][q.sc] != 0) continue;を書き忘れてて無限にMLEくらってた #include <bits/stdc++.h> #define chmin(a, b) ((a)=min((a), (b))) #define chmax(a, b) ((a)=max((a), (b))) #define fs first #define sc second #define eb emplac</bits/stdc++.h>…
解法:幅優先探索やるだけ。queueの使い方を完全に忘れてて自分のブログを熟読して思い出した。 #include <bits/stdc++.h> #define chmin(a, b) ((a)=min((a), (b))) #define chmax(a, b) ((a)=max((a), (b))) #define fs first #define sc second #define eb emplace_back </bits/stdc++.h>…