yokobuttonの不定期で競技プログラミングをするブログ

不定期で解けた競技プログラミングコンテストの問題を載せています。

「ゼロからのOS自作入門」をHyper-Vで動かしたときのメモ

「ゼロからのOS自作入門」を読んで作成した自作osを、Hyper-Vで動かしたときに難しかったところをメモしておきます。ACPI PMタイマまで作成しましたが、USBドライバ、windowなど作成していない機能もあります。 まずはブート可能なイメージファイルを作成す…

C++でRange Coder(桁上がりなし)

C++

・高速な算術圧縮を実現する「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++でプログラミングしてみました。 テストをあま…

平面性テストと埋め込みのプログラム

// an implementation of the hopcroft and tarjan planarity test and embedding algorithmを参考に平面性テストと埋め込みのプログラムを作成しました。// 入力 : 頂点数n,辺数mの単純無向グラフG// 出力 : Gが平面的ならばPLANARと頂点数n,辺数mの平面的…

東京海上日動プログラミングコンテスト2022(AtCoder Beginner Contest 256)D - Union of Interval

問題の要約実数L,Rに対して、L以上R未満からなる次数の集合を[L,R)と表す。このような形で表される集合を右半開区間という。N個の右半開区間[Li,Ri)が与えられる。これらの和集合をSとする。Sを最小の個数の右半開区間の和集合として表せ。 制約1<=N<=2*10^51…

東京海上日動プログラミングコンテスト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列…

東京海上日動プログラミングコンテスト2022(AtCoder Beginner Contest 256)B - Batters

問題の要約高橋君の代わりに次の問題を解くプログラムを作成せよ。 マス0、マス1、マス2、マス3の4つのマス目がある。はじめマスの上には何もない。また、整数Pがあり、はじめP=0である。正の整数からなる数列A=(A1,...,AN)が与えられるので、i=1,...,Nにつ…

