SRM 444 Div1
試験的に図書館から参加．
22:00まで空いていると思いこんでいたけど，実際は21:30までらしい．
結果
Easy(250) 116.50pts
Medium(500) 371.19
Hard(1000) Opened
Easy
最初はO(N^4)で頑張ろうと思ったが実装ミスが怖くなったので，安全なO(N^5)のコードを書くことに．
結構時間を掛けてしまったが無事Accepted
実装(Visual Basic.NET)
Imports Microsoft.VisualBasic Imports System Imports System.Collections Imports System.Text Imports System.Collections.Generic Imports System.IO Imports System.Math Imports Weight = System.Int32 Public Class UnfoldingTriangles Dim W As Integer, H As Integer Dim MAP(50, 50) As Integer Public Function Check(ByVal X As Integer, ByVal Y As Integer, ByVal Size As Integer, ByVal Limit As Integer) As Boolean Dim yy As Integer = Y Dim xt As Integer = X Dim I as Integer For xx As Integer = X - Size + 1 To X If xt < 0 OrElse Y >= H Then Return False If (MAP(xt, yy) <> 2) Then Return False yy += 1 xt -= 1 Next '次に.を含まないか判定 'MsgBox("!") yy = Y Dim Cnt As Integer = 0 xt = X For xx As Integer = X - Size + 1 To X For i = yy + 1 To Y + Size - 1 If (MAP(xt, i) = 0) Then Return False If MAP(xt, i) = 2 Then Cnt += 1 Next yy += 1 xt -= 1 Next If Cnt > Limit Then Return False '周囲に1が無いかどうか For i = X - Size + 1 To X If MAP(i, Y + Size) = 1 Then Return False Next For i = Y To Y + Size - 1 If MAP(X + 1, i) = 1 Then Return False Next Check = True End Function Public Function Calc(ByVal X As Integer, ByVal Y As Integer, ByVal Limit As Integer) As Integer Dim Ans As Integer = 0 If MAP(X, Y) <> 2 Then Return -1 For Calc = 1 To 51 If (Check(X, Y, Calc, Limit)) Then Ans = Max(Ans, Calc) End If Next If Ans = 0 Then Return -1 Else Return Ans * (Ans + 1) / 2 End If End Function Public Sub DPrint() For i As Integer= 0 To H - 1 For j As Integer= 0 To W - 1 Select MAP(j, i) Case 1 'Debug.Write("#") Case 2 'Debug.Write("/") Case 0 'Debug.Write(".") End Select Next 'Debug.WriteLine("") Next i 'Debug.WriteLine("") End Sub Public Function solve(ByVal grid As String(), ByVal unfoldLimit As Integer) As Integer Dim i As Integer, j As Integer solve = -1 H = grid.Length W = grid(0).Length '0白 1黒 2斜め For i = 0 To H - 1 For j = 0 To W - 1 Dim T As Integer = 0 Select Case Mid(grid(i), j + 1, 1) Case "#" T = 1 Case "/" T = 2 End Select MAP(j, i) = T Next Next DPrint() For i = 0 To H - 1 For j = 0 To W - 1 solve = Max(solve, Calc(j, i, unfoldLimit)) Next Next End Function End Class
Medium
見た瞬間，4の個数を最大化するBitDPと気づいたが，
最初は前2列の状態を保存しておく必要があると思いこんでしまい，時間制限的な問題でC++で解くことにした．
最終的に書き終わってから保存する必要があるのは前1列+2個ということに気づき修正し提出．
実装(C++)
#include <vector> #include <list> #include <map> #include <set> #include <deque> #include <stack> #include <bitset> #include <algorithm> #include <functional> #include <numeric> #include <utility> #include <sstream> #include <iostream> #include <iomanip> #include <cstdio> #include <cmath> #include <cstdlib> #include <ctime> #include <cstring> using namespace std; #define REP(i,x) for(int i=0;i<(int)x;i++) class FourBlocks { public: int maxScore(vector <string>); }; int W,H; int MAP[10][25]; char dp[11][26][1<<14]; int solve(int x,int y,int forward){ if(dp[x][y][forward]>=0)return dp[x][y][forward]; //cout<<x<<","<<y<<";"<<forward<<endl; //置く場合 int nx,ny; int res=0; nx=x+1,ny=y; if(nx>=W)nx=0,ny++; if(ny==H)return 0; if(W-x>=2&&H-y>=2){ //置けるかどうか if((forward&1)==0) if(((forward>>1)&1)==0){ if(((forward>>W)&1)==0){ if(((forward>>W+1)&1)==0){ if(MAP[x][y]==0&&MAP[x+1][y]==0&&MAP[x][y+1]==0&&MAP[x+1][y+1]==0){ res=solve(nx,ny,(forward|1|2|(1<<W)|(1<<W+1))>>1)+1; } } } } } res=max(res,solve(nx,ny,forward>>1)); return dp[x][y][forward]=res; } int FourBlocks::maxScore(vector <string> grid) { W=grid.size(); H=grid[0].size(); memset(dp,-1,sizeof(dp)); REP(i,W)REP(j,H){ MAP[i][j]=grid[i][j]=='1'; } return W*H+12*solve(0,0,0); }
