Search

Computer House Random
Computer House Random
  • Randomについて
  • ブログ
  • Project
  • 作品紹介
  • 部員紹介

AHCに参加してみた。

競プロ勉強

Haniwa
最終更新 2021/05/03

AHCとは?

AHCとはAtCoder Heuristic ContestのことでAtCoder社が開催するマラソン形式のコンテストです。マラソン形式とは答えが決まっておらず、少しでもスコアをより良いものにして、他の競技者とそのスコアで勝負すると言ったものです。この形式のコンテストはほとんど参加したことがないのですが、AHCはこれから定期的(1ヶ月に1回くらい?)開催されるらしく、レートもつくので試しに参加してみました。今から、問題の概要と僕が考えた方針とその結果について書いていこうと思います。

問題の概要

AHC001問題文リンク
簡単まとめると、10000✕10000の広告枠に依頼された広告の矩形領域を振り分けていく問題です。 広告主からは領域に入れて欲しい座標と希望の面積が与えられるます。 その希望座標を含むように、できるだけ希望面積に近くなるように矩形領域を提供するようなプログラム作成せよという問題です。 厳密にいうと嘘の部分もあるのですが大体はこんな感じです。

方針について

今回、僕は全ての広告を横または縦で切った領域に分けるという方針をとりました。 全く同じx座標,あるいはy座標に複数の希望された座標がある場合は切った方向と垂直に分けるようにしています。 何を言っているか分からないと思うので以下の画像のようになるようプログラムを組んだんだなーと思ってもらえたら十分です。

こんな分割の仕方をする会社に広告の掲示頼みたくないと思うの普通ですが、なんとこんな分割の仕方で要件の88%達成したことになります!
次はこのような分割を組み合わせていくコードを書きました。
このときに分割するラインの場所やそのラインの増加数をランダムに決め、結果が良くなったらそのデータを保存していくと言った方法をとりました。
この「結果が良くなったらそのデータを保存していく」といった方法を山登り法というので良ければ調べて見てください。
ちなみに実は焼き鈍し法(山登り法の派生)っぽく一定の確率でラインを減らすといったプログラムも実装したのですが結果が悪くなった(と思っていた)ので その結果は下のようになりました。(これ時間計測ミスっていてちゃんと直したらかなり点数が上がりました!)

結果

得点は45391057665点(およそ90%)で順位は565位/1389位でした。
僕のプログラムの結果が悪かった理由は空白の面積が大きすぎたところですね。 広告の希望面積の合計はちょうど広告を貼れる全体の面積(10000✕10000)にいっちするので空白が多いとそれだけ点数が下がることになります。
実際、トップ層の人達は空白面積が少なく、点数の最大値に対して99%以上の得点を出していました。(すごいですね!)

最後に

方針とか雑になりましたがマラソン形式のコンテストはこんな感じでした。
まあ、結果はあまり良くなかったですが楽しかったので、皆さんも良ければ参加してみてください!

新入生向けブログリレー2021

2021年度オンライン部活動説明
競技プログラミング 新歓ブログリレー2021 記事を共有
Avatar
Haniwa

ハニワです。

Computer House Random はパソコンによる創作活動を行っている大阪府立大学の部活動です

Avatar
Haniwa

ハニワです。

競技プログラミング 新歓ブログリレー2021 記事を共有

News

ICPC2020参加記

ICPC
pngn
2021/05/08

コンピュータハウスランダムってどんな部活?

【1日目】5分でわかるランダムのこと
NEGI
最終更新 2020/04/18

はじめまして、らんだむちゃんです!

自己紹介と最初の動画
らんだむちゃん
最終更新 2020/03/19

作品紹介

【18日目】難波駅構内をblenderで再現してみた

途中経過
うっかり侍
2021/08/31

【17日目】ウィルダネスアドベンチャー(?)

いつかリベンジする
クマイザサ
最終更新 2021/08/30

【16日目】CHICKEN NIGHTS

正直、すまんかった
Marcus
最終更新 2021/08/29

Tag Cloud

作品紹介 (48) 新歓ブログリレー2021 (46) 新歓ブログリレー2020 (37) 競技プログラミング (34) 新歓ブログリレー2022 (33) 雑談 (32) ゲーム (30) ゲーム制作 (24) 競プロ勉強会 (22) 作品展示リレー2021夏 (19)

最新の投稿

【38日目】OneDriveでファイルを管理して授業や部活で活用しよう!

オム大、クラウド1TBくれるってよ
Kwang
最終更新 2022/04/29

【37日目】受けループやらメタビートやらのすゝめ

(ゲームにおいては)人の嫌がることをするのが最も楽しい
クマイザサ
2022/04/28

【36日目】マイクラのMODパックで遊ぼう

MODパックの導入は難しそうって思ってない?
neuron
2022/04/27

【35日目】大阪公立大学 中百舌鳥図書館利用のススメ

かなり長め
Rikky
2022/04/26
READ MORE

関連記事


ICPC2020参加記

ICPC

Avatar

主客転倒について

コストの寄与を考える

Avatar

競プロのすすめ

そろそろ復帰したい

Avatar

競プロ成長録的なもの

精進しよう

Avatar

ARC120-F解説

ARC120 F

Avatar

新入生向けブログリレー閉会式

お疲れ様でした

Avatar

Random
Randomについて
ライセンス
Privacy Policy
お問い合わせ
部員専用サイト
Project
新入生向けブログリレー2022
作品展示リレー2021夏
競プロ勉強会
Web
らんだむちゃん
ブログ
作品紹介
LT会
グラフィック
DTM
タグ一覧
Copyright © 2020 Computer House Random
引用
コピー ダウンロード