microbeの活動日記

プログラミングコンテストなどの活動を書いています

ABC078参加記

AtCoder Beginner Contest 078 - AtCoder

ABC078に参加しました.

 

結果

Dを無限にバグらせてギリギリ全完.悲しいね.

 

A

gist030d7267b1b582d853e49093d1b9886f

 

B

gistb59a376415083e6e1db7c67403f838d5

 

C

電卓を使ってサンプルに合うようにいじいじすると式が出てきます.

gist575773c7b7902a815e5e97d1fb9f71fa

 

D

みんな大好きmini-max法
O(1)解法が想定解らしいのですが,僕は天才ではないのでアルゴリズムで殴ることしかできません.

gistea5b66baae10a05b61a0b98e51bda1bc

 

 

こんなんでJOI予選通れるとは思えないのであと一か月無限に精進しなければなりませんね.

しかし後期中間試験まであと1週間しかないため精進する時間があまりとれないので悲しい…

男子高専生は女子高生なのか?

所属している学科にもよりますが,周りに女子が少ない,女子レベルが低い場合は,一番女子に近い存在である男子高専生が自動的に女子高生にランクアップするため男子高専生は女子高生であると言えます.ちなみに僕は女子高生です.

第28回高専プロコン参加記

今年,山口県周南市で行われた第28回全国高等専門学校プログラミングコンテストに競技部門の選手として参加してきました.

 

公式サイトはこちら

第28回大島大会(2017)

いきなりですが成績から

・1回戦(第4試合) 1位通過

・準決勝7位通過

・決勝16位(未完成)

 

1回戦はなんかピースの形がやばくてソルバーが動きそうになかったので配置情報を3つ使用して人力でした.反省してます.(帰ってからソルバー使って解こうとしたけどやっぱりむずかしかった)

準決勝は配置情報2形状情報1を使用してぎりぎり完成で7位

決勝は配置情報1形状情報1でいこうと思ったのですがまさかのソルバーがバグってしまいました.こんなこともあろうかともう1台PCを用意していたのですがUSBハブが不調で周辺機器がつながらず断念し,結局未完成に終わってしまいました.プログラムで負けるのならともかくバグや周辺機器の不調で通常通り競うことができずやりきれない気持ちで決勝を終えました.バグについては後述の反省で.

ソルバーに関しては,傾き・長さが合うものに優先順位をつけてマージさせていく貪欲アルゴリズムです.公開しようかと思いましたが決勝でバグるようなものなので恥ずかしく,公開しません.

 

反省

今回の反省は何よりメンバーと作業分担が出来なかったことです.僕以外のメンバーが4年生でインターンなどによりあまり部活にこれなかったというのもありますが,作業の分担は決めたものの,ほとんどの作業を僕1人でやっておりバグを直す時間が全く足りなくなってしまいました.結局のところは全て僕の責任なのでメンバーには申し訳ないばかりです.

 

これは少し愚痴のようになってしまい申し訳ないですが,僕の所属している部活は全体的に競技部門に対するやる気がほとんどないように感じられます.確かに去年のように完全に人力部門になってしまったようなこともありましたが,それを除いても部員全体の競技部門に対する意識が「課題・自由部門に落ちた時の逃げ道」というものになっているようです.別にそれでもいいのですが,競技部門に出るのであればちゃんとやらないと絶対に勝てません.やるからにはちゃんとやること.これはとても大事だと思います.

 

感想

競技部門に関しては反省することが多々ありますが,大会に参加することはとても楽しかったです.他高専の方と交流もできましたし,らてプロともお話できたので大満足です.個人的に競技部門が一番性に合っているので来年もぜひ競技部門に参加出来たらなと思います.

全列挙 : POJ2718,POJ3187,POJ3050,AOJ0525

蟻本に掲載されている問題

2718 -- Smallest Difference
3187 -- Backward Digit Sums
3050 -- Hopscotch
おせんべい | Aizu Online Judge

POJ2718

数を組み合わせて2つの整数をつくり,その差の絶対値の最小値を求める
std::next_permutationを使うと幸せになれる

gista2d834daff05f9c5c2e8181542d9b59c

 

POJ3187

パスカルの三角形的なもので最終的な和がsumになるような1~Nの並びを求める.
std::next_permutationなら辞書順に生成されるので幸せになれる

gist43f11673ba894460accdc05e188ceee3

 

POJ3050

BFS

gista17b044b1a0e70d86410c6f68290a3bb

 

AOJ0525

行と列を全列挙してると時間が足りないのでひっくり返す行さえ決まればあとは1がr/2より多いものをひっくり返せばいい.行だけの全列挙なら多くてもパターンは2^{10}程度で済む.

gist77ba324305ea5711bc61df08410e3d27

 

やっぱり実装力がないので悲しい

幅優先探索 : AOJ0558,POJ3009,POJ3669,AOJ0121

 蟻本に掲載されてる問題

チーズ | Aizu Online Judge
3009 -- Curling 2.0
3669 -- Meteor Shower

7 パズル | Aizu Online Judge

 

AOJ0558

今の地点から次の地点までをそれぞれBFS

gista68c9a4a9079e3fcb551c5396b4abff7

 

POJ3009

蟻本にはBFSって載ってるけどDFSのほうが楽そう

gist95359f3f435df4cdb2e4a5654bd9b316

 

POJ3669

現時点から行けるところへBFS

gistfbee62bee1c46c63732904490a7aded7

 

AOJ0121

01234567からいける最小回数をあらかじめ計算しておく

gist8cf6341ef52f40278177fcd94d059322

 

 

実装力皆無なのでかなしい
書き方に統一性がないけど昔のコードもあるので許して

 

深さ優先探索 : POJ1979,AOJ0118,AOJ0033

蟻本に掲載されてる問題

1979 -- Red and Black
財産分配 | Aizu Online Judge
玉 | Aizu Online Judge

 

POJ1979

w * hの赤いブロック('#')と黒いブロック('.'),始めの位置('@')の情報が与えられるので初め位置から赤いブロックを通らずに行くことが可能なブロックの数を求める
すでに行った場所を記録しながら探索

gist1b26b641b414b5d7ad4e3b7b75dee0a0

 

AOJ0118

すべての場所から探索を初めて探索した箇所が1箇所以上であればカウント
すでに行った場所は記録

gist7e91cefa0949a8d7a5d389759bdec287

 

AOJ0033

脳死

giste57fcf9d68c75f757fd3841c7dd1b67a

 

POJはいい加減C++11以上を使えるようにしてくれ

Typical DP Contest : C - トーナメント

C: トーナメント - Typical DP Contest | AtCoder

 

問題概要

2^{k} 人でトーナメントが行われるのでそれぞれが優勝する確率を求める.
ただし,PとQが対戦してPが勝つ確率は1/(1+10^{(RQ-RP)/400})とする.

 

方針

確率DP
dp[i][j] := i回戦目でjが勝つ確率
PとQが対戦するかどうかの判定が難しかった...

 

ソース

gist19a47ee2cc462ea31dac94d13fe0f2cb