JOI予選を４完＋部分点でAランク取れたのでJOI本選に行って来ました。 JOI本選通ってしまったということでそれまでの期間、意識高い顧問からの課題をこなす日々を過ごした。 一応自分でもAOJのVolume 5は全部解こうと目標立ててたのに結局４問ほど残ってしま…

Zig-Zag Numbers ■問題 2947や71946などの各桁が増加、減少、増加…およびその逆となってる数字をジグザグ数とする。 A以上B以下のMの倍数であるジグザグ数の個数を求めよ。 ■解法 制限が 1 A以上B以下はx以下のジグザグ数の個数をf(x)とすると、f(B) - f(A-1…

Cleaning Robot ■問題 部屋の盤面が与えられ、スタートからすべての汚れたマスを通るように移動するときの最小距離を求めろ。 ■解法 すべてのマスを通ってという巡回セールスマン問題のような問題だがスタートと各汚れとの距離は障害物があるため、先にBFSし…

方向音痴のトナカイ ■問題 教会と家の情報がn*mの盤面で与えられます。 トナカイは上下左右に直進しかできず、一度止まった家の上は通過できなくなります。 教会からスタートし、すべての家に訪れてまた教会に戻ってくるルートは何通りあるか求めよ。 ■解法 …

MooFest ■問題 直線上にいるN匹の牛の聴力と座標が与えられる。 異なる2匹の牛の座標の差の絶対値と聴力の大きい方を掛けたものをすべての組み合わせに対して求めその総和を出力せよ。 ■解法 すべての組み合わせを試す際、聴力に対して昇順ソートすることで…

Gather the Maps! ■問題 n人の子孫がそれぞれ宝の地図の断片を１枚ずつ持っています。 n人の日程はわかり、その日が暇な人同士なら誰かにその断片を渡すことができます。 誰かがすべての断片を手にするまでの最小の日数を求めなさい。 ■解法 誰かの断片を別…

Traveling by Stagecoach ■問題 m個の街がp本の道路でつながれている。 道路を利用するには券が必要で、移動にかかる時間は距離/券の数字だけの時間が掛かる。 また、券は１枚につき１回しか使えません。 あなたはn枚の券を持っていて街aから街bに行きたい時…

A. Team ■問題 3つの0か1がn個与えられて、1が2つ以上あるものが何個あるか求めよ。 ■解法 数えるだけ ■ソース #include <cstdio> #include <iostream> #include <algorithm> using namespace std; int main(void) { int n; cin >> n; int ret = 0; for(int i = 0; i < n; i++){ int c = 0</algorithm></iostream></cstdio>…

Rearranging Seats ■問題 r*cあるものを、それぞれ上下左右に移動させたとき場所がかぶることなく全て移動できるかどうか求める。 ■解法 すべてを上下左右に移動できるかどうかは、ある一点から上下左右に移動し、他のすべての点を通って最初の点に戻ってこ…

Patisserie ■問題 幾つかの円を任意の順番で並べたとき必要な幅の最小が箱の幅より小さいかどうかを求める。 ■解法 dp[直前に度の円を使ったか][使った円の集合]で横幅を求めて、それがはこの大きさより小さいかを判定する。 2円の中点を繋ぐ線分はr1+r2、2…

Princess, a Cryptanalyst ■問題 入力されたすべての文字列を部分文字列として含む最小の長さの文字列SSSを求める。 複数あったら辞書順で小さいものにする。 ■解法 SSSの後ろの10文字と、使ったかどうかをビットで表現したやつを引数に持たせてDPする。 使…

250 - EasyConversionMachine ■問題 'a'と'b'からなる２つの文字列の片方の文字列中の文字をk回交換したときに2つの文字列を等しくできるかどうかを調べる。 ■解法 異なる箇所の数の数えて頑張る。 ■ソース #include <cstdio> #include <cstdlib> #include <cmath> #include <climits> #includ</climits></cmath></cstdlib></cstdio>…

A - 宝くじ ■問題 購入した宝くじと当選結果の一致している数字の数を数えてそれに対応した順位を出力する。 ５つだった場合はボーナス数字があるかどうかで決める。 ■解法 一致しているものを数えるだけ やるだけ ■ソース #include<cstdio> #include<cstring> #include<cmath> #incl</cmath></cstring></cstdio>…

A - 大好き高橋君 ( Love me do ) ■問題 n個の単語でできた文が与えられて、指定された文字列が入力の中に何個あるか数える。 ■解法 単語が指定の文字列と同じか比較するだけ やるだけ '.'が最後についても良いことに注意する ■ソース #include<cstdio> #include<cmath> #in</cmath></cstdio>…

Circles Intersection ■問題 2つの円の中点の座標と半径が与えられる。 1つの円がもう一つの円の中にあるか、円周が交わっているかいないかという2つの円の関係を求める。 ■解法 2つの中点との距離hを求めて、 Br+h>Ar だったら円Aの中にBがある。 Ar+h>Br …

Maximum Sum Sequence ■問題 整数nとn個の整数が与えられます。 その中の連続する値の合計の最大値を求めなさい。 ■解法 累積和を求めて連続の前と後ろをループで全通り試す。 ■ソース #include<cstdio> #include<algorithm> using namespace std; int d[5005]; int main(void){</algorithm></cstdio>…

Treasure Hunt ■問題 幾つかの移動歩数と回転角度が与えられます。 座標(0,0)地点で北向きに立っている状態から移動歩数分前に進み、回転角度分右に（負の値なら左）向きます。 それを入力が"0,0"になるまで続けた時の座標の整数部分を答えなさい。 ■解法 移…

Stray Twins ■問題 もう一方と上下左右反対に移動する双子がいます。 二人の座標とデパートの情報が与えられた時二人が巡り合えるまでの最短距離を求めなさい。 最短距離が100以上になるときは"NA"と出力しなさい。 ■解法 現在の距離、2人のx,y座標を持たせ…

2011年のJOI本選問題を解いてみました。 １～３までは苦戦しながらも自力で行けましたが４，５はヒントを貰ったり色々して解きました。 実力がほしいのと解法の証明とかできるようになりたい。 □１問目 □２問目 □３問目 □４問目 □５問目 1.Planetary Explora…