microbeの活動日記

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

日本情報オリンピック2017/2018 予選参加記

本選参加有資格者として参加しました.今年が最後のJOI予選になります.(高校から存在を知った人にはチャンスが2年しか残されてないの罠じゃないですか)

この記事は熊本高専Advent Calendar 11日目の記事も兼ねています.

 

結果

A,B,C,Eの4完 + D部分点で410点でした.3完で終わると思っていたので4完出来てうれしかったです.

 

解説

1問目 鉛筆(Pencils)

問題:
鉛筆をN本以上買うときにA本でB円のセットとC本でD円のセットのどちらかのセットのみをいくつか購入するときの必要な金額の最小値を求める.

方針:
やる
問題文をよく読むとどちらか一方のセットしか買うことができないことに注意する.

gist4cc34e3387c4d0dbae738baa0e552aa6

 

2問目 双六(Sugoroku)

問題:
スタートとゴールを除いて1と0から構成されるN個のマスがあるので,1のマスを踏むことなくゴール出来るサイコロのうち最も面の数が少ないサイコロを求める.

方針:
考察するのが面倒だったので全探索した.
面の数が小さいサイコロから見ていき,出る可能性のある面をすべて再帰で求めていきゴール出来たらそれが答え .計算量が怖いので1を踏んだらそれ以上は枝刈りした.

gist60247aaaa2a52c1e59dfdb998382e5aa

あとから考えたら1が最多くも連続している箇所さえ超えられればいいので最も多く1が連続している個数+1で求まると気付いた.

 

3問目 幹線道路(Trunk Road)

問題:

南北にのびるW本の道路と東西に延びるH本の道路があって各交差点に人が住んでいる.南北,東西にのびる道路のうちそれぞれ1本の計2本を幹線道路とするとき,各交差点から最も近い幹線道路までの距離の総和の最小値を求める.

方針:
どれを幹線道路にするかを決めて各交差点からの距離*各交差点に住む人数をすべての組み合わせにおいて全探索する.O(H^2 W^2)

gistdb0f1ff0fa9465a8fff11b23bf6a3c95

 

4問目 水ようかん(Mizuyokan)

すぐにDPだと察したので部分点(10点)だけとって逃げました.予選終わってから各プロが話してるの見て解いた.

問題:
N本の切れ目がある水ようかんをどこかの切れ目でいくつかに切った時の長さ最大のピースと最小ピースの長さの差の最小値を求める.

方針:
dp[i][j] := i本の切れ目までの切り方を確定し,長さ最大のピースがjであるときのこれまでの最小のピースの最大値.
Lの累積和をとっておくと切った区間の長さをO(1)で求められるので計算量が減る.別にしなくても十分通るだろうけど.

gist91fce8a135515b29a854b7616cc02090

 

5問目 森林伐採(Deforestation)

何とか時間内にACして100点.

問題:
H*Wのマスで森林が構成されていて木が生えていないマスのみ1マス移動するごとに1分で移動でき,木が生えているマスはそのマスに隣接したマスから1分かけて1本切ることができる.北西から南東まで移動できるようになるまでにかかる時間の最小値を求める.ただし,木を1本切るたびに北西まで1度戻らなければならない.

方針:
問題見た瞬間に最短経路問題に帰着できることに気づき,拡張Dijkstraっぽいことをする.
北西から(i,j)までの最小時間とそこまでに行くことができる最小のマス数を持たせておく.すると1本木を切って北西に持って帰るまでの時間も簡単に計算できる.
グラフを構成してもいいけどグリッドでそのままやったほうが考えるのも実装も楽そう.楽しかった.

gistce24420dd3dc1e39657bbc53c74eb421

 

6問目 L番目のK番目の数(LthKthNumber)

部分点も取れなかった

問題:
横一列にそれぞれ数が書かれたN枚のカードが並べられており,連続するK枚以上のカードの列すべてに対して次の操作を行う

  • 選んだカードを,書かれている整数が小さい順に左から並べる.
  • 並べたカードのうち,左から K 番目のカードに書かれた整数を紙に書き出す.
  • 選んだカードを,すべて元の位置に戻す.

これから書き出された整数を昇順に並べた時,L番目の数を求める.

方針:
わかんないや!(放棄)
プロたちによると二分探索でうまくやるといけるらしい.

 

感想

最初にも書いてますが,3完で終わると思ってましたが4完出来てうれしかったです.ただ問題の雰囲気が今までと少し違って感じたので少し戸惑いました.難易度的には僕の感覚では全然わからないですが5問目が楽しかったです.いい加減DP問題を本番中に解けるようになりたいなあ...
ボーダーもさまざまな情報が飛び交ってますが全然予想できなくて怖いですね.400以上は確定と願いたいんですが1度だけボーダー420の年があるので余計怖い.頼むから通っててくれ.

 

余談ですが景気付けにHHKBを購入しました.おかげで気分が高揚してます.

ガウスの消去法をC言語で実装

この記事は熊本高専Advent Calendar 8日目の記事です.

 

本日AdventCalendarに書く人がいなかったため,それを埋めるついでにガウスの消去法をC言語で実装したので紹介しようと思います.

 

ガウスの消去法とは

ガウスの消去法は,連立一次方程式を解くための多項式時間アルゴリズムになります.他に連立一次方程式の解を明示的に表すことができるものとしてクラメルの公式がありますが,クラメルの公式で大規模な問題を解こうとすると計算量が爆発してしまうためあまり計算機で解くことにおいてはおすすめしません.

ガウスの消去法は,前進消去と後退代入という2つの操作からなります.文字だけで見ると少し難しく感じてしまいますがアイデア的には中学数学レベルで解けるようなものでとても簡単です.

 

本当にその場しのぎみたいな記事で,詳しく解説する時間がなかったので詳しいところは以下のサイトを参考にしていただけると幸いです.

ガウスの消去法 - Wikipedia

 

ソースコード

gist2a2c29a2ae3da762f1cb226f9a7a8e10

 

 

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

 

 

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