"プレゼント" AtCoder Beginner Contest 038 D

D - プレゼント

解法
最長増加部分列(LIS)の問題として解きました。
実装は蟻本の63~65ページを参考にしています。
まずは箱の幅で昇順にソート、幅が同じ箱どうしでは高さの降順にソートします。
そして高さのみを考えてLISを求めれば答えが出ます。
dp[i]は、「長さがi+1であるような増加部分列における最終要素の最小値」で、dpは最初全部の要素が114514。
heightを前から見ていき、二分探索でheight[k]をdpのどこに挿入できるかを探してdpを更新していく。
これを最後までやると、箱をi+1重にできる場合はdp[i]が114514より小さくなっているので答えがわかる。

# ABC038D
import bisect
N = int(input())
hako = []

for k in range(N):
    hako.append(list(map(int, input().split())))

hako = sorted(hako, key = lambda x: (x[0],-x[1]))
height = []
for k in range(N):
    height.append(hako[k][1])

dp = [114514] * (N+1)
for k in range(N):
    dp[bisect.bisect_left(dp, height[k])] = height[k]

ans = 0
for k in range(N+1):
    if dp[k] < 114514:
        ans = k+1
print(ans)

"埋め立て" AtCoder Regular Contest 031 B

B - 埋め立て

解法
深さ優先探索の典型的な問題。実装は蟻本を参考にしました。
関数dfsはまずスタート位置を"x"にして、スタート位置から移動できる先が"o"ならそこをスタート地点にしてまたdfs、という再帰になっています。
(x,y)のコマを埋め立てたときに島が一つになっている場合は、dfs(x,y)が終わると地図が全部"x"で埋まります（島が一つでない場合は"o"が残る）。これを関数checkでチェック。
スタート地点は10*10箇所しかないので全部試す。

# ARC031B
import copy
field = []
for p in range(10):
    field.append([str(x) for x in str(input())])
 
temp = copy.deepcopy(field)
 
dx = [1,0,-1,0]
dy = [0,1,0,-1]
 
 
def dfs(x,y):
    temp[x][y] = "x"
    for p in range(4):
        nx = x + dx[p]
        ny = y + dy[p]
        if 0<=nx<10 and 0<=ny<10 and temp[nx][ny]=="o":
            dfs(nx,ny)
    return
 
 
def check():
    for p in range(10):
        for q in range(10):
            if temp[p][q] == "o":
                return False
    return True
 
 
for p in range(10):
    for q in range(10):
        temp = copy.deepcopy(field)
        dfs(p,q)
        if check() == True:
            print("YES")
            exit()
print("NO")

"魔法使い高橋君" AtCoder Regular Contest 053 C

C - 魔法使い高橋君

解法
（公式解説の通りにやっただけです）
a<bの魔法はリストu（upperの頭文字）に、a>=bのはリストdに入れていく。
dはaの値が小さい順に、uはbの値が大きい順にソートする。
あとは題意通りに温度を上げ下げしてmaxをとって答え。

// ARC053C
N = int(input())
u = []
d = []
 
for p in range(N):
    a, b = map(int, input().split())
    if a < b:
        d.append([a,b])
    else:
        u.append([a,b])
 
d.sort(key = lambda x: x[0])
u.sort(key = lambda x: x[1], reverse = True)
 
t = 0
ans = 0
for x in d:
    t += x[0]
    ans = max(ans, t)
    t -= x[1]
for x in u:
    t += x[0]
    ans = max(ans, t)
    t -= x[1]
 
print(ans)

"謎の人物X" AtCoder Regular Contest 023 B

B - 謎の人物X

解法

実験するとこんな感じになる。左上を1行1列目として一般化すると
i行j列目にD回の移動で行けるのは、i+j<=Dかつ、i+jとDの偶奇が一致する場合。
それぞれのマス目でこの条件を満たすか調べて、満たすもののmaxをとったのが答えになる。

// ARC023B
#include <bits/stdc++.h>
#define REP(i,n) for(int i = 0; i < (int)(n); ++i)
using namespace std;

int main(){
    int R, C, D;
    cin >> R >> C >> D;
    vector< vector > board(R,vector(C,0));
    REP(i,R){
        REP(j,C){
            cin >> board[i][j];}}
    int ans = 0;
    REP(i,R){
        REP(j,C){
            if(i+j<=D && (i+j)%2==D%2) ans = max(ans, board[i][j]);}}
    cout << ans << endl;
    return 0;
}

"AtCoderでじゃんけんを" AtCoder Regular Contest 048 B

AtCoderでじゃんけんを

