参加記: AtCoder Beginner Contest 187
allegrogikenコンテストページ
感想
Dまでは30分間くらい楽しく解けて、Eで詰んだ
木構造をいい感じに作るのがわからなくて残り時間ずっと勉強してた・・
allegrogikenA - Large Digits
入力の値が3桁で固定されていてとてもやさしい。
文字列で受けて、各バイトから '0' 分を引く実装で済ませました。
コードゴルフめいた実装も遊びでやってみた
allegrogikenB - Gentle Pairs
苦戦してる人がそこそこいた印象。二次元座標系の問題は最近わりと多く出てる気がします。
線の傾きは y / x なのでそれを求めてやればいい・・のだけど、
今回は -1 <= 傾き <= 1 かどうかを判定するだけでOKなので、割り算を使わなくてもよい。
2点間の横、縦それぞれの距離(絶対値)を dx dy としておいて、 dy <= dx になるペアが対象になります。
計算量は
解説曰く、
提出
allegrogikenC - 1-SAT
制約より、 !!a みたいに!が2つ以上ついてるケースを想定する必要はないです。
登場した単語を Set かなんかで記憶しておきましょう。
!から始まる単語なら!を抜いたもの、!から始まらない単語なら!を先頭につけたものがすでに登場してるかチェックして、チェックにかかったらその文字を出力します。すべての単語でチェックをすり抜けたら satisfiable です。
サンプルケースには a !a の順序で不満な文字が入っていますが、 !a a と逆順で来るケースをテストしておくとより安心した提出ができます（しました）。
テストしなかったけど、 !から始まる同単語が2回以上登場するケースとかもかなー。
提出
D言語では組み込みの Set が無いので、連想配列のキーで実装することが多いです。
嫌いではないけど可読性がチト悪いので Set のテンプレート実装を書いておきたい（多分やらないやつ）
allegrogikenD - Choose Me
いつもの（？）高橋 vs 青木問題です。
問題文をよく読んで「演説の効能」を見極めるのが大事かなーと思いました。
問題を数式モデルにしてみる
初期状態を「どの町でも演説を行わない状態」として、演説を増やしていくことを考えます。
青木氏の得票数:
V_{a}
高橋氏の得票数:V_{t}
初期状態
高橋派の住民は演説が無ければ投票しませんが、青木派の住民はみんな青木氏に投票します。
V_{a} = \sum^{N}_{n=1} An
V_{t} = 0
新たに 町i
高橋氏が演説を行うと、住民の派閥に関係なくその町の全住民が高橋氏に投票してくれます。青木氏の票が下がって、高橋氏の票が増える・・ という構図になります。
V_{a} = V_{a} - A_{i}
V_{t} = V_{t} + A_{i} + B_{i}
この演説による
町
における演説の効能: i E_{i} = 2A_{i} + B_{i}
終了条件
「高橋氏の得票数 > 青木氏の得票数」となれば、それ以上演説する必要はありません。
V_{t} > V_{a}
問題を解く
ところで、高橋氏はあまり演説をしたくないので「演説回数を最小にしつつ選挙に勝ちたい」と考えます。なので、最小化した時に想定される演説回数を答える問題となっています。（実際、選挙の演説にはかなりのマネーがかかると思うのでとても現実的な問題ですね！）
こういうときには「効果が最も高い町から演説していく」という単純そうな狙いで十分です。貪欲法とかいうらしい。
さきほど「演説の効能」を数式モデルとして定義しました。この値で町をソートして効能が高いところから選び、終了条件を満たせばそこで終了です！
提出
コンテスト中のは汚かったので、少しきれいにした・・ 青木氏の初期得票数から効能分を引いていき、マイナスになったら終わり・・ という感じで数式を入れ替えた条件で実装してみました。
allegrogikenE - Through Path
完全に理解したら書く
allegrogikenF - Close Group
完全に理解したら書く