問題の要約 N=2^20項からなる数列A=(A0,A1,...,AN-1)があり,はじめ,全ての要素は-1。 Q個のクエリを順番に処理せよ。 i(1<=i<=Q)個目のクエリはti=1またはti=2を満たす整数ti及び整数xiで表され,内容は以下の通り。 ・ti=1のとき,以下の処理を順番に行う。 1…

問題の要約 N人の生徒が4日間にわたる試験を受けている。 それぞれの日に行われる試験は300点満点。すなわち,4日間を通した試験の満点は1200点。 現在3日目までの試験が終わり,これから4日目の試験が行われようとしている。 i(1<=i<=N)番目の生徒はj(1<=j<=3…

問題の要約 N人の友達がいる。それぞれ友達1,友達2,...,友達Nというあだ名で呼ばれている。 ある日,秘密を友達Xに知られてしまう。 i=1,2,...,Nについて,友達iが秘密を知ったとき,友達Aiがまだ秘密を知らなければ,友達iは秘密を友達Aiに教えてしまう。 秘密…

問題の要約 毎日S時0分に部屋の電気をつけ,毎日T時0分に消す。 電気をつけている間に日付が変わることもある。 X時30分に部屋の電気がついているかどうか判定しろ。制約 0<=S,T,X<=23 S≠T入力 S T X考え方 1,まずS<T,S>Tで条件分岐したい。 2,S<Tのとき 電気がついているのはSからTまで。 X時30分のときに電気がついているか判定しなければいけない。 XはS以上T未満の範囲ならok。 3,S>Tのとき 電気がつい</tのとき></t,s>…

問題の要約 電車がN個あり,電車1,電車2,...,電車Nと名前がついている。 はじめ電車どうしは連結しておらず,バラバラ。 クエリがQ個与えられるので,与えられた順番に処理しなさい。 クエリは次の3種類のいずれか。 ・1 x y:電車xの後部と,電車yの前部を連結さ…

問題の要約 10^100行7列の行列Aがあり,任意の整数対(i,j)(1<=i<=10^100,1<=j<=7)についてその成分は(i-1)*7+j。 N行M列の行列Bが与えられるので,BがAの一部の短形領域を(向きを変えずに)切り出したものであるかを判定しろ。制約 1<=N<=10^4 1<=M<=7 1<=Bi,j<…

問題の要約 N頂点N-1辺の木が与えられる。 頂点は1,2,...,Nの番号がついており,i番目の辺は頂点aiと頂点biを結んでいる。 この木がスターであるか判定しろ。 ただしスターとは,1つの頂点から他の全ての頂点に1本ずつ辺が出ている木のことである。制約 3<=N<=…

問題の要約 英小文字のみからなる長さ3の文字列Sが与えられる。 Sの各文字を並び替えて得られる文字列は,何種類あるか?制約 Sは英小文字のみからなる長さ3の文字列 入力 S 考え方 1,これは同じものがある順列である。 2,順列はC++ではnext_permutationで生成…

問題の要約 直交座標の上にN個の街があり,1,2,...,Nと番号がつけられている。 街iは地点(xi,yi)にあり,2つの異なる番号の街が同じ座標にあることはない。 魔法があり,魔法は整数の組(a,b)によって識別されていて,地点(x,y)にいるときに魔法(a,b)を使うと,(x+…

問題の要約 武術家の覚えられる技がN個あり,技1,2,...,Nと名前がついている。 1<=i<=Nについて,技iを習得するには時間Tiの修練が必要で,さらに,修練の開始時点で技Ai,1,Ai,2,...,Ai,Kiをすでに習得している必要がある。 ここで,1<=j<=Kiについて,Ai,j

問題の要約 1からNまでの番号のついたN個の数列が与えられる。 数列iは、長さLiでj(1<=j<=Li)番目の要素がai.jであるような数列である。 数列iと数列jは,Li=Ljかつすべてのk(1<=k<=Li)に対してai,k=aj,kが成り立つとき同じであるとみなす。 同じ数列は1種類…

問題の要約 実数Xが小数第三位まで入力される。 Xを小数第一位で四捨五入した結果として得られる整数を出力しなさい。制約 0<=X<=100入力 X考え方 1,小数を四捨五入する関数があればよい。 2,C++にはround関数があるのでそれを使う。 実際のプログラム#inclu…

問題の要約 N個の部署があり,i(1<=i<=N)番目の部署にはAi人の社員がいる。異なる部署に同じ社員はいない。 1つのプロジェクトをK個の部署から1人ずつ選出して作り、ちょうどK人から構成したい。 プロジェクトは最大でいくつ作れるか?1人が複数のプロジェクト…

問題の要約 正の整数Nが与えられる。 A<=B<=CかつABC<=Nであるような正の整数の組(A,B,C)の個数を求めよ。 制約上2^63未満であることが保証されている。制約 1<=N<=10^11入力 N 考え方 1,A=1,B=1のとき,Cは1からNまでのN個ある。 A=1,B=2のとき,Cは2からfloo…

問題の要約 1からNの番号のついたN人の人がいる。 人iはビルの面積をSiと予想。 本来のビルの面積は4ab+3a+3bである(a,bは正の整数)。 N人のうち、予想した面積が確実に誤りであるとわかる人数を求めよ。制約 1<=N<=20 1<=Si<=1000入力 N S1,...,SN 考え方 1…

問題の要約 1,2,...,Nの番号のついたN人に合計K枚のカードを配る。 番号Aから始めて、1枚ずつ順番にカードを配る。 最後のカードは誰に配られるでしょう。制約 1<=N,K<=1000 1<=A<=N入力 N K A 考え方 1,まず人の番号を1ずつずらす。 1,2,...,N => 0,1,...,N…

//木の同型性判定プログラム//"Explanation for Tree isomorphism talk"と"木を隠すなら森の中"を参考にプログラミングしてみました。//ソースコードはC++//入力:頂点数n、(辺数n-1)、の二つの根なし無向木T1とT2//出力:T1とT2が同型ならば"Yes"、そうでない…

//グラフの平面性テストのプログラムです。//Ulrik BrandesのThe Left-Right Planarity Testを参考にしてプログラミングしてみました。//Embeddingのところは未完成なので参考程度にどうぞ。//ソースコードはC++です。//入力:頂点数n、辺数mの単純無向グラフ…

２，リスト彩色予想 リスト彩色予想 任意の単純グラフGは、ch1(G)=χ1(G)である。 (証明) 1つ反例を示すことで、予想を否定する。 完全グラフKpの位数が奇数の場合を考える。Kpのサイズqはp(p-1)/2である。 完全グラフKpに対してχ1(Kp)=p(pが奇数)、p-1(pが偶…

(注意)この記事はディーステル「グラフ理論」の内容をお借りしている部分が多いです。 １、リスト彩色 グラフGと、その各頂点に対して塗ることが許される色のリストが与えられている。このとき、そのリストから選んだ色を頂点に割り当てて、Gを彩色すること…

漫画「数学ゴールデン」の1巻に次のような問題が出てくる。それを解いてみた。 「17人それぞれが他の全員と互いに手紙のやりとりをしている。 その手紙では3つの話題のみがやりとりされている。 そして、同じ2人組の間でなされる話題は常に同じ1つのやりとり…

４，全彩色 グラフGの全彩色とは、Gの隣接するどの2元、または接続するどの2元も異なる色を持つようなGの元(頂点と辺)に色を付けることである。k個の色を用いる全彩色をk-全彩色という。グラフGに対して、k-全彩色が存在するときGはk-全彩色可能であるという…

３，辺彩色 グラフGの隣接する辺が異なる色になるように、グラフGの各辺に色をつけることを、Gの辺彩色といい、k個の色が使われているとき、それをk-辺彩色という。グラフGに対して、k-辺彩色が存在するときGはk-辺彩色可能であるという。Gがk-辺彩色可能で…

２、線グラフと全グラフ グラフGにおいて、頂点集合E(G)を持ち、その中の2頂点は、G内の隣接する2辺であるとき、かつそのときに限って隣接するようなグラフをGの線グラフといいL(G)で表す。 グラフGの全グラフT(G)とは、集合V(G)⋃E(G)と1対1対応する頂点集合…

(注意)完全グラフと全彩色予想の内容や定理の証明は「グラフ理論序説」からお借りしている部分が多いです。 １，因子分解 グラフHがグラフGの部分グラフであるとは、Hが V(H)がV(G)の部分集合 かつ E(H)がE(G)の部分集合 を満たすグラフのことである。特に、…

４，グラフの頂点彩色 単純グラフGの隣接するどの2頂点も異なる色になるようにGのすべての頂点を色分けすることをGの頂点彩色という。k種類の色によるGの頂点彩色をGのk-彩色といい、Gがk-彩色できるとき、Gはk-彩色可能であるという。 グラフの頂点vに色を…

２、木 閉路のない連結なグラフを木と呼ぶ。 定理２・１ 木において、位数をp、サイズをqとすると、 p=q+1 が成り立つ。 (証明)数学的帰納法で証明する。 ①位数p=1のとき、サイズq=0である。 q≧2とすると、p=2のとき、q=1により式が成り立つ。 ②位数がp-1以…

（注）この極大平面的グラフの頂点彩色と四色問題の記事の内容や定理の証明は、「グラフ理論序説」の内容をそのままお借りしているところがあります。 １，グラフ グラフGとは、集合の対(V(G)、E(G))である。 V(G)をグラフGの頂点集合、V(G)の元を頂点という…

「やさしいグラフ論」を読んでプログラムしたくなったので、載せておきます。 ソースコードはC++です。 入力：負でない整数の列s：d1,d2,・・・,dn(d1≧d2≧・・・≧dn) 出力：sがグラフ的であるならばグラフを出力、そうでないならばNoを出力。 #include<iostream>#inclu</iostream>…

「やさしいグラフ論」を読んでプログラムしたくなったので、載せておきます。 ソースコードはC++です。 入力：負でない整数の列s：d1,d2,・・・,dn(d1≧d2≧・・・≧dn) 出力：sがグラフ的であるならばYes、そうでないならばNo。 #include<iostream>#include<vector>#include<algorithm> usin</algorithm></vector></iostream>…