comp を指定する https://cpprefjp.github.io/reference/algorithm/next_permutation.html 上のサイトを見ると, 第三引数に比較関数を取れるので, 比較関数を作れば辞書順の逆でやることも可能. プログラムは以下の通りになる. #include <bits/stdc++.h> using namespace st</bits/stdc++.h>…

問題 問題概要 スタートからゴールまで最短距離で移動したい. 影を通れば距離には加算されない. (2017 ICPC国内模擬 E) 解法 建物とその影を考えて多角形を作り, N個の多角形どうしの距離を計算して辺を作り, ダイクストラで最短距離を計算すれば良い. 建物…

問題 問題概要 グラフがあたえられる. 各頂点のいくつかはガソリンステーションでガソリンを入れることができる. ガソリンがなくならずに, スタートからゴールに行くまでの最短距離を求める. またLPGのタンクの最大容量もあたえられる. 車の燃費は10km/Lであ…

問題 問題概要 頂点の間の容量が与えられる. 複数のスタートから一つのゴールまで最大どのくらいのものを運ぶことができるか. 解法 G個のスタート地点があるので, スタート地点の頂点を新たに作り, そこから魔導石に近い魔法使いへ辺の容量がINFの辺をはる. …

問題 問題概要 五芒星が与えられる. スタートの星からゴールの星までの移動の最小距離を求める. 星の中は移動距離に入らない. 解法 星と星の距離は, 各星は5つの辺からなっていることから, 5つの辺ぞれぞれを総当りで調べて, その中の最小値が距離になる. こ…

問題 問題概要 ボールが通る線分とそれをじゃまするN個の直方体が与えられる. 直方体に重ならずに線分をスタートからゴールまで通ることができるボールの半径の最大値を求める. 解法 長方形と線分の距離をdとして求める半径をrとすると, d <= hのとき, r = d…

問題 問題概要 頂点を(-100,-100)、(100,-100)、(100,100)、(-100,100) とする正方形とn個の線分が与えられる. 線分の両端は正方形の辺上にある. 線分により正方形がいくつに分割されるかを求めよ. 解法 順番に線分を書いていくことを考える. いま書く線分と…