東京海上日動プログラミングコンテスト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(lon</iostream>…

NOMURA プログラミングコンテスト2022(AtCoder Beginner Contest 253)D - FizzBuzz Sum Hard

問題の要約1以上N以下の整数であって、Aの倍数でもBの倍数でもないものの総和を求めよ。 制約1<=N,A,B<=10^9 入力N A B 考え方1,1からNの総和を求める。これはN*(N+1)/2で求めることができる。2,上の数からAの倍数の総和を引く。Aの倍数の総和はN/A*(N/A+1)/…

NOMURA プログラミングコンテスト2022(AtCoder Beginner Contest 253)C - Max - Min Query

問題の要約整数の多重集合Sがある。はじめSは空。Q個のクエリが与えられるので順に処理せよ。クエリは次の3種類のいずれか。 ・1 x:Sにxを1個追加する。 ・2 x c:Sからxをmin(c,(Sに含まれるxの個数))個削除する。 ・3:(Sの最大値)-(Sの最小値)を出力。この…

NOMURA プログラミングコンテスト2022(AtCoder Beginner Contest 253)B - Distance Between Tokens

問題の要約H行W列のマス目があり、そのうち二つの異なるマスに駒が置かれている。マス目の状態はH個の長さWの文字列S1,...,SHで表される。Si,j=oならばi行目j列目のマスに駒が置かれていることを、Si,j=-ならばそのマスには駒が置かれていないことを表す。一…

NOMURA プログラミングコンテスト2022(AtCoder Beginner Contest 253)A - Median?

問題の要約整数a,b,cが与えられる。bがこれらの整数の中央値であるかどうか判定しろ。 制約1<=a,b,c<=100 入力a b c 考え方1,bがaとcの間であればよいが、これだけではa<=c,c<aの2通りあるので、c<aの場合aとcの値を交換する。2,a<=cなので、a<=bかつb<=cならばbは中央値。 実際のプログラム#include<iostream> using namespace std; int main(){ int a,b,c; cin >> a >> b >> c; if(a > c){ s</aの2通りあるので、c<aの場合aとcの値を交換する。2,a<=cなので、a<=bかつb<=cならばbは中央値。>…

AtCoder Beginner Contest 252 C - Slot Strategy

問題の要約N個のリールからなるスロットがある。i番目のリールの配列は文字列Siによって表される。ここでSiは0,1,...,9がちょうど1回ずつ現れる長さ10の文字列。それぞれのリールには対応するボタンがついており、各非負整数tについて、スロットが回り始めて…

AtCoder Beginner Contest 252 B - Takahashi's Failure

問題の要約T君の家にN個の食品があり、i番目の食品のおいしさはAi。また、T君には嫌いな食品がK個あり、具体的にはi=1,2,...,Kについて、Bi番目の食品が嫌い。T君はN個の食品のうち、おいしさが最大の食品から1つを選んで食べようと考えている。T君が嫌いな…

AtCoder Beginner Contest 252 A - ASCII code

問題の要約英小文字a,b,...,zのASCII文字コードはこの順に97,98,...,122。97以上122以下の整数Nが与えられるので、ASCII文字コードがNであるような英小文字を出力せよ。 制約Nは97以上122以下の整数 入力N 考え方1,そのまま整数をcharにキャストすればよい。…

パナソニックグループプログラミングコンテスト2022(AtCoder Beginner Contest 251) C - Poem Online Judge

問題の要約ポエムオンラインジャッジ(以下POJ)は提出された文字列に得点をつけるオンラインジャッジ。POJにN回の提出があった。早い方からi番目の提出では文字列Siが提出されて、得点はTi。(同じ文字列が複数回提出される場合もある)ただし、POJでは同じ文字…

パナソニックグループプログラミングコンテスト2022(AtCoder Beginner Contest 251) B - At Most 3 (Judge ver.)

問題の要約おもり1,おもり2,...,おもりNのN個のおもりがある。おもりiの重さはAi。以下の条件を満たす正整数nを良い整数とよぶ。 ・3個以下の異なるおもりを自由に選んで、選んだおもりの重さの和をnにすることができる。W以下の正整数のうち、良い整数は何…

パナソニックグループプログラミングコンテスト2022(AtCoder Beginner Contest 251) A - Six Characters

問題の要約英小文字からなる文字列Sが与えられる。Sの長さは1以上かつ3以下。Sを繰り返して得られる文字列であって、長さが6のものを出力しろ。 入力S 考え方1、Sの長さが1、2、3のそれぞれでどうなるか考える。 Sの長さが1のとき->Sを6個つなげる。 Sの長さ…

「ゼロからのOS自作入門」でMinGW-W64用のUEFIプログラムを書いてみた

この記事は、「ゼロからのOS自作入門」という書籍はLinuxとEDK2とClangで書かれているのですが、そのプログラムをWindowsとgnu-efiの一部とMinGW-W64で書いてみたという記事です。ようやく第4章が終わったので、参考として、そこまでのソースコードを記事に…

Windows10でのMinGW-w64とgnu-efiのヘッダーを使ったUEFIプログラミング

Windows10でMinGW-w64とgnu-efiを使ったUEFIプログラミングがしたかったので、「hello world」を表示させるところまでの手順を載せます。注意としては、gnu-efiの一部のファイルだけを使っているので、gnu-efiの関数を使えるかはわからないです。 1.7-Zip.ex…

AtCoder Beginner Contest 246 C - Coupon

問題の要約 N個の商品がある。i=1,...,Nについて、i番目の商品の値段はAi円。 今、K枚のクーポンを持っている。 1枚のクーポンは1つの商品に対して使用することができ、1つの商品に対してはクーポンを何枚でも(0枚でもよい)使用することができる。 値段がa円…

AtCoder Beginner Contest 246 B - Get Closer

問題の要約 二次元平面上の点(0,0)から点(A,B)に向かって距離1だけ移動する。 移動後の座標を求めよ。 なお、制約より点(0,0)と点(A,B)の距離は1以上であることが保証される。制約 入力は全て整数 0<=A,B<=1000 (A,B)≠(0,0)入力 A B出力 移動後の点を(x,y)と…

AtCoder Beginner Contest 246 A - Four Points

問題の要約 xy平面上に長方形がある。この長方形の各辺はx軸またはy軸に平行であり、面積は0ではない。 この長方形の4つの頂点のうち異なる3つの頂点の座標(x1,y1),(x2,y2),(x3,y3)が与えられるので、残る1つの頂点の座標を求めよ。制約 -100<=xi,yi<=100入…

AtCoder Beginner Contest 245 D - Polynomial division

問題の要約 N次多項式A(x)とM次多項式B(x)がある。 それらの積をC(x)=A(x)B(x)とする。 A0,...,ANおよびC0,...,CN+Mが与えられるので、B0,...,BMを求めよ。 ただし、与えられる入力に対して、条件を満たすB0,...,BMがただ一つ存在することが保証される。制約…

AtCoder Beginner Contest 245 C - Choose Elements

問題の要約 長さNの整数からなる数列A=(A1,...,AN),B=(B1,...,BN)が与えられる。 以下の条件を全て満たす長さNの数列X=(X1,...,XN)が存在するかを判定しろ。 ・すべてのi(1<=i<=N)について、Xi=AiまたはXi=Bi ・すべてのi(1<=i<=N-1)について、|Xi-Xi+1|<=K …

AtCoder Beginner Contest 245 B - Mex

問題の要約 長さNの整数からなる数列A=(A1,...,AN)が与えられる。 A1,...,ANに含まれない最小の非負整数を求めよ。制約 1<=N<=2000 0<=Ai<=2000入力 N A1 ... AN考え方 1,vector<bool>でAiが含まれるかどうかを管理する。 2,vector<bool>を0から確認していけば最小の非負</bool></bool>…

AtCoder Beginner Contest 245 A - Good morning

問題の要約 高橋君がA時B分ちょうどに、青木君はC時D分1秒に起きた。 高橋君の起床時刻が青木君より早いならばTakahashiを、そうでないならばAokiを出力しろ。制約 0<=A<=23 0<=B<=59 0<=C<=23 0<=D<=59入力 A B C D考え方 1,単純な条件分岐でよい。 AがCよ…

AtCoder Beginner Contest 244 D - Swap Hats

問題の要約 1,2,3の番号が付いた3人のT君がおり、赤・緑・青の色がついた3種類の帽子がそれぞれ1つずつある。 それぞれのT君は帽子を1つかぶっており、T君iがはじめにかぶっている帽子の色は文字Siで表される。 ここで、Rは赤、Gは緑、Bは青に対応している。…

AtCoder Beginner Contest 244 C - Yamanote Line Game

問題の要約 T君とA君は2人で次の対戦ゲームをする。 T君が先手でゲームを始め、ゲームが終了するまでの間、2人は交互に1以上2N+1以下の整数を1つずつ宣言する。 どちらかが一度でも宣言した整数は、それ以降どちらも二度と宣言することは出来ない。先に整数…

AtCoder Beginner Contest 244 B - Go Straight and Turn Right

問題の要約 xy平面を考える。x軸の正の向きを東向き、y軸の正の向きを北向きとする。 はじめ、点(x,y)=(0,0)にいて、東を向いている。 SとRのみからなる長さNの文字列T=t1t2...tNが与えられる。i=1,2,...,Nの順番で下記を行う。 ・ti=Sならば、いま向いてい…

AtCoder Beginner Contest 244 A - Last Letter

問題の要約 英小文字からなる長さNの文字列Sが与えられる。Sの末尾の文字を出力せよ。制約 1<=N<=1000入力 N S考え方 1,c++の場合、文字列をstringで受け取って、N-1の文字を出力する。 実際のプログラム#include<iostream>#include<string> using namespace std; int main(){ </string></iostream>…