オセロです
pythonで実行したらできると思います
バグってたらごめんなさい。その際、良ければどんなバグがあったか教えていただけると助かります。
def start(): global banmen,okenai banmen=[[-1 for i in range(8)] for j in range(8)] for i in range(1,9): for j in range(1,9): num=(i-1)*8+j if num<10: num="0"+str(num) else: num=str(num) banmen[i-1][j-1]=num banmen[4][4]="●" banmen[3][3]="●" banmen[4][3]="○" banmen[3][4]="○" print() for i in range(8): print_banmen="" for j in range(8): count=count_notturnkoma("○","●",i,j) if count>0 or banmen[i][j]=="○" or banmen[i][j]=="●": print_banmen+=banmen[i][j] else: print_banmen+="・" print_banmen+=" " print(print_banmen) print() control(0) def control(turn): print() if turn==0: print("白の順番です。打つ手の番号を入力してください。") te=input() if len(te)==2 and te[0] in num and te[1] in num and 1<=int(te[0])*10+int(te[1])<=64 and banmen[(int(te)-1)//8][(int(te)-1)%8]!="○" and banmen[(int(te)-1)//8][(int(te)-1)%8]!="●": ban_ope(turn,te) else: print("有効な番号を入力してください") control(turn) else: print("黒の順番です。打つ手の番号を入力してください。") te=input() if len(te)==2 and te[0] in num and te[1] in num and 1<=int(te[0])*10+int(te[1])<=64: ban_ope(turn,te) else: print("有効な番号を入力してください") control(turn) print() def ban_ope(turn,te): if turn==0: me="○" you="●" else: me="●" you="○" if te[0]=="0": te=te[1] te=int(te) i=(te-1)//8 j=(te-1)%8 if not 0<=i<8 or not 0<=j<8: print("適切な数値を入力してください") control(turn) return count=count_turnkoma(me,you,i,j) if count==0: print("有効な手を入力してください") control(turn) if count>0: banmen[i][j]=me okeru=0 anti_okeru=0 koma=0 for i in range(8): print_banmen="" for j in range(8): count=count_notturnkoma(you,me,i,j) if count>0 or banmen[i][j]=="○" or banmen[i][j]=="●": print_banmen+=banmen[i][j] else: print_banmen+="・" print_banmen+=" " if count>0 and not banmen[i][j]=="○" and not banmen[i][j]=="●": okeru+=1 if banmen[i][j]=="●" or banmen[i][j]=="○": koma+=1 anti_count=count_notturnkoma(me,you,i,j) if anti_count>0 and not banmen[i][j]=="○" and not banmen[i][j]=="●": anti_okeru+=1 print(print_banmen) if koma==64: print("対局終了！") finish() elif okeru==0: if anti_okeru==0: print("どっちも置けない！") print() finish() else: print("置ける場所がない！") print() ### for i in range(8): print_banmen="" for j in range(8): count=count_notturnkoma(me,you,i,j) if count>0 or banmen[i][j]=="○" or banmen[i][j]=="●": print_banmen+=banmen[i][j] else: print_banmen+="・" print_banmen+=" " print(print_banmen) ### control(turn) else: okenai=0 if turn==0: control(1) else: control(0) def count_turnkoma(me,you,i,j): count=0 temp=0 for k in range(1,i+1): if banmen[i-k][j]!=me and banmen[i-k][j]!=you: break elif banmen[i-k][j]==you: temp+=1 else: if temp!=0: count+=temp for l in range(1,k): banmen[i-l][j]=me break temp=0 for k in range(1,min(j+1,i+1)): if banmen[i-k][j-k]!=me and banmen[i-k][j-k]!=you: break elif banmen[i-k][j-k]==you: temp+=1 else: if temp!=0: count+=temp for l in range(1,k): banmen[i-l][j-l]=me break temp=0 for k in range(1,8-i): if banmen[i+k][j]!=me and banmen[i+k][j]!=you: break elif banmen[i+k][j]==you: temp+=1 else: if temp!=0: count+=temp for l in range(1,k): banmen[i+l][j]=me break temp=0 for k in range(1,min(8-i,8-j)): if banmen[i+k][j+k]!=me and banmen[i+k][j+k]!=you: break elif banmen[i+k][j+k]==you: temp+=1 else: if temp!=0: count+=temp for l in range(1,k): banmen[i+l][j+l]=me break temp=0 for k in range(1,j+1): if banmen[i][j-k]!=me and banmen[i][j-k]!=you: break elif banmen[i][j-k]==you: temp+=1 else: if temp!=0: count+=temp for l in range(1,k): banmen[i][j-l]=me break temp=0 for k in range(1,min(8-i,j+1)): if banmen[i+k][j-k]!=me and banmen[i+k][j-k]!=you: break elif banmen[i+k][j-k]==you: temp+=1 else: if temp!=0: count+=temp for l in range(1,k): banmen[i+l][j-l]=me break temp=0 for k in range(1,8-j): if banmen[i][j+k]!=me and banmen[i][j+k]!=you: break elif banmen[i][j+k]==you: temp+=1 else: if temp!=0: count+=temp for l in range(1,k): banmen[i][j+l]=me break temp=0 for k in range(1,min(i+1,8-j)): if banmen[i-k][j+k]!=me and banmen[i-k][j+k]!=you: break elif banmen[i-k][j+k]==you: temp+=1 else: if temp!=0: count+=temp for l in range(1,k): banmen[i-l][j+l]=me break return count def count_notturnkoma(me,you,i,j): count=0 temp=0 for k in range(1,i+1): if banmen[i-k][j]!=me and banmen[i-k][j]!=you: break elif banmen[i-k][j]==you: temp+=1 else: if temp!=0: count+=temp for l in range(1,k): pass #banmen[i-l][j]=me break temp=0 for k in range(1,min(j+1,i+1)): if banmen[i-k][j-k]!=me and banmen[i-k][j-k]!=you: break elif banmen[i-k][j-k]==you: temp+=1 else: if temp!=0: count+=temp for l in range(1,k): pass #banmen[i-l][j-l]=me break temp=0 for k in range(1,8-i): if banmen[i+k][j]!=me and banmen[i+k][j]!=you: break elif banmen[i+k][j]==you: temp+=1 else: if temp!=0: count+=temp for l in range(1,k): pass #banmen[i+l][j]=me break temp=0 for k in range(1,min(8-i,8-j)): if banmen[i+k][j+k]!=me and banmen[i+k][j+k]!=you: break elif banmen[i+k][j+k]==you: temp+=1 else: if temp!=0: count+=temp for l in range(1,k): pass #banmen[i+l][j+l]=me break temp=0 for k in range(1,j+1): if banmen[i][j-k]!=me and banmen[i][j-k]!=you: break elif banmen[i][j-k]==you: temp+=1 else: if temp!=0: count+=temp for l in range(1,k): pass #banmen[i][j-l]=me break temp=0 for k in range(1,min(8-i,j+1)): if banmen[i+k][j-k]!=me and banmen[i+k][j-k]!=you: break elif banmen[i+k][j-k]==you: temp+=1 else: if temp!=0: count+=temp for l in range(1,k): pass #banmen[i+l][j-l]=me break temp=0 for k in range(1,8-j): if banmen[i][j+k]!=me and banmen[i][j+k]!=you: break elif banmen[i][j+k]==you: temp+=1 else: if temp!=0: count+=temp for l in range(1,k): pass #banmen[i][j+l]=me break temp=0 for k in range(1,min(i+1,8-j)): if banmen[i-k][j+k]!=me and banmen[i-k][j+k]!=you: break elif banmen[i-k][j+k]==you: temp+=1 else: if temp!=0: count+=temp for l in range(1,k): pass #banmen[i-l][j+l]=me break return count def finish(): kuro=0 siro=0 for i in range(8): for j in range(8): if banmen[i][j]=="○": siro+=1 if banmen[i][j]=="●": kuro+=1 print() print(" 結 果 発 表 ") print() print(" ○... ",siro) print(" ●... ",kuro) print() if siro>kuro: print(" ○白の勝ち！！ ") if siro<kuro: print(" ●黒の勝ち！！ ") if siro==kuro: print(" 引 き 分 け ") exit() num=["0","1","2","3","4","5","6","7","8","9"] start()
take911のAHC008
こんにちは
take911です。福井大学で物理をやってる人です。AtCoderは2019年9月からはじめ、それ以来ゆるゆる参戦しています。アルゴのレートは執筆現在828で緑🌳レートです。
マラソン、僕は結構楽しいと思っています。その楽しさをピコ単位でも皆さんに伝えられたら僕は嬉しいです。時はAM2:54。夜食を喰らいながら、ゆっくり書いていこうと思います。この記事が公開される日は来るのかな？
対象は、まったくわからないレベル ～ コンテスト200位あたり を想定しています。1桁、2桁の順位を取った人からすれば、かなり退屈に感じる記事かもしれません。どちらかと言えば新規参入者を増やしたい気持ちで書いている記事ですので、そのあたりはご勘弁をお願いしたいことと、正直僕が書ける精いっぱいはこれくらいなので、重ねてご勘弁をお願いしたいなと思っています。
問題概要
30×30のオフィス内に従業員とペットがいる。できるだけペットを排除し、広い空間を確保すると得点が高い。
従業員一人の得点はざっくり、
定数×(その従業員のいる部屋の広さ)÷2^(その部屋の中のペットの数)
で与えられます。ペットの数により指数関数的に得点は減少することに注意する必要があります。なので基本的には、何もしないよりも部屋を分割したほうが得点が高くなります。
例：広さ450, ペット5の部屋は、広さ900, ペット10の部屋より 2^4倍 得点が高い
なので、中央の位置に縦に1本線を引くだけでも点は上がります。
全従業員の得点の平均が、そのケースでのスコアとなります。
また、ペットは5種類いて、それぞれ移動方法が異なります。
牛：ランダムに1マス移動
豚：ランダムに2マス移動
うさぎ：ランダムに3マス移動
犬：ある標的の人に向かって移動したあと、ランダムに1マス移動
猫：ある標的のマスに向かって移動したあと、ランダムに1マス移動
ランダムな移動は、移動可能なマスの中で選ばれます。移動可能なマスがない場合、移動しません。
また、犬、猫は標的にたどり着くと、ランダムに標的を選び直します。その際、到達不可能な標的は選ばれません。
以上は僕が雑に砕いて書いたルールです。詳細で正確で、かつ公式なルールを以下に貼ります。
とりあえず最終結果と、最終結果の解法を
結果はこれです。
提出者数934人中185位、得点は1ケース平均で29,144,898点でした。1613パフォで、今回初めてヒューリスティックで水コーダーになりました。
以下の動画はこの解法をビジュアライズしたものです。
動きとしては、
１．人を事前に決めた置き始めの位置に移動させる。
(16,5),(16,11),(16,17),(16,23),(16,29)の5つのマスを置き始めの位置としました。人数は5~10人なので、mod5を使えば人数が変わってもうまく分けられます。
２．30×2の縦長空間をぐるっと回りながら柵を設置していく。
shining_tileとかいう名の30×30の二次元配列を持っておきます。光っています。事前に障害物を置く場所は決めてあり、置く場所であればその位置の要素を１, そうでなければ０として判定をしていました。少し下スクロールしていただくとドット絵があります。そのドット絵でこの色をしているところが配列shining_tileで１にした部分であり（一部例外あり、上からしか置けないところは２、下からしか置けないところは３）、障害物を設置するところです。
光り輝くタイルの上にまだ障害物が置かれていなければ普通に障害物を設置するのですが、光り輝くタイルの上に障害物はないけれど動物が居たりして置くことができない場合は、移動せずそのマスで待機する仕様にしました。こうすると、ぐるりと1週回るだけで部屋を作り終えることができ、はやいです。
３．”シガンシナ区”に全員集結。ただし、一人を調査兵団として壁外へ...
そう、ここは進撃の巨人パートです。わかりにくいかと思いますので、ドット絵を入れておきます。このドット絵の色と、以下の記述で文字に付けている色は対応しているので、ぜひ絵を見ながら読んでみてください。
配置は、一人(調査兵団とします)を壁の外の(30,30)に、それ以外(駐屯兵団とします)を壁の扉の目の前に配置します。犬(巨人)は人に向かって進んでいくので、巨人は灰色の範囲、壁の扉の位置、調査兵団の位置、駐屯兵団の位置、のいずれかを動き回ることになります。まあ、だいたいは灰色の範囲にいます。巨人がすべて壁外にいるとき扉を封鎖すれば、壁内に巨人がおらず、巨人と人の住み分けができるようになり、作戦は成功です。え、壁外にいる調査兵団は...？...健闘を祈ります。多分リヴァイです、多分。扉を閉じられないときというのは壁の扉の位置、駐屯兵団の位置や、その隣接するマスに犬がいるときですが、それらのマス数は少ないので、数十ターンもあれば実現できることが多かったです。
４．通路を左右移動しながら、動物の入った部屋を閉めていく
ここも、ドット絵を添えておきます。
壁内に残った人たちは、通路を等間隔で移動してもらいます。その移動の際、その人のいるマスが黄色のマスの隣であり、かつその部屋の中にペットがいれば障害物を置きました。
以上の手順でペットを分離し、できるだけ広い部屋を作りました。
解法はわかった。で、どう実装するのん？
ここまで読んでいただいた方、ありがとうございます。これ以降は細々とした実装の話を書いていくので、次回のコンテスト前にちょっと覗きに来るとか、コンテスト中にチラ見しに来るとかでも超嬉しいのでそんな感じで。
とりあえず提出コードを貼ります。が、1000行を超えているしごちゃごちゃしているので全然見なくても大丈夫です。
全部は書けないので、主要かなと感じるところを選んで書いていきます。もし求めているところの説明がなければ、ここのコメントやtwitterなどで言っていただければ追加で書くかもしれません。
基本データの管理
field=[[[] for i in range(30)] for j in range(30)] N=int(input()) pet_place=[] for _ in range(N): pi,pj,pt=map(int,input().split()) pi-=1 pj-=1 field[pi][pj].append(pt) pet_place.append([pi,pj,pt]) M=int(input()) human_place=[] for _ in range(M): hi,hj=map(int,input().split()) hi-=1 hj-=1 field[hi][hj].append(7) human_place.append([hi,hj]) shining_tile=[[0 for i in range(30)] for j in range(30)]
僕は人やペットや障害物の位置関係を二次元配列に書き入れ、直感的に見たかったため、最初の入力をペットと人の配列、二次元配列であるfield配列の両方に入れています。ペットはその番号、人は7、障害物は9です。二次元配列の各要素を配列にしないと、人がいるところにペットが入ってきたとき人の番号である7がペット番号に上書きされ、エラーの元になるため注意が必要です。何人かに聞くと、二次元配列に人やペットを焼き直している人は僕だけだったので、ややマイナーな置き方かもしれません。人やペットの移動は、その都度fieldの配列から取り出し、移動先に追加することによって実現しました。
目的地の決め方
goal=[] for i in range(M): goal.append([15,6*(i%5)+4])
これは初期の目的地（最終結果の解法の１．で説明した部分）の決め方です。目的地を設定したい場合は、このgoal配列に目的地を入れれば完了です。
移動できるかの判定
def walker(i,j,ti,tj): if j<tj and (field[i][j+1]==[] or field[i][j+1][0]!=9): j+=1 return [i,j,"R"] if i<ti and (field[i+1][j]==[] or field[i+1][j][0]!=9): i+=1 return [i,j,"D"] if i>ti and (field[i-1][j]==[] or field[i-1][j][0]!=9): i-=1 return [i,j,"U"] if j>tj and (field[i][j-1]==[] or field[i][j-1][0]!=9): j-=1 return [i,j,"L"] return [i,j,"."]
i, j は現在いる座標、ti, tjは目的地の座標です。現在地と目的地を入れるだけで、自動で移動先を返してくれるので、この関数はかなり便利でした。欠点は、移動先を右上、左上、右下、左下の４つで返すため、壁の裏にある目的地に回っていくような場合は使い物になりません。ただ、今回の僕のプログラムではそのような動きはないため、これで十分です。基本的には、先ほどのgoal配列に目的地を入れ、この移動の関数がそれをti, tjとして読み込むことで、目的地を決めるところから目的地への移動までの動きは完成します。
障害物を置くべき場所かどうかの判定
def neighbor_checker(i,j,seed,m): #(i,j)の周囲4マスについて、輝くタイルがあれば文字を出力 elif seed==3: li=[] if i>0 and field[i-1][j]==[] and shining_tile[i-1][j]==1: li.append([i-1,j,"u"]) if j>0 and field[i][j-1]==[] and shining_tile[i][j-1]==1: li.append([i,j-1,"l"]) if i<29 and field[i+1][j]==[] and shining_tile[i+1][j]==1: li.append([i+1,j,"d"]) if j<29 and field[i][j+1]==[] and shining_tile[i][j+1]==1: li.append([i,j+1,"r"]) if i<29 and field[i+1][j]==[] and shining_tile[i+1][j]==2: li.append([i+1,j,"d"]) if i>0 and field[i-1][j]==[] and shining_tile[i-1][j]==3: li.append([i-1,j,"u"]) return li
配列shining_tileについて、周囲4マスのうち要素が1のマスがあれば、それは置くべき場所であるので、配列 li に追加します。ただし、要素が2なら上からしか置けず、要素が3なら下からしか置けません。この関数は、周囲4マスのうち、置くべき場所の位置と英小文字を入れた配列 li を返します。
障害物を置くことができるかの判定
def neighbor_checker(i,j,seed,m): #(i,j)に台を置くとき、その周囲4マスに ペット がいなければ 0 を出力 if seed==1: if i>0: for r in field[i-1][j]: if 1<=r<=5: return 1 if j>0: for r in field[i][j-1]: if 1<=r<=5: return 1 if i<29: for r in field[i+1][j]: if 1<=r<=5: return 1 if j<29: for r in field[i][j+1]: if 1<=r<=5: return 1 for r in field[i][j]: if 1<=r<=5: return 1 return 0
i, jに障害物を置きたいとき、そのマスと、その周囲4マスにペットがいると障害物を置くことができないため、その5マスについてのx, yについてfield[x][y]の要素にペットの番号が含まれていないかを確認します。
周囲に障害物を置くべきマスを残した状態で、移動するべからず
def neighbor_checker(i,j,seed,m): if seed==5: if i>0 and (field[i-1][j]==[] or field[i-1][j][0]!=9) and shining_tile[i-1][j]==1: return 1 if j>0 and (field[i][j-1]==[] or field[i][j-1][0]!=9) and shining_tile[i][j-1]==1: return 1 if i<29 and (field[i+1][j]==[] or field[i+1][j][0]!=9) and shining_tile[i+1][j]==1: return 1 if j<29 and (field[i][j+1]==[] or field[i][j+1][0]!=9) and shining_tile[i][j+1]==1: return 1 if i<29 and (field[i+1][j]==[] or field[i+1][j][0]!=9) and shining_tile[i+1][j]==2: return 1 if i>0 and (field[i-1][j]==[] or field[i-1][j][0]!=9) and shining_tile[i-1][j]==3: return 1 return 0
周囲を確認し、shining_tileが0でない（置くべき)であるにもかかわらず、そのマスのfieldが9でない（障害物が置かれていない)なら1を返し、移動させません。(この理由は最終結果の解法２．で説明済)
移動するか、障害物を置くかの判定について
ti=goal[m][0] tj=goal[m][1] #目的地の取り出し li=neighbor_checker(i,j,3,m) #周囲4マスに置くべき場所があれば li に入れる for f in li: # li の要素を順に取り出し、 #設置スイッチがオンであり、設置可能なら、 if put_sw[m] and neighbor_checker(f[0],f[1],1,m)==0: field[f[0]][f[1]].append(9) #fieldに9を入れ、設置 send += f[2] #提出用の配列に文字を追加 break else: #置かなかったなら #もし周囲に置くべきなマスがあるのに置かれておらず、 #かつ設置スイッチがオンなら if neighbor_checker(i,j,5,m)==1 and put_sw[m]: wli=[i,j,"."] #移動しない(最終結果の解法２．で説明済) else: #そうでなければ wli=walker(i,j,0,ti,tj) #ti, tjに向かい移動 i=wli[0] j=wli[1] #i, jを再設定
ここの部分は長くなるため、コードに直接コメントをしておきました。
部屋の中にペットが入っているかどうかの判定
def scan(J,seed): if J%3==1: if seed==0: for i in range(14): for j in range(J-1,J+1): for con in field[i][j]: if 1<=con<=5: return 1 return 0 if seed==1: for i in range(17,30): for j in range(J-1,J+1): for con in field[i][j]: if 1<=con<=5: return 1 return 0
着目する従業員の横の座標を J としています。部屋にペットが入っているか判断する段階では、従業員が（解法４．で述べた）水色の通路を移動しています。その様子をもう一度貼っておきます。
黄色のマスが中にペットがいれば閉じるマスです。Jがそのマスの隣に来た時（J%3==1)、上下の部屋の中のマスを全部探索して、ペットがいれば、閉じます。
まとめ
マラソンはガチで疲れます。リアルガチ。ただ、それを超えるだけのやりがいと楽しさを持っている競技だと僕は思います。忙しい生活をしていればなおさら手を伸ばしにくい競技かと思います。そんな方がこの記事を見てほんのちょっとでも面白そうと思ってくれたなら、僕はこれを書いてよかったなと感じられます。では、このあたりで失礼します。