問題 問題概要 長方形が与えられ, そのますに値が入っている. 長方形を分割してくが, 分割方法は区切られた長方形を一つ選び, それを縦か横どちらに切って分ける. 分割できるのは, 分割後に任意のグループを一つ選び, 抑制需要(残ったグループのますの値の合…

問題 問題概要 ‘('と’)‘が含まれた文字列が与えられる. その文字列のl番目からからr番目のまでの文字を考えたときに, その中にカッコの対応が最大でいくつできるかを書くクエリごとに答える. 解法 segtreeを使えばよい. 状態として区間[l, r)の中で, すでに…

アドレスの差分にはならない. int main(void){ int a[2]; int k = &a[1] - &a[0]; return 0; } 上のコードを実行したら, kを表示すると結果は1となる. 4ではない. ポインタ同士の引き算は内部でアドレスの値を引いた後にそのポインタが指している変数の型の…

問題 問題概要 奇数回目に数列を左から隣同士を見て, ORを計算し, 偶数回目に数列を左から見て, XORを計算する. それぞれのステップで数列の要素数は半分になる. 数列の要素数が1になるまでこれを繰り返す. はじめの数列がm回変化するので, m個の数列に対し…

問題 問題概要 与えられた漸化式によって導かれるM番目の値を求めよ. 解法 andとxorの演算は, (G, 和, 積) := ({1,0}, xor, and)とすると, 環をなしている. また, 行列の演算は半環であれば, 成り立つ. これらのことから, 通常の行列ライブラリの和をxorへ, …

問題 問題概要 1以上N以下の全ての数字のなかに数字1が全部でいくつ含まれているか? 解法 脳死しているので桁dpをする. dp[i][j][k] := i桁目まで見て, j==1ならNより小さい, 1を使った数がk回となる数字の総数 という状態を決めてやればいい. 漸化式の遷移…

問題 問題概要 頂点1からNまでの最短コストを求めよ. ただし辺のコストtに加えて, 辺を通る時の色が決められているので, 色を変えるのにもコストがかかる. xからyに色を変える場合のコストは, |x-y|である. 解法 拡張ダイクストラをすればいい. dist[i][j]と…

問題 問題概要 a1 = 1, ai = 100ai-1 + 1という数列がある. 第N項を1000000007と101010101010101010101で割ったあまりを求める. 解法 前半の解 数列の一般項を求めて計算するだけ. ただし, 数が大きくなるため, 逐次modをとったり, powmodでやらないと行けな…

問題 問題概要 1以上N以下の整数で、109 + 1 の倍数かつ回文の数の個数を求めな 解法 109+1の倍数かつ回文になるには, 109+1に回文をかければ良い. よって, Nを109+1で割った数以下の整数で, 回文の個数を数えれば良い. よって, dfsを用いて, その整数の桁数…

問題 問題概要 [l, r]の区間を考えた時に, al, .. , ar の最大値と bl, .. , br の最小値が一致する区間の総数を求める. 解法 区間の左端を固定して, 右端を伸ばしていくと, aの最大値は単調増加, bの最小値は単調減少していくので, 区間を伸ばしていくとど…

問題 問題概要 N人の人がM個の教室を掃除する. 一人が掃除する連続区間の教室が与えられる. ひとつの教室につき一人以上が掃除をしていればいい. どの区間を掃除する人はさぼることができるか. さぼる人は 同時に1人として考える. 解法 まずimos法を利用して…

問題 問題概要 与えられた文字列に応じて出力する文字列を変更する. 解法 string s; while(cin>>s){ //処理 } 上記のような方法で, スペースまでの文字列を受け取り, 終了したらwhileを抜けれる. ミス なし. コード #include <bits/stdc++.h> using namespace std; typedef </bits/stdc++.h>…

問題 問題概要 A1をstartとした時の頂点までの最短経路の情報が与えられる. その木の高さで作ることのできるグラフは何通りあるか, mod1e9+7で答えろ. 解法 まず, A１からの最短経路の情報が与えられているはずなので, A1以外で最短経路が0であればそのよう…

問題 問題概要 Nが素数ならPrime Nが合成数で, 1の位が2,5で割り切れず, 各桁の和が3で割り切れないとき, Prime それ以外なら Not Prime 解法 まず, 普通に素数判定をし, 素数ならPrime. 次に, 1のくらいが2, 5で割り切れず, 各桁の和が3で割り切れないけれ…

問題 問題概要 i番目のものをi+1として考えて, 色を塗っていく. 塗る色はその数の素因数と同じ色にしてはいけない. 塗る色の最小数を求める問題. 解法 その数しか素因数を持たない素数はすべて同じ色で塗ることが可能. そのようにすると, 素数でない数はすべ…

問題 問題概要 文字列が2つ与えられる. ひとつの文字列を指定された文字列に置換する操作を行うクエリに応える. 解法 setで管理しながら, 置換される方をeraseして, 加える方をinsertしていけばいい. ミス なし. コード #include <bits/stdc++.h> using namespace std; type</bits/stdc++.h>…

問題 問題概要 与えられた文字列をすべて与えらた順番で辞書順にする. そのために各文字列から末尾の文字を好きなだけ取り除いていい. 取り除く文字の最小数を求める問題. 解法 一番後ろの文字はそのままにできることがわかるので, 後ろから順番に見ていき, …

問題 問題概要 数列a, bが与えられる. 数列ｂは好きな順番に変更することができる. (1) a[i] > b[i] となる i の個数の最小数 (2) a[i] < b[i]となる i の個数の最大数 を求める問題 解法 2部マッチングの最大数を使ってとく. 数列bを任意の順番に動かすこと…

問題 問題概要 カップを3つ用意して, その中のどこかに玉をいれる. カップの番号を左から0, 1, 2としてn回動かす. その動かし方は, 奇数回の時は0と1を入れ替えて, 偶数回の時は1と2を入れ替える. n回入れ替えたあとの位置が与えられるので, はじめ何番目の…

問題 問題概要 明らかなfsbがある. さらにスタックが+xである. しかし文字数制限がある. 解法 % file babyecho babyecho: ELF 32-bit LSB executable, Intel 80386, version 1 (SYSV), statically linked, for GNU/Linux 2.6.24, BuildID[sha1]=c9a66685159a…

問題 問題概要 ノード間のつながりが与えられる. 任意の4つのノードの組み合わせを考えて, その4つのノード間のつながりだけを考えたときに四角形となっている組み合わせがいくつあるか. 解法 n=50なので, すべての任意の4つの組み合わせの総数nC4を全部計算…

問題 問題概要 2017 + (2017*2017)2017 のMOD Mを計算. 解法 2017*2017のを2017乗するととても大きな値になるので逐次MODをとりながら計算していく. 掛け算足し算の計算ではすべて計算したあとにMODをとっても, 計算途中でMODをとって計算していっても結果は…

問題 問題概要 OXXXOXXのようなOとXからなる文字列が与えられる. OはEastの勝ちで, XはWestの勝ちを表している. 先に3連勝したほうを勝ちとする. どちらが勝つか. 勝者がない時はNAを出力. 解法 連続した3文字が同じ文字であるかを判定し, 先に同じ文字にな…