Mujin Programming Challenge 2017"/>
Atcoder Mujin Programming Challenge 2017
颓废了一晚上系列,抄yjq系列
A - Robot Racing
時間制限 : 2sec / メモリ制限 : 256MB
配点 : 900 点
問題文
あなたはカエル型のロボットを開発しています。 あなたはこのロボットに競走をさせることにしました。
まず、あなたは数直線上に N 体のロボットを置きました。 ロボットには 1 から N までの番号が振られています。 今、i 番目のロボットは座標 xi にいます。 ただし、xi はすべて整数であり、0<x1<x2<…<xN が成り立ちます。
あなたは次の操作を繰り返し行います。
- 数直線上のロボットを一体選ぶ。 選んだロボットの座標を x とする。 座標 x−1, x−2 のうち他のロボットがいない座標を着地点に選ぶ。 選んだロボットを着地点へジャンプさせる。
あるロボットの座標が 0 以下になった場合、そのロボットはゴールしたと見なされ、即座に数直線から取り除かれます。 すべてのロボットがゴールするまで、あなたは操作を行い続けます。
あなたが操作を行う方法によって、N 体のロボットがゴールする順番は何通りかありえます。 N 体のロボットがゴールする順番は何通りありうるでしょうか?109+7 で割った余りを求めてください。
制約
- 2≤N≤105
- xi は整数である。
- 0<x1<x2<…<xN≤109
部分点
- 500 点分のテストケースでは、N≤8 が成り立つ。
入力
入力は以下の形式で標準入力から与えられる。
N x1 x2 … xN
出力
N 体のロボットがゴールする順番は何通りありうるか? 109+7 で割った余りを出力せよ。
入力例 1
3 1 2 3
出力例 1
4
3 体のロボットがゴールする順番は、次の 4 通りありえます。
- (ロボット1→ロボット2→ロボット3)
- (ロボット1→ロボット3→ロボット2)
- (ロボット2→ロボット1→ロボット3)
- (ロボット2→ロボット3→ロボット1)
入力例 2
3 2 3 4
出力例 2
6
3 体のロボットがゴールする順番は、次の 6 通りありえます。
- (ロボット1→ロボット2→ロボット3)
- (ロボット1→ロボット3→ロボット2)
- (ロボット2→ロボット1→ロボット3)
- (ロボット2→ロボット3→ロボット1)
- (ロボット3→ロボット1→ロボット2)
- (ロボット3→ロボット2→ロボット1)
例えば、次図のように操作を行うと、(ロボット3→ロボット2→ロボット1) の順にゴールします。
入力例 3
8 1 2 3 5 7 11 13 17
出力例 3
10080
入力例 4
13 4 6 8 9 10 12 14 15 16 18 20 21 22
出力例 4
311014372
答えを 109+7 で割った余りを出力してください。 なお、このケースは部分点のテストケースには含まれません。
yjq:对于所有可能第i个被假的棋子, 一定是所有棋子从第一个开始连续的某些棋子。
手推一下就好了。
B - Row to Column
時間制限 : 2sec / メモリ制限 : 256MB
配点 : 1300 点
問題文
縦 N 行、横 N 列の正方形状のマス目があります。 上から i 行目、左から j 列目のマスを (i, j) と表します。
最初、各マスは白か黒です。 最初のマス目の配色は、正方形状に並ぶ文字 aij (1≤i, j≤N) として与えられます。 マス (i, j) が白ならば aij は .
であり、黒ならば aij は #
です。
あなたは、マス目の配色を塗り替えるロボットを開発しています。 このロボットは次の操作を繰り返し行うことができます。
- 整数 i, j (1≤i, j≤N) をそれぞれ自由に選ぶ。 マス (i, 1), (i, 2), …, (i, N) の色をそれぞれ c1, c2, …, cN として記憶する。 その後、マス (1, j), (2, j), …,(N, j) の色をそれぞれ c1, c2, …, cN で塗り替える。
あなたの目標は、すべてのマスを黒にすることです。 すべてのマスを黒にすることが可能か判定し、可能ならば必要な操作回数の最小値を求めてください。
制約
- 2≤N≤500
- aij は
.
または#
である。
部分点
- 300 点分のテストケースでは、N≤3 が成り立つ。
入力
入力は以下の形式で標準入力から与えられる。
N a11…a1N : aN1…aNN
出力
すべてのマスを黒にすることが可能ならば、必要な操作回数の最小値を出力せよ。 不可能ならば、代わりに -1
を出力せよ。
入力例 1
2 #. .#
出力例 1
3
例えば、次のように操作を行うと、次図のようにマス目の配色が変わります。
- i=1, j=2 と選んで操作を行う。
- i=1, j=1 と選んで操作を行う。
- i=1, j=2 と選んで操作を行う。
入力例 2
2 .. ..
出力例 2
-1
入力例 3
2 ## ##
出力例 3
0
入力例 4
3 .#. ### .#.
出力例 4
2
入力例 5
3 ... .#. ...
出力例 5
5
yjq:
无解的情况显然是没有黑色格子。在有解情况下, 最优策略一定是先把某一行全部变成黑色,再用这一行去搞事情。
枚举是哪一行, 然后先看第i列有没有黑格子, 有的话就用这个格子来搞这一行所有的白格子, 不然就先随便把一个黑格子转到第i列, 再来搞。
就做完啦!
代码其实Atcoder是公开的
这是我把yjq的改了一下,我觉得更好看一点
#include<bits/stdc++.h>
using namespace std;
int n,ans=-1;
const int N = 505;
char mp[N][N];
bool br[N],bc[N],wr[N],wc[N];
bool flag = 0;
int main(){scanf("%d", &n);for( int i = 1; i <= n; i++ ){scanf("%s", mp[i]+1);for( int j = 1; j <= n; j++ )if( mp[i][j] == '#' ){ br[i] = bc[j] = flag = 1; }else wr[i] = wc[j] = 1;}if( !flag ){ puts("-1"); return 0; }for (int i = 1; i <= n; i ++) {int tmp = 0 ;if (!bc[i]) tmp = 1 ; for( int j = 1; j <= n; j++ )if( mp[i][j] == '.' )tmp++;for( int j = 1; j <= n; j++ )if( wc[j] ) tmp++;if( tmp < ans || ans == -1 ) ans = tmp ; }printf("%d\n", ans);return 0;
}
更多推荐
Atcoder Mujin Programming Challenge 2017
发布评论