「ゼロからのOS自作入門」をHyper-Vで動かしたときのメモ
「ゼロからのOS自作入門」を読んで作成した自作osを、Hyper-Vで動かしたときに難しかったところをメモしておきます。
ACPI PMタイマまで作成しましたが、USBドライバ、windowなど作成していない機能もあります。
まずはブート可能なイメージファイルを作成する手順を載せます。
1:UEFIブート可能なUSBメモリを作成する。
2:そのUSBメモリをUSB Image Toolなどで丸ごとイメージファイルにする。これをos.imgとする。
3:WinISOなどブート可能なイメージファイルを作成できるソフトウェアのboot imageにos.imgを設定してブート可能なイメージファイルを作成する。これをos.isoとする。
4:os.isoをhyper-vの仮想マシンのdvdドライブにセットして起動する。
bootloderで変更したところを載せます。
まず、FrameBufferSizeを使うことをやめました。その代わり、VerticalResolution、HorizontalResolution、PixelsPerScanLineを使います。
次に、CDやDVDは書き込みができないため、memory mapをファイルに書くことをやめました。
そして、カーネルのロードのときにエラーが出たため。カーネルのビルドの時に--image-baseオプションの値を変更しました。私の環境では0x464c000で動きました。
kiernelで変更したところを載せます。
ACPI PMタイマが動かなかったので、osdevのサイトを見てFADTの構造体を変更して、X_PMTimerBlockを使用してACPI PMタイマを動かしました。
C++でRange Coder(桁上がりなし)
・高速な算術圧縮を実現する「Range Coder」
https://codezine.jp/article/detail/443
・Algorithms with Python レンジコーダ(range coder)[2]
http://www.nct9.ne.jp/m_hiroi/light/pyalgo37.html
を参考にC++でプログラミングしてみました。
テストをあまりしていないですし、圧縮率も調べてないですが参考までに載せます。
range_coder.hpp
range_coder.cpp
encoder.cpp
decoder.cpp
の4つのプログラムを載せます。
// range_coder.hpp
#pragma once
#include<iostream>
#include<fstream>
#include<vector>
#include<string>
using uint = unsigned int;
using byte = unsigned char;
using filename = std::string;
class RangeCoder{
private:
uint low;
std::vector<byte> lows;
uint lows_count;
uint code;
std::vector<byte> codes;
uint codes_count;
uint range;
uint total;
filename inputfilename;
filename outputfilename;
std::ifstream ifs;
std::ofstream ofs;
std::vector<byte> words;
uint digit_start[0x100] = {0};
uint digit_size[0x100] = {0};
const uint max_range = 0xffffffff;
const uint min_range = 0x00010000;
const uint mask = 0xffffffff;
const uint mask1 = 0xff000000;
const uint shift = 24;
void initializeEncoder();
void runEncoder();
void encode(uint start, uint size);
void encode_normalize();
void initializeDecoder();
void runDecoder();
void decode();
void decode_normalize();
public:
RangeCoder(filename inputfile, filename outputfile, bool encode);
};
// range_coder.cpp
#include"range_coder.hpp"
RangeCoder::RangeCoder(filename inputfile, filename outputfile, bool encode){
inputfilename = inputfile;
outputfilename = outputfile;
ifs.open(inputfilename, std::ios::in | std::ios::binary);
if(!ifs){
std::cout << "can not open a inputfile." << std::endl;
exit(0);
}
ofs.open(outputfilename, std::ios::out | std::ios::binary);
if(!ofs){
std::cout << "can not open a outputfile." << std::endl;
exit(0);
}
if(encode){
byte buffer;
do{
ifs.read( (char*)&buffer, sizeof(byte));
words.push_back(buffer);
++digit_size[buffer];
//std::cout << (unsigned short)buffer << std::endl;
}while(!ifs.eof());
runEncoder();
// totalを出力ファイルへ埋め込む
ofs.write( (char*)(&total), sizeof(uint));
// digit_sizeを出力ファイルへ埋め込む
for(uint i = 0; i < 0x100; ++i){
ofs.write( (char*)(&digit_size[i]), sizeof(uint));
}
// lowsを出力ファイルへ埋め込む
ofs.write( (char*)(&lows_count), sizeof(uint));
//std::cout << lows_count << std::endl;
for(uint i = 0; i < lows_count; ++i){
ofs.write( (char*)(&lows[i]), sizeof(byte));
}
//std::cout << total << std::endl;
// テスト用
/*
for(uint i = 0; i < 0x100; ++i){
std::cout << i << " " << digit_start[i] << " " << digit_size[i] << std::endl;
}*/
// テスト用
/*
for(uint i = 0; i < static_cast<uint>(word.size()); ++i){
ofs.write( (char*)(&word[i]), sizeof(byte));
}*/
}else{
ifs.read( (char*)&total, sizeof(uint));
//std::cout << total << std::endl;
for(uint i = 0; i < 0x100; ++i){
ifs.read( (char*)(&digit_size[i]), sizeof(uint));
}
// lowsをcodesとして入力する
ifs.read( (char*)&lows_count, sizeof(uint));
//std::cout << lows_count << std::endl;
codes.assign(lows_count, 0);
for(uint i = 0; i < lows_count; ++i){
ifs.read( (char*)(&codes[i]), sizeof(byte));
}
runDecoder();
for(uint i = 0; i < total; ++i){
ofs.write( (char*)(&words[i]), sizeof(byte));
}
//std::cout << total << std::endl;
// テスト用
/*
for(uint i = 0; i < 0x100; ++i){
std::cout << i << " " << digit_start[i] << " " << digit_size[i] << std::endl;
}*/
}
}
void RangeCoder::initializeEncoder(){
low = 0;
range = max_range;
total = words.size() - 1;
lows_count = 0;
for(uint i = 0; i < 0x100; ++i){
digit_start[i] = digit_size[i];
}
for(uint i = 0; i < 0x100-1u; ++i){
digit_start[i+1] += digit_start[i];
digit_start[i] -= digit_size[i];
}
}
void RangeCoder::runEncoder(){
initializeEncoder();
for(uint i = 0; i < total; ++i){
encode(digit_start[words[i]], digit_size[words[i]]);
}
//std::cout << low << std::endl;
lows.push_back( (byte)( (low >> 24) & 0xff));
++lows_count;
lows.push_back( (byte)( (low >> 16) & 0xff));
++lows_count;
lows.push_back( (byte)( (low >> 8) & 0xff));
++lows_count;
lows.push_back( (byte)(low & 0xff));
++lows_count;
}
void RangeCoder::encode(uint start, uint size){
uint unit = range / total;
low = low + start * unit;
range = size * unit;
encode_normalize();
}
void RangeCoder::encode_normalize(){
while( (low & mask1) == ( (low + range) & mask1)){
lows.push_back( (byte)(low >> shift));
++lows_count;
low = (low << 8) & mask;
range <<= 8;
}
while(range < min_range){
range = (min_range - (low & (min_range-1))) << 8;
lows.push_back( (byte)(low >> shift));
++lows_count;
low = (low << 8) & mask;
}
}
void RangeCoder::initializeDecoder(){
low = 0;
range = max_range;
codes_count = 0;
code = codes[codes_count];
++codes_count;
code = (code << 8) + codes[codes_count];
++codes_count;
code = (code << 8) + codes[codes_count];
++codes_count;
code = (code << 8) + codes[codes_count];
++codes_count;
//std::cout << code << std::endl;
for(uint i = 0; i < 0x100; ++i){
digit_start[i] = digit_size[i];
}
for(uint i = 0; i < 0x100-1u; ++i){
digit_start[i+1] += digit_start[i];
digit_start[i] -= digit_size[i];
}
}
void RangeCoder::runDecoder(){
//std::cout << "test message runDecoder in." << std::endl;
initializeDecoder();
for(uint i = 0; i < total; ++i){
decode();
}
}
void RangeCoder::decode(){
uint unit = range / total;
uint value = (code - low) / unit;
byte word;
for(byte i = 0; i <= 0xff; ++i){
if(digit_start[i] <= value && value < digit_start[i]+digit_size[i]){
word = i;
break;
}
}
words.push_back(word);
low = low + digit_start[word] * unit;
range = digit_size[word] * unit;
decode_normalize();
}
void RangeCoder::decode_normalize(){
while( (low & mask1) == ( (low + range) & mask1)){
code = ( (code << 8) & mask) + codes[codes_count];
++codes_count;
low = (low << 8) & mask;
range <<= 8;
}
while(range < min_range){
range = (min_range - (low & (min_range-1))) << 8;
code = ( (code << 8) & mask) + codes[codes_count];
++codes_count;
low = (low << 8) & mask;
}
}
// encoder.cpp
#include<iostream>
#include"range_coder.hpp"
using namespace std;
int main(int argc, char *argv){
if(argc != 2){
return 0;
}
filename inputfile(argv[1]);
filename outputfile = inputfile + ".rc";
RangeCoder* rc = new RangeCoder(inputfile, outputfile, true);
delete rc;
return 0;
}
// decoder.cpp
#include<iostream>
#include"range_coder.hpp"
using namespace std;
int main(int argc, char *argv){
if(argc != 2){
return 0;
}
filename inputfile(argv[1]);
filename outputfile(argv[1], inputfile.size()-3);
RangeCoder* rc = new RangeCoder(inputfile, outputfile, false);
delete rc;
return 0;
}
平面性テストと埋め込みのプログラム
// an implementation of the hopcroft and tarjan planarity test and embedding algorithmを参考に平面性テストと埋め込みのプログラムを作成しました。
// 入力 : 頂点数n,辺数mの単純無向グラフG
// 出力 : Gが平面的ならばPLANARと頂点数n,辺数mの平面的グラフの埋め込み、そうでないならばNOTPLANAR
#include<iostream>
#include<vector>
#include<list>
#include<stack>
#include<algorithm>
#include<memory>
using namespace std;
class Graph{
private:
enum class LeftRight{
Empty,
Left,
Right,
};
using Vertex = long long;
using VertexNum = long long;
using Edge = pair<Vertex, Vertex>;
using EdgeNum = long long;
using GraphList = vector<list<Vertex>>;
using Num = long long;
using NumEdgePair = pair<Num, Edge>;
const Vertex VertexNull = -1;
class Block{
private:
list<Num> Latt,Ratt;
list<Edge> Lseg,Rseg;
public:
Block(Edge e, list<Num> &A){
Lseg.push_back(e);
Latt.insert(Latt.end(), A.begin(), A.end());
A.clear();
}
void flip(){
swap(Latt, Ratt);
swap(Lseg, Rseg);
}
Num headOfLatt(){
return Latt.front();
}
bool emptyLatt(){
return Latt.empty();
}
Num headOfRatt(){
return Ratt.front();
}
bool emptyRatt(){
return Ratt.empty();
}
bool leftInterlace(stack<unique_ptr<Block>> &S){
if(Latt.empty()){
cout << "Latt is never empty." << endl;
exit(0);
}
if(!S.empty() && !(S.top()->emptyLatt()) && Latt.back() < S.top()->headOfLatt()){
return true;
}else{
return false;
}
}
bool rightInterlace(stack<unique_ptr<Block>> &S){
if(Latt.empty()){
cout << "Latt is never empty." << endl;
exit(0);
}
if(!S.empty() && !(S.top()->emptyRatt()) && Latt.back() < S.top()->headOfRatt()){
return true;
}else{
return false;
}
}
void combine(unique_ptr<Block> &Bprime){
Latt.insert(Latt.end(), Bprime->Latt.begin(), Bprime->Latt.end());
Ratt.insert(Ratt.end(), Bprime->Ratt.begin(), Bprime->Ratt.end());
Lseg.insert(Lseg.end(), Bprime->Lseg.begin(), Bprime->Lseg.end());
Rseg.insert(Rseg.end(), Bprime->Rseg.begin(), Bprime->Rseg.end());
Bprime->Latt.clear();
Bprime->Ratt.clear();
Bprime->Lseg.clear();
Bprime->Rseg.clear();
}
bool clean(Num dfsnum_w, vector<vector<LeftRight>> &alpha, vector<Num> &dfsnum){
while(!Latt.empty() && Latt.front() == dfsnum_w){
Latt.pop_front();
}
while(!Ratt.empty() && Ratt.front() == dfsnum_w){
Ratt.pop_front();
}
if(!Latt.empty() || !Ratt.empty()){
return false;
}
for(auto itr = Lseg.begin(); itr != Lseg.end(); ++itr){
Edge e = *itr;
alpha[e.first][e.second] = LeftRight::Left;
}
for(auto itr = Rseg.begin(); itr != Rseg.end(); ++itr){
Edge e = *itr;
alpha[e.first][e.second] = LeftRight::Right;
}
return true;
}
void addToAtt(list<Num> &Att, Num dfsnum_w0, vector<vector<LeftRight>> &alpha, vector<Num> &dfsnum){
if(!Ratt.empty() && headOfRatt() > dfsnum_w0){
flip();
}
Att.insert(Att.end(), Latt.begin(), Latt.end());
Latt.clear();
Att.insert(Att.end(), Ratt.begin(), Ratt.end());
Ratt.clear();
for(auto itr = Lseg.begin(); itr != Lseg.end(); ++itr){
Edge e = *itr;
alpha[e.first][e.second] = LeftRight::Left;
}
for(auto itr = Rseg.begin(); itr != Rseg.end(); ++itr){
Edge e = *itr;
alpha[e.first][e.second] = LeftRight::Right;
}
}
};
bool runPlanarityTest;
bool isPlanarityGraph;
bool runPlanarEmbed;
VertexNum n;
EdgeNum m;
GraphList G_list;
GraphList Gin_list;
void countSort(vector<NumEdgePair> &input, Num exp){
EdgeNum num = static_cast<Num>(input.size());
vector<NumEdgePair> output(num);
vector<Num> count(10, 0);
for(EdgeNum i = 0; i < num; ++i){
++count[(input[i].first / exp) % 10];
}
for(Num i = 1; i < 10; ++i){
count[i] += count[i-1];
}
for(EdgeNum i = num-1; i >= 0; --i){
output[count[(input[i].first / exp) % 10]-1] = input[i];
--count[(input[i].first / exp) % 10];
}
for(EdgeNum i = 0; i < num; ++i){
input[i] = output[i];
}
}
void radixSort(vector<NumEdgePair> &input){
EdgeNum num = static_cast<EdgeNum>(input.size());
Num maxNum = input[0].first;
for(EdgeNum i = 0; i < num; ++i){
maxNum = max(maxNum, input[i].first);
}
for(Num exp = 1; maxNum /exp > 0; exp *= 10){
countSort(input, exp);
}
}
void dfs(Vertex now, vector<bool> &reached){
reached[now] = true;
for(auto itr = G_list[now].begin(); itr != G_list[now].end(); ++itr){
Vertex next = *itr;
if(!reached[next]){
dfs(next, reached);
}
}
}
void makeBiconnectedGraph(){
vector<bool> reached(n, false);
Vertex u = 0;
for(Vertex v = 0; v < n; ++v){
if(!reached[v]){
dfs(v, reached);
if(u != v){
G_list[u].push_back(v);
G_list[v].push_back(u);
}
}
}
for(Vertex v = 0; v < n; ++v){
reached[v] = false;
}
vector<Num> dfsnum(n);
vector<Vertex> parent(n, VertexNull);
Num dfs_count = 0;
vector<Num> lowpt(n);
dfsInMakeBiconnectedGraph(0, dfs_count, reached, dfsnum, lowpt, parent);
}
void dfsInMakeBiconnectedGraph(Vertex v, Num &dfs_count, vector<bool> &reached, vector<Num> &dfsnum, vector<Num> &lowpt, vector<Vertex> &parent){
dfsnum[v] = dfs_count;
++dfs_count;
lowpt[v] = dfsnum[v];
reached[v] = true;
if(G_list[v].empty()){
return;
}
Vertex u = G_list[v].front();
for(auto itr = G_list[v].begin(); itr != G_list[v].end(); ++itr){
Vertex w = *itr;
if(!reached[w]){
parent[w] = v;
dfsInMakeBiconnectedGraph(w, dfs_count, reached, dfsnum, lowpt, parent);
if(lowpt[w] == dfsnum[v]){
if(w == u && parent[v] != VertexNull){
G_list[w].push_back(parent[v]);
G_list[parent[v]].push_back(w);
}
if(w != u){
G_list[u].push_back(w);
G_list[w].push_back(u);
}
}
lowpt[v] = min(lowpt[v], lowpt[w]);
}else{
lowpt[v] = min(lowpt[v], dfsnum[w]);
}
}
}
void reorder(vector<Num> &dfsnum, vector<Vertex> &parent){
vector<bool> reached(n, false);
Num dfs_count = 0;
list<Edge> Del;
vector<Num> lowpt1(n), lowpt2(n);
Vertex first_vertex = 0;
dfsInReorder(Del, first_vertex, dfs_count, reached, dfsnum, lowpt1, lowpt2, parent);
for(auto it = Del.begin(); it != Del.end(); ++it){
Edge e = *it;
Vertex u = e.first;
Vertex v = e.second;
for(auto itr = G_list[u].begin(); itr != G_list[u].end(); ){
if(*itr == v){
itr = G_list[u].erase(itr);
continue;
}
++itr;
}
}
vector<vector<Num>> cost(n, vector<Num>(n, 0));
vector<Edge> edges;
for(Vertex v = 0; v < n; ++v){
for(auto itr = G_list[v].begin(); itr != G_list[v].end(); ++itr){
Vertex w = *itr;
Num c = (dfsnum[w] < dfsnum[v] ? 2*dfsnum[w] : (lowpt2[w] >= dfsnum[v] ? 2*lowpt1[w] : 2*lowpt1[w]+1));
cost[v][w] = c;
edges.push_back(make_pair(v, w));
}
}
vector<NumEdgePair> sort_edges;
for(Vertex u = 0; u < n; ++u){
for(auto itr = G_list[u].begin(); itr != G_list[u].end(); ++itr){
Vertex v = *itr;
sort_edges.push_back(make_pair(cost[u][v], make_pair(u, v)));
}
}
radixSort(sort_edges);
G_list.clear();
G_list.resize(n);
for(EdgeNum i = 0; i < static_cast<EdgeNum>(sort_edges.size()); ++i){
Edge e = sort_edges[i].second;
G_list[e.first].push_back(e.second);
}
}
void dfsInReorder(list<Edge> &Del, Vertex v, Num &dfs_count, vector<bool> &reached, vector<Num> &dfsnum, vector<Num> &lowpt1, vector<Num> &lowpt2, vector<Vertex> &parent){
dfsnum[v] = dfs_count;
++dfs_count;
lowpt1[v] = dfsnum[v];
lowpt2[v] = dfsnum[v];
reached[v] = true;
for(auto itr = G_list[v].begin(); itr != G_list[v].end(); ++itr){
Vertex w = *itr;
if(!reached[w]){
parent[w] = v;
dfsInReorder(Del, w, dfs_count, reached, dfsnum, lowpt1, lowpt2, parent);
lowpt1[v] = min(lowpt1[v], lowpt1[w]);
}else{
lowpt1[v] = min(lowpt1[v], dfsnum[w]);
if(dfsnum[w] >= dfsnum[v] || w == parent[v]){
Del.push_back(make_pair(v, w));
}
}
}
for(auto itr = G_list[v].begin(); itr != G_list[v].end(); ++itr){
Vertex w = *itr;
if(parent[w] == v){
if(lowpt1[w] != lowpt1[v]){
lowpt2[v] = min(lowpt2[v], lowpt1[w]);
}
lowpt2[v] = min(lowpt2[v], lowpt2[w]);
}else{
if(lowpt1[v] != dfsnum[w]){
lowpt2[v] = min(lowpt2[v], dfsnum[w]);
}
}
}
}
bool stronglyPlanar(Edge e0, list<Num> &Att, vector<vector<LeftRight>> &alpha, vector<Num> &dfsnum, vector<Vertex> &parent){
// determine the cycle C(e0)
Vertex x = e0.first;
Vertex y = e0.second;
Edge e = make_pair(y, G_list[y].front());
Vertex wk = y;
while(dfsnum[e.second] > dfsnum[wk]){
wk = e.second;
e = make_pair(wk, G_list[wk].front());
}
Vertex w0 = e.second;
// process all edges leaving the spine
Vertex w = wk;
stack<unique_ptr<Block>> S;
while(w != x){
Num count = 0;
for(auto itr = G_list[w].begin(); itr != G_list[w].end(); ++itr){
e = make_pair(w, *itr);
++count;
if(count != 1){
// test recursively
list<Num> A;
if(dfsnum[w] < dfsnum[e.second]){
if(!stronglyPlanar(e, A, alpha, dfsnum, parent)){
while(!S.empty()){
S.pop();
}
return false;
}
}else{
A.push_back(dfsnum[e.second]);
}
// update stack S of attachments
unique_ptr<Block> B(new Block(e, A));
while(true){
if(B->leftInterlace(S)){
S.top()->flip();
}
if(B->leftInterlace(S)){
while(!S.empty()){
S.pop();
}
return false;
}
if(B->rightInterlace(S)){
B->combine(S.top());
S.pop();
}else{
break;
}
}
S.push(move(B));
}
}
// prepare for next iteration
while(!S.empty() && S.top()->clean(dfsnum[parent[w]], alpha, dfsnum)){
S.pop();
}
w = parent[w];
}
// test strong planarity and compute Att
Att.clear();
while(!S.empty()){
unique_ptr<Block> B(move(S.top()));
S.pop();
if(!B->emptyLatt() && !B->emptyRatt() && (B->headOfLatt() > dfsnum[w0]) && (B->headOfRatt() > dfsnum[w0])){
while(!S.empty()){
S.pop();
}
return false;
}
B->addToAtt(Att, dfsnum[w0], alpha, dfsnum);
}
if(w0 != x){
Att.push_back(dfsnum[w0]);
}
return true;
}
void embedding(Edge e0, LeftRight t, vector<vector<LeftRight>> &alpha, vector<Num> &dfsnum, list<Edge> &T, list<Edge> &A, Num &cur_nr, vector<vector<Num>> &sort_num, vector<Edge> &tree_edge_into, vector<Vertex> &parent){
// embed : determine the cycle C(e0)
Vertex x = e0.first;
Vertex y = e0.second;
tree_edge_into[y] = e0;
Edge e = make_pair(y, G_list[y].front());
Vertex wk = y;
while(dfsnum[e.second] > dfsnum[wk]){
wk = e.second;
tree_edge_into[wk] = e;
e = make_pair(wk, G_list[wk].front());
}
Vertex w0 = e.second;
Edge back_edge_into_w0 = e;
// process the subsegments
Vertex w = wk;
list<Edge> Al, Ar;
list<Edge> Tprime, Aprime;
T.clear();
T.push_back(e);
while(w != x){
Num count = 0;
for(auto itr = G_list[w].begin(); itr != G_list[w].end(); ++itr){
e = make_pair(w, *itr);
++count;
if(count != 1){
// embed recursively
if(dfsnum[w] < dfsnum[e.second]){
LeftRight tprime = (t == alpha[e.first][e.second] ? LeftRight::Left : LeftRight::Right);
embedding(e, tprime, alpha, dfsnum, Tprime, Aprime, cur_nr, sort_num, tree_edge_into, parent);
}else{
Tprime.push_back(e);
Aprime.push_back(make_pair(e.second, e.first));
}
// update list T,Al ans Ar
if(t == alpha[e.first][e.second]){
Tprime.insert(Tprime.end(), T.begin(), T.end());
T.clear();
swap(T, Tprime);
Al.insert(Al.end(), Aprime.begin(), Aprime.end());
Aprime.clear();
}else{
T.insert(T.end(), Tprime.begin(), Tprime.end());
Tprime.clear();
Aprime.insert(Aprime.end(), Ar.begin(), Ar.end());
Aprime.clear();
swap(Ar, Aprime);
}
}
}
// compute ws adjacency list and prepare for next iteration
Edge ew = tree_edge_into[w];
T.push_back(make_pair(ew.second, ew.first));
for(auto itr = T.begin(); itr != T.end(); ++itr){
sort_num[e.first][e.second] = cur_nr;
++cur_nr;
}
T.clear();
while(!Al.empty() && Al.back().first == parent[w]){
T.push_back(Al.back());
Al.pop_back();
}
T.push_back(tree_edge_into[w]);
while(!Ar.empty() && Ar.front().first == parent[w]){
T.push_back(Ar.front());
Ar.pop_front();
}
w = parent[w];
}
// prepare the output
A.clear();
swap(A, Ar);
A.push_back(make_pair(back_edge_into_w0.second, back_edge_into_w0.first));
A.insert(A.end(), Al.begin(), Al.end());
Al.clear();
}
public:
void initialize(VertexNum n, EdgeNum m, GraphList G_list){
this->n = n;
this->m = m;
this->G_list = G_list;
this->Gin_list = G_list;
runPlanarityTest = false;
isPlanarityGraph = false;
runPlanarEmbed = false;
}
bool planar(){
if(runPlanarityTest){
return isPlanarityGraph;
}
runPlanarityTest = true;
if(n <= 3){
isPlanarityGraph = true;
return true;
}
if(3*n-6 < m){
return false;
}
// make G a copy of Gin and add edges to make G bidirected
vector<Edge> companion_in_G;
vector<Vertex> link(n);
bool Gin_is_bidirected = true;
for(Vertex u = 0; u < n; ++u){
link[u] = u;
}
for(Vertex u = 0; u < n; ++u){
for(auto itr = G_list[u].begin(); itr != G_list[u].end(); ++itr){
Vertex v = *itr;
companion_in_G.push_back(make_pair(link[u],link[v]));
}
}
// bidirect G
vector<Num> nr(n);
vector<vector<Num>> cost(n, vector<Num>(n,0));
Num cur_nr = 0;
for(Vertex u = 0; u < n; ++u){
nr[u] = cur_nr;
++cur_nr;
}
for(EdgeNum i = 0; i < static_cast<EdgeNum>(companion_in_G.size()); ++i){
Edge e = companion_in_G[i];
Vertex u = e.first;
Vertex v = e.second;
cost[u][v] = ( ( nr[u] < nr[v] ) ? n*nr[u]+nr[v] : n*nr[v]+nr[u] );
}
vector<NumEdgePair> sort_edges;
for(Vertex u = 0; u < n; ++u){
for(auto itr = G_list[u].begin(); itr != G_list[u].end(); ++itr){
Vertex v = *itr;
sort_edges.push_back(make_pair(cost[u][v], make_pair(u, v)));
}
}
radixSort(sort_edges);
G_list.clear();
G_list.resize(n);
for(EdgeNum i = 0; i < static_cast<EdgeNum>(sort_edges.size()); ++i){
Edge e = sort_edges[i].second;
G_list[e.first].push_back(e.second);
}
list<Edge> L;
for(Num i = 0; i < static_cast<Num>(sort_edges.size()); ++i){
L.push_back(sort_edges[i].second);
}
while(!L.empty()){
Edge e = L.front();
L.pop_front();
if(!L.empty() && (e.first == L.front().second) && (L.front().first == e.second)){
L.pop_front();
}else{
G_list[e.second].push_back(e.first);
Gin_is_bidirected = false;
}
}
// make G biconnected
makeBiconnectedGraph();
// make H a copy of G
GraphList H_list = G_list;
vector<Edge> companion_in_H = companion_in_G;
vector<Edge> reversal;
for(Num i = 0; i < static_cast<Num>(companion_in_H.size()); ++i){
Edge e = companion_in_H[i];
reversal.push_back(make_pair(e.second, e.first));
}
// test planarity
vector<Num> dfsnum(n);
vector<Vertex> parent(n, VertexNull);
reorder(dfsnum, parent);
vector<vector<LeftRight>> alpha(n, vector<LeftRight>(n, LeftRight::Empty));
list<Num> Att;
Vertex first_vertex = 0;
Edge e0 = make_pair(first_vertex, G_list[first_vertex].front());
alpha[e0.first][e0.second] = LeftRight::Left;
if(!stronglyPlanar(e0, Att, alpha, dfsnum, parent)){
return false;
}
// construct embedding
list<Edge> T,A;
cur_nr = 0;
vector<vector<Num>> sort_num(n, vector<Num>(n));
vector<Edge> tree_edge_into(n);
e0 = make_pair(first_vertex, G_list[first_vertex].front());;
embedding(e0, LeftRight::Left, alpha, dfsnum, T, A, cur_nr, sort_num, tree_edge_into, parent);
T.insert(T.end(), A.begin(), A.end());
for(auto itr = T.begin(); itr != T.end(); ++itr){
Edge e = *itr;
sort_num[e.first][e.second] = cur_nr;
++cur_nr;
}
vector<NumEdgePair> sort_Gin;
for(Vertex u = 0; u < n; ++u){
for(auto itr = Gin_list[u].begin(); itr != Gin_list[u].end(); ++itr){
Vertex v = *itr;
sort_Gin.push_back(make_pair(sort_num[u][v], make_pair(u, v)));
}
}
radixSort(sort_Gin);
Gin_list.clear();
Gin_list.resize(n);
for(Num i = 0; i < static_cast<Num>(sort_Gin.size()); ++i){
Edge e = sort_Gin[i].second;
Gin_list[e.first].push_back(e.second);
}
isPlanarityGraph = true;
runPlanarEmbed = true;
return true;
}
void printPlanarEmbedding(){
if(!runPlanarEmbed){
cout << "Do not run planar embed." << endl;
return ;
}
printGin_list();
}
void printG_list(){
for(Vertex u = 0; u < n; ++u){
cout << u << " : ";
for(auto itr = G_list[u].begin(); itr != G_list[u].end(); ++itr){
Vertex v = *itr;
cout << v << " ";
}cout << endl;
}cout << endl;
}
void printGin_list(){
for(Vertex u = 0; u < n; ++u){
cout << u << " : ";
for(auto itr = Gin_list[u].begin(); itr != Gin_list[u].end(); ++itr){
Vertex v = *itr;
cout << v << " ";
}cout << endl;
}cout << endl;
}
};
int main(){
long long n, m;
cin >> n >> m;
vector<list<long long>> G_list(n);
for(long long i = 0; i < m; ++i){
long long u, v;
cin >> u >> v;
G_list[u].push_back(v);
G_list[v].push_back(u);
}
Graph G;
G.initialize(n, m, G_list);
//G.printG_list();
if(G.planar()){
cout << "PLANAR" << endl;
G.printPlanarEmbedding();
}else{
cout << "NOTPLANAR" << endl;
}
return 0;
}
東京海上日動プログラミングコンテスト2022（AtCoder Beginner Contest 256）D - Union of Interval
問題の要約
実数L,Rに対して、L以上R未満からなる次数の集合を[L,R)と表す。このような形で表される集合を右半開区間という。
N個の右半開区間[Li,Ri)が与えられる。これらの和集合をSとする。Sを最小の個数の右半開区間の和集合として表せ。
制約
1<=N<=2*10^5
1<=Li<Ri<=2*10^5
入力
N
L1 R1
...
LN RN
出力
Sが最小でk個の右半開区間の和集合で表せるとする。そのようなk個の右半開区間[Xi,Yi)をXiの昇順で以下のようにk行出力せよ。
X1 Y1
...
Xk Yk
考え方
1,[Li,Ri)をvector<pair<int,int>> LRで管理する。
2,[Li,Ri)と[Lj,Rj)(i<j)を考えると、大小関係を考えるのが面倒くさいので、ソートをして、[Li,Ri)<=[Lj,Rj)(i<j)を確定してしまう。
3,考えるべき大小関係は大きく分けて
Ri < Lj : 加えて、もしRi<Rjならば[Li,Rj)としてよい。
Lj <= Ri : [Lj,Rj)は新しく起点となる右半開区間である。
の2つとなる。
4,ソートしているので、LRの最初から順に大小関係を考えていけばよい。
実際のプログラム
#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
using namespace std;
int main(){
int N;
cin >> N;
vector<pair<int,int>> LR(N);
for(int i = 0; i < N; ++i){
cin >> LR[i].first >> LR[i].second;
}
sort(LR.begin(), LR.end());
vector<pair<int,int>> ans;
for(auto it = LR.begin(); it != LR.end();){
if(ans.empty()){
ans.push_back(*it);
++it;
}else if( (*it).first <= ans[ans.size()-1].second){
if(ans[ans.size()-1].second < (*it).second){
ans[ans.size()-1].second = (*it).second;
}
++it;
}else{
ans.push_back(*it);
++it;
}
}
for(int i = 0; i < static_cast<int>(ans.size()); ++i){
cout << ans[i].first <<" "<< ans[i].second << endl;
}
return 0;
}
東京海上日動プログラミングコンテスト2022（AtCoder Beginner Contest 256）C - Filling 3x3 array
問題の要約
6個の整数、h1,h2,h3,w1,w2,w3が与えられる。
縦横3×3のマス目に、以下の条件をすべて満たすように各マスに正の整数を1つずつ書き込むことを考える。
・i=1,2,3について、上からi行目に書き込んだ数の和がhiになる。
・j=1,2,3について、左からj列目に書き込んだ数の和がwjになる。
条件を満たす書き込み方は全部で何通り存在するか?
制約
3<=h1,h2,h3,w1,w2,w3<=30
入力
h1 h2 h3 w1 w2 w3
考え方
1,3×3の行列のマスに名前をつける。
m00 m01 m02
m10 m11 m12
m20 m21 m22
2,3*3で9重のfor文になりそうだが、m02,m12,m20,m21,m22はm00,m01,m10,m11が決まればh1,h2,h3,w1,w2,w3から引き算で求まるので、4重のfor文で大丈夫。
実際のプログラム
#include<iostream>
#include<vector>
using namespace std;
int main(){
vector<int> h(3);
vector<int> w(3);
cin >> h[0] >> h[1] >> h[2];
cin >> w[0] >> w[1] >> w[2];
int ans = 0;
for(int m00 = 1; m00 <= 30; ++m00){
for(int m01 = 1; m01 <= 30; ++m01){
int m02 = h[0] - m00 - m01;
if(m02 <= 0){
continue;
}
for(int m10 = 1; m10 <= 30; ++m10){
int m20 = w[0] - m00 - m10;
if(m20 <= 0){
continue;
}
for(int m11 = 1; m11 <= 30; ++m11){
int m12 = h[1] - m10 - m11;
if(m12 <= 0){
continue;
}
int m21 = w[1] - m01 - m11;
if(m21 <= 0){
continue;
}
int m22_1 = h[2] - m20 - m21;
if(m22_1 <= 0){
continue;
}
int m22_2 = w[2] - m02 - m12;
if(m22_2 <= 0){
continue;
}
if(m22_1 == m22_2){
++ans;
}
}
}
}
}
cout << ans << endl;
return 0;
}
東京海上日動プログラミングコンテスト2022（AtCoder Beginner Contest 256）B - Batters
問題の要約
高橋君の代わりに次の問題を解くプログラムを作成せよ。
マス0、マス1、マス2、マス3の4つのマス目がある。はじめマスの上には何もない。
また、整数Pがあり、はじめP=0である。
正の整数からなる数列A=(A1,...,AN)が与えられるので、i=1,...,Nについて順番に次の操作を行う。
1.マス0に駒を1個置く。
2.マス上の全ての駒を番号がAi大きいマスに進める。言い換えると、駒がマスxにあればその駒をマスx+Aiに移動する。
ただし移動先のマスが存在しない(すなわちx+Aiが4以上になる)駒たちに関しては、それらを取り除いてPに除いた個数を加算する。
すべての操作を行った後のPの値を出力せよ。
制約
1<=N<=100
1<=Ai<=4
入力
N
A1 A2 ... AN
考え方
1,マス目が4つだけではなく、無限個あると考える。
2,1個目の駒はA1+...+AN、2個目の駒はA2+...+AN、となりN個目の駒はANとなる。
よって、Aiをvector<int> Aで管理し、後ろの方から和を取っていけばよい。
3,すべてのAについて4以上かどうかを判定し、4以上ならPを1増やせばよい。
実際のプログラム
#include<iostream>
#include<vector>
using namespace std;
int main(){
int N;
cin >> N;
vector<int> A(N);
for(int i = 0; i < N; ++i){
cin >> A[i];
}
for(int i = N-2; i >= 0; --i){
A[i] += A[i+1];
}
int P = 0;
for(int i = 0; i < N; ++i){
if(A[i] >= 4){
++P;
}
}
cout << P << endl;
return 0;
}
東京海上日動プログラミングコンテスト2022（AtCoder Beginner Contest 256）A - 2^N
問題の要約
Nが与えられる。2^Nを出力せよ。
制約
0<=N<=30
入力
N
考え方
1,C++にはx^yを計算するpow関数があるが、浮動小数点数型なので誤差が出る。
2,x^yを計算するmypow関数を自作する。
実際のプログラム
#include<iostream>
using namespace std;
long long mypow(long long x, long long y){
long long ans = 1;
for(long long i = 0; i < y; ++i){
ans *= x;
}
return ans;
}
int main(){
long long N;
cin >> N;
cout << mypow(2LL,N) << endl;
return 0;
}