解法：
配列RとHには、それぞれi番目の人のレートと手を入れていく(0 <= i < N)。
ヴェクターVに各レート・各手の人数を記録する。
レートの小さい方から人数の累積和を取っていく。S[i]はレートがi以下の人数。
出力するときは配列RとHを見ていって、i番目の人の場合は
勝ち数：自分よりレートの低い人の数（S[R[i]-1]）+ 自分と同じレートかつ手で勝てる人の数(V[R[i]][(H[i]+1)%3])
負け、引き分けも同様。

// ARC048B
#include <bits/stdc++.h>
#define REP(i,n) for(int i = 0; i < (int)(n); ++i)
using namespace std;
int R[100001], H[100001];
vector< vector > V(100001, vector(3,0));

int main() {
    int N;
    cin >> N;
    REP(i,N){
        cin >> R[i] >> H[i];
        H[i]--;
        V[R[i]][H[i]]++;}

    vector S(100001,0);
    for(int i = 1; i < 100001; i++) {
        S[i] += S[i-1] + V[i][0]+V[i][1]+V[i][2];}

    REP(i,N){
        cout << S[R[i]-1] + V[R[i]][(H[i]+1)%3] << " " << N - S[R[i]] + V[R[i]][(H[i]+2)%3] << " " << V[R[i]][H[i]] - 1 << endl;}

    return 0;
}

"経路" AtCoder Beginner Contest 037 D

経路

解法
解答のpdfがまだなかったため、ACされた方のコードをいくつか読んで参考にさせてもらいました。
深さ優先検索だけだとTLEになってしまったのでdpという配列を作ってメモ化再帰にしました。
あるマスについて上下左右に進めるかをチェックして進める場合はそこからまた上下左右をチェックして……、という再帰になっていて、調べ終わったら配列dpに記録します。
既に探索した場所ならば配列dpに記録してあるので、その値を返します。
入力例1に対応するboardは
0 0 0 0 0...
0 1 4 5 0...
0 2 4 9 0...
0 0 0 0 0...
............
という風にして、端のマスからは進めないようにしてから各マスを出発点としてdfsをしています。

// ABC037D
#include <bits/stdc++.h>
#define REP(i,n) for(int i = 0; i < (int)(n); ++i)
using namespace std;
int board[1002][1002];
long long dp[1002][1002];
long long mod = 1000000007;
int H, W;
 
void shokika(){
    REP(i,1002){
        REP(j,1002){
            board[i][j] = 0;}}
}
 
long long dfs(int i, int j){
    if(dp[i][j]) return dp[i][j];
    long long temp = 1;
    if(board[i][j] < board[i][j+1]) temp += dfs(i,j+1);
    if(board[i][j] < board[i+1][j]) temp += dfs(i+1,j);
    if(board[i][j] < board[i][j-1]) temp += dfs(i,j-1);
    if(board[i][j] < board[i-1][j]) temp += dfs(i-1,j);
    return dp[i][j] = temp % mod;
}
 
int main() {
    int H, W;
    cin >> H >> W;
    shokika();
    for (int i=1; i<=H; i++) {
        for (int j=1; j<=W; j++){
            cin >> board[i][j];}}
 
    long long ans = 0;
    for (int i=1; i<=H; i++) {
        for (int j=1; j<=W; j++){
            ans += dfs(i,j);}}
 
    cout << ans % mod << endl;
    return 0;
}

"派閥" AtCoder Beginner Contest 002 D

派閥

解法
知り合い関係をbool g[12][12]で記録（n番とm番が知り合いならg[n][m] = g[m][n] = true）。
それぞれの議員について、以下のように「その議員を入れた派閥で最大のものの人数」を求めていく。
派閥をvectorで表して、
1. まず議員を一人vに入れる（この人を含めた派閥で最大のものを考える）。
2. まだチェックしていない議員について、派閥全員と知り合いならその人を派閥に入れる。
3. 2を繰り返す。
各議員についてこれを繰り返して、vが一番長かったときの長さを答えとしています。
計算量はN^2。

// ABC002 D
#include <bits/stdc++.h>
#define REP(i,n) for(int i = 0; i < (int)(n); ++i)
using namespace std;
bool g[12][12];

int main(){
    int N, M;
    cin >> N >> M;
    REP(i,M){
        int x, y;
        cin >> x >> y;
        x--; y--;
        g[x][y] = true; g[y][x] = true;}

    int ans = 0;
    REP(i,N){
        vector v;
        v.push_back(i);
        REP(j,N){
            int l = v.size();
            int c = 0;
            for(int i = 0; i < v.size(); i++) {
                if(g[v[i]][j]) c++;}
            if(c == l){
                v.push_back(j);}}
        if(ans < v.size()) ans = v.size();}
    cout << ans << endl;
    return 0;
}