「JOI模擬予選的なもの」に参加して下さった皆さん、ありがとうございました！
tester用に作った問題文です
忍者のセキュリティの仕様がhogeで画像が表示されなかったり、３番の問題文が途中で切れってしまったりと、大変でしたがなんとか無事終えることが出来ました。
結果が良かった方は素直に喜んで下さい。
また、今回のものは「JOI予選」でも、増してや「JOI模擬予選」ですらないので、あまり思うようにいかなかった方も別に気にすることはありません！
例年のJOI予選通過レベルの目安はだいたい
- ３完＋そこそこの部分点
だと思っています。
４完ならば通ってもなんらおかしくないでしょう。
問題についてですが、見ていただければ分かると思いますが、かなり去年のJOI予選を意識して作っています。
過去問の復習をしていた人にとっては、応用力を問う問題セットになっていたのではないかと思います。
各問題のsolved数とfirst Acceptです。
- solved : 17 first : maruuusa83
- solved : 14 first : hogloid
- solved : 6 first : tozangezan
- solved : 3 first : hogloid
- solved : 7 first : tozangezan
- solved : 3 first : hogloid
以下は各問題に対する解説です。
１番「NPCA vs まるきゅう」
例年、JOI予選１番には
- 入出力ができるか
- 簡単な計算が出来るか
みたいなことだけを必要とする、簡単な問題が出ています。
ミスをしないように、あんまり時間を掛けないでサクッと解いてしまいましょう。
#include<cstdio> using namespace std; int main(){ int a, b, c, d; scanf("%d%d%d%d",&a,&b,&c,&d); printf("%d\n",a-b+c-d); return 0; }
↓これはダメです！問題文読みましょう！
x;main(){x=!puts("0");}
言ってる意味が分からない人はチルノの・・・を見ましょうw
２番「魔法女装少年 hiromuたん」
なのは？ なにそれおいしいの？
去年のJOI２番と非常に似ていますが、本質的な部分はちょっと違います。
あまり意識せずに解いた方が良いでしょう。
両方の魔法陣を回転させて調べていくと、O(n^3)になりTLEです。
なので、片方の魔法陣を固定してもう１つの魔法陣を回転させるだけで十分なことに気付かなければなりません。
これならばO(n^2)なので余裕で間に合います。
#include<cstdio> #include<algorithm> using namespace std; int main(){ int i, j, n, x, ans = 0; char a[1005], b[1005]; scanf("%d%s%s",&n,a,b); for(i = 0; i < n; i++){ x = 0; for(j = 0; j < n; j++){ if(a[j] == b[(j+i)%n]) x++; } ans = max(ans,x); } printf("%d\n",ans); return 0; }
文字列操作関連には多少なりとも知識が必要なので(文字コード、配列を余分にとる理由など・・・)、そのあたりは調べておきましょう。
３番「Mine is sweeper」
３番にしてはちょっと難しめです。
全探索などをするのは無理なので、うまい戦略を見つけなければなりません。
赤文字で強調してある、
「盤外に接しているマスには地雷が埋まっていることはない。」
という条件を活用しましょう！
とりあえず、「左からx個目、上からy個目」のマスを(x,y)と表すことにします。
まず、上の条件と、(1,1)のマスが 0 であることから、
下図の黄緑のマスには地雷がないことが分かります。
次に、(2,1)のマスが 1 なので、(3,2)のマスには地雷が必ず埋まっていることになりますよね？
地雷が埋まっているマスには、説明のために赤い色を塗っておきます。
後のことを考えて、地雷が埋まっているマスの「近く」のマスの数字をデクリメント（-1すること）しておきましょう。
同じようなことを、左上から右下に向かって順番にやっていくと、全てのマスの地雷の有無が分かります。
うまくいきましたね。
実装にも少し力が必要です。
#include<cstdio> #include<string> #include<algorithm> using namespace std; int m[50][50]; int main(){ int i, j, dw, dh, w, h; scanf("%d%d",&w,&h); for(i = 0; i < h; i++) for(j = 0; j < w; j++) scanf("%d",&m[i][j]); for(j = 0; j < w; j++) printf("0%c",(j==w-1)?'\n':' '); for(i = 0; i < h-2; i++){ printf("0 "); for(j = 0; j < w-2; j++){ if(m[i][j]){ printf("1 "); for(dw = 0; dw <= 2; dw++) for(dh = 0; dh <= 2; dh++) m[i+dh][j+dw]--; } else { printf("0 "); } if(j == w-3) puts("0"); } } for(j = 0; j < w; j++) printf("0%c",(j==w-1)?'\n':' '); return 0; }
行末の改行の前にスペースを出力しないように気をつけましょう。
４番「あくじのためにあみだしたくじ」
あみだくじの問題は、過去のJOI本戦でも出たことがあります。
問題にしやすいということですね^^
まず、「横棒を消す」という操作をそのままの意味でとらえるのではなく、「横棒に出会ったときに、その横棒を『使う』or『使わない』を選ぶ」というイメージでとらえた方が良いかもしれません。
「各横棒をに関して消すかどうかを決めてシミュレーションしてhoge...」とか言う方針だとO(2^m)とかになり、絶対に間に合わないからです。
そこで、DPの登場です。
基本的な方針としては、「ある高さである縦棒を辿っているときの『それまでに辿った横棒の本数』の最大値を計算していく」という感じです。
何が良いのかというと、（図の端が切れてたらスミマセン・・・）
ダイヤマークのところに辿り着くには、上の３通りの辿り方がありますが、
『それまでに辿った横棒の本数』は左の図から順に、0本、2本、4本です。
しかし、この問題においては最大値しか求める必要がないので、上図の左２つのような辿り方は考えなくてよいのです。
こういうものを効率的に排除することが出来れば良いのです。
それを実現するひとつの方法がDPです。
DPは素晴らしいアルゴリズムなので、知らなければ蟻の本などで是非勉強して下さい！
↓蟻の本
- 作者: 秋葉拓哉,岩田陽一,北川宜稔
- 出版社/メーカー: 毎日コミュニケーションズ
- 発売日: 2010/09/11
- メディア: 単行本（ソフトカバー）
- 購入: 52人 クリック: 1,402回
- この商品を含むブログ (80件) を見る
#include<cstdio> #include<algorithm> using namespace std; const int INF = 100000000; int dp[10001]; int main(){ int i, n, m, k, x, y; scanf("%d%d%d",&n,&m,&k); for(i = 0; i <= n; i++) dp[i] = -INF; dp[k] = 0; for(i = 0; i < m; i++){ scanf("%d",&x); y = max(dp[x],dp[x+1]+1); dp[x+1] = max(dp[x+1],dp[x]+1); dp[x] = y; } printf("%d\n",dp[1]); return 0; }
「dp[i]」に「今、左から i-1 番目の縦棒にいるときの『それまでに辿った横棒の本数』の最大値」を記録しながら一番下まで処理していっています。
O(n*m)では間に合わないので「メモリの再利用」をしましょう。
５番「超人的な太郎君のためのゲーム」
簡単すぎないか心配だった問題です。
というのも、実装は去年の５番よりも軽いので、『この問題が幅優先探索の問題であることに気付けるか』ということに全てがかかっていると思っていたからです。
どうなんでしょうか・・・気付けるものなんでしょうか・・・？
どうやら４よりは簡単だったようですね。
まずこの問題の構造を把握しましょう。
簡単に言うと、この問題はグラフに帰着することが出来ます。
具体的には
- 面が頂点
- 「ワープ土管」と「面クリア」が辺（コストは全て１）
- 1面からN面までの最短距離が答え
と、こんな感じです。
辺のコストが全て１なので、ダイクストラを使わずとも、幅優先探索でOKです。
#include<cstdio> #include<queue> #include<algorithm> using namespace std; typedef pair<int,int> P; int g[10001][101]; bool used[10001]; int main(){ int i, j, n, m; queue<P> q; P p; scanf("%d%d",&n,&m); for(i = 1; i < n; i++){ for(j = 0; j < m; j++){ scanf("%d",&g[i][j]); } g[i][m] = i+1; } q.push(P(1,0)); while(!q.empty()){ p = q.front(); q.pop(); if(p.first == n){ printf("%d\n",p.second); return 0; } if(used[p.first]) continue; used[p.first] = true; for(i = 0; i <= m; i++){ q.push(P(g[p.first][i],p.second+1)); } } return -1; }
また「5面→4面」のような、戻る方向の「ワープ土管」がないとすれば、DPのようなイメージでもうちょっとだけ簡単に解けます。
６面「超人的な太郎君のための遊具」
ぱない人にも楽しんでもらえるような問題にしたつもりです。
シンプルながら、なかなか難しい問題です。
まず、入力データをソートしても良いという
ことに気付きましょう。
ソートした入力データがこんな感じだったとしましょう。
大きい数字から順に見ていくと良さそうですね。
まずは、9,8の場所が確定しますね？
次は 7 ですが、7の入るマスの候補は２通りあります（オレンジのマス）。
どうしましょう？
しかし少し考えてみると、どちらのマスが 7 であっても状況はほとんど変わらないことが分かります。
ここでは仮に、左のマスが 7 だったとします。
次は 5 ですが、5 の入るマスは確定しますね？
さて、7の次が5だったので、6が飛びました。
6はどこのマスに入るでしょうか。
緑のマスには 7以下の数字ならばどんな数字でも入ることが出来ます。
逆に、オレンジのマスには 5以下の数字しか入りません。
よって6が入ることの出来るマスは、緑のマスのうち他の数字が入っていないマスとなります。（例の場合だと１マスしかありませんが、複数マスある場合もあります。）
あとは 4~1 ですが、４ヶ所に４つの数字を入れる組み合わせなので、4!ですね。
というわけで答えは、
9 : 1
8 : 1
7 : 2
6 : 1
5 : 1
4~1 : 4!
を掛け合わせたものなので、2*(4!) = 48 となります。
とこんな感じの方針になります。
階乗などを求めるのに一番時間がかかり O(W*H)くらいです。
#include<cstdio> #include<queue> #include<algorithm> #define fi first #define se second using namespace std; typedef pair<int,int> P; typedef long long ll; const ll mod = 1000000007; P p[2002]; int xy[2]; int main(){ int i, j, w, h, a, emp = 0, pre; ll ans = 1; scanf("%d%d",&w,&h); pre = w*h+1; for(i = 0; i < w; i++){ scanf("%d",&a); p[i] = P(a,0);} for(; i < w+h; i++){ scanf("%d",&a); p[i] = P(a,1);} sort(p,p+w+h+1,greater<P>()); for(i = 0; i < w+h; i++){ if(pre-p[i].fi-1 > emp || p[i].fi == p[i+2].fi || p[i] == p[i+1]){ puts("0"); return 0;} for(j = p[i].fi+1; j < pre; j++){ ans *= emp; emp--; ans %= mod; } if(p[i].fi == p[i+1].fi){ emp += xy[0]+xy[1]; xy[0]++; xy[1]++; i++; } else { emp += xy[!p[i].se]-1; xy[p[i].se]++; ans *= xy[!p[i].se]; ans %= mod; } pre = p[i].fi; } while(emp){ ans *= emp; ans %= mod; emp--;} printf("%lld\n",ans); return 0; }
コーナーケースに注意！（ありえない入力の場合など）
