2017 ICPC国内予選

参加しました。

チーム名はIQ94(由来は1994年生まれだから)

チームメンバー　hyksm ホハム(mtsd) polyomino

でした。

始まる前のチームとしての作戦は以下の通り。

hyksm :  (重そうな)実装担当

polyomino : 考察+実装

mtsd : 考察

要するに(私は使い物にならないので) hyksmとpolyominoで交互にコーディングしていこうという話でした。

各人の適正を考えるとこうするしかないという感じでした。
（要するに僕は考察でどうにか成果を出せということ）

では実際。

スタート直後、印刷をpolyominoが、hyksmがA問題をそのまま解き始める。

polyominoの印刷スピードは最速感があった。

最初の問題の割り振りは以下のようになった。

B問題:polyomino

C問題:mtsd

読んでるうちにAを通す。polyominoがBを解き始める。hyksmにC問題の概要を伝えると、「もっと後ろを解いて」とのこと。

とりあえず、全体の問題を流し読みして、F問題のような話は数学の問題として見たことがあったので自分が解きにいかないとという気持ちになる。

B問題polyominoが実装で微妙に詰まったらしく、hyksmにコーダー交代。先にCを解いてそのままBを解くという流れに。

その間にD,E,Fを2人で考えることに。

DはXORをとって0になるような選び方の最大値だよなぁと思ったがよくわからない。制約どうやって使うんだ？多分DPでしょ？ナップザック問題だけどbitDPは無理だな？？と分からない。

Eは論理変数も少ないし、文の長さが十分短いので全部先に列挙させればいいな、構文解析やればいいなという感じに。

A~Cを解いたhyksmと、polyominoがEをどっちが書くか相談。hyksmに一任。

あとの二人はDとFを考える。

Ｆは0-indexで始めると絶対見通しがいいと思って図をひたすら書く。一回折り曲げた後は重なった部分は同一視して～～とかいろいろ考えるも泥沼にはまっていく。2^3のパターンとかを書き始めるが、これで本当に分かるのか？と悩み始めツライ感じに。延々1時間半は悩む。

（shurikenがこうすりゃいいんじゃん！みたいなことを言っているのが聞こえてさらに心がやられる)

hyksmがEを通し、DとFをチーム全員で考え始める。とりあえずそれっぽいことをhyksmに適当に言ったら、（たぶん関係なく）hyksmが4分割すれば行けそう！と言い始めそのままコーディングへ。

polyominoとDを考え始める。2部グラフでどうにかする？無理そう、流石にＤじゃでないだろみたいな感じでやっぱDP系か～という感じに。変数としてpair<それまでの選んだ個数、XORした値>みたいなものを考えるんかなぁ～という話になり、もしかしてsetにバンバン追加してけばいいんじゃね！？という感じに。適当な（嘘）計算量解析によりなんか行けそう！とか適当に言ってみる。とりあえず紙コーディング。

ここらへんで上位陣が全部東大でひえぇ～～～～って思う。

F上手く行かないということになり、コードを印刷して、デバッグへ。その間にDを書き始める（残り30分切っていた）。

ついに僕がコーディングすることに。10行くらい書いたところでpolyominoが印刷から帰ってきたので交代。ペアコーディングに。一通り書ききって動かしたら止まらない。setの追加の位置がダメ→修正→string用に書いたXORがおかしい→修正→サンプル通る！

ギリギリのケースで間に合うか不安になるもとりあえずテストケースを投げる。やはり時間がかなりかかって焦る。

hyksmがFを修正しながら、後でDの答えが返ってくるのを待つ（残り15分くらい）。

D1個目通る！D2個目へ。hyksm怒涛のF修正！

D2個目もプログラムが終了！提出！Congratulation!!(2:50:59)

残り10分、Fの修正を見守る。なんかオーバーフローが起きている→1<<n を(ll)1 << n に修正→サンプルあってる！

テストケースを落として提出！Correct!もう一個提出！Congratulation!!(2:56:50)

終了～

結果 6完　11位（学内順位7/10)　　（学内予選酷すぎる）

shurikenチームはおめでとうございます。

結果、完全にhyksm様様でした。

F、チーム作戦的にも問題的にも自分が解けないといけない問題だったのにやらかしてしまって本当に悲しい。焦ってもいいことはないね。算数勢辞めます。

来年はhyksm神がいないので、もっと研鑽を積んで実装の鬼になろう（か他のプロを呼んできたい）と思います。

おまけ。

家に帰って最初にやったこと。

う～んｗ終わり！ｗ

AtCoder Grand Contest 017

参加しました。

A問題 Biscuits

ビスケットが入った袋がn個。i番目の中にはA_i個ビスケットが入っていて偶数個か奇数個食べたいときの袋の選び方はいくつかという問題。

偶数個入ってる袋と奇数個入ってる袋の個数をともに数えて、組み合わせを愚直に計算しました。

B問題 Moderate Difference

Nマスあって1番左のマスはA、1番右のマスはBである。隣り合う2つのマスの差がC~Dの間という条件で、数字を埋めることができるかという問題。

2つおきに見ていくとC+D間隔に山ができて、(D-C)*kの範囲の自由度が生じるのでそんな感じかな〜〜と思って実装しましたが、1ケースだけ落ちました。

C問題も書いては消してを繰り返し不毛に2時間溶かしました。おしまい。

順位　615位　パフォーマンス 1508 新レート 1936(-41)

2017年度ICPC模擬国内予選

そういえば、学科民3人で参加してました。

良いチーム名が思い浮かばず、1994年生まれという共通点から IQ94(1994)というチーム名に。

分担は以下のような感じになりました。

---解いた問題---

A問題 polyomino

B問題 hyksm

C問題 ほとんどhyksm (一応考察 +mtsd)

D問題 mtsd(書いてバグらせる人)  polyomino(それを怒る人)

E問題 hyksm 幾何ライブラリ (polyominoも一緒に考えてたはず)

---手を付けようとした問題---

G問題 mtsd polyomino （考察まで）

H問題 hyksm 

まあこんな感じでした。具体的にどんな感じでやったかは以下のような感じ。

13時半くらいに学科控室に集まる。polyominoと昼ごはんを買いにファミマへ。

控室に戻ったらhyksmも到着。昼ご飯を食べながら駄弁る。

13時50分くらいに慌てて環境を整えだす。

全員普段のエディタがバラバラ。いつもはsublime text使ってるけどまあpolyominoに合わせる。hyksmはvimを準備。

一応キーボードを持ってきていたのでちゃんと動くかチェック。macだったので若干変。まあ仕方なしといった感じ。

14時にページを更新するも問題が出ない。違うページ見てるか？と焦る。コンテスト延期の情報をTwitterで確認。

結局3時までだったのでダラダラ駄弁る。

結局開始までに特に作戦を決めず。最初に座ってたpolyominoにAを任せる。まあ通す。

その間にBとCをhyksmと読む。Bはとりあえず前から見ていけばいいねという感じ。Cは獲得しうる点数のmaxとminさえ見ておけばいいね、被ったらもう一方も見ようねという感じ。

結局二つとも実装をhyksmに投げて、その間にD問題を考える。

問題文の解釈に手こずる・・・　まあ2分探索だろうな～　これレベルの上げ方貪欲でいいの？という話に。

その間にhyksmが2問とも通す。流石、頼りになる男。

貪欲でいいことにようやく気付き、すかさず書いてやるぜ～とPCの前に。

普通に書くのに手こずる。安定の実装力。後ろでE問題はやるだけだとかHも解けるぞとか言われていて普通に焦る。

Dを一応書ききってテストケース実行。なんかおかしい、つらい。デバッグタイムへ。

polyominoと一緒にどこがおかしいのかを調べ始める。なんかいろいろヤバそうという話に。

その間にhyksmがH解けたというのでHを書いてもらう。

結局、2分探索のスタート範囲とかboolの条件がおかしいということが分かる。（頭がこんがらがっていてもうダメ）

H書き終わってテストケースも通ったとのことで提出。WA。よく聞いてみると勘違いしていた模様。悲しいね。

まあ気を取り直してD問題修正へ。上手く行ってそう。提出しよう！

提出用ケースを見るとanswerが-1ばかり。不安になって問題データを確認。回数制限がでかすぎるの多くない？ということで一応投げるかと提出。通りました(*^▽^*)

ここらへんで確か2時間くらい経過？

hyksmの持ってきた幾何ライブラリをフル活用でE問題を解きに行く。その間にF,Gを考える。
Fはグラフ関係のなにかだけどグラフはよく知らないしパス。Gは算数力が試されそうだしGやるぞ！という感じでGの考察へ。

まず許される状態を考えて、二人だけで閉じた関係の時だけ変なことが起きるんだなということが分かる。後は白丸、黒丸、仕切りの並び替え問題に帰着だ！という感じに。

まあE通した段階でもう間に合わなそうだなって感じになって終了。

順位を見てみると7位！E通したチームが少なかったのが影響したかという感じ。まぁF通したチームは多かったけど・・・

まあ本番は同じ大学のチームがまあ強い。はい。って感じになるんでしょうが。5問解けたらうれしいなって感じの目標で。

初の参加となりますが、チームワークが問われていて役割分担とか面白いですね。

僕は当日は実装することはやめて、頑張って実装を応援しようという感じになりましたとさ。（これで考察もボロボロだとただの置物になってしまう恐怖）

AtCoder Regular Contest 077

参加しました。

C問題 pushpush

長さnの数列{a_i}から、空の列bに対して以下の操作をn回行う。

1. a_i をbの末尾に追加

2. bを反転

bを出力しなさいという問題。

bを作ってみて対応するaのindexを書いてみると、

n,n-2,n-4...,0,1,3,5...,n-1

or

n,n-2,n-4...,1,0,2,4...,n-1

となるのでそれをもとにやりました。

D問題 11

1~nが少なくとも１つ含まれるn+1個の要素のある数列aに対して,

要素kの部分列（連続しなくてよい)は何種類ありますか？という問題。

1つだけかぶっているということは明らか。かぶっているのをpとする。

(aコ) p (bコ) p (cコ)

という感じの列のとき,普通に全パターンを取ってくると

(aコの中のいくつかから選ぶ) p (cコの中のいくつかから選ぶ)

というようなやつだけ2回ずつ数えているので,それだけ減算しました。

（コンビネーション書くのに時間をかけまくるという体たらくっぷり）

E問題はなんかimosやればいいんだろうなというところまではなんとなくわかったけど、上手くできずに終了。

順位 307位　パフォーマンス 1831 新レート 1977(-16)

算数ゲー来ないかなぁ（）

AtCoder Regular Contest 076

参加しました

C問題 Reconciled?

区別可能なN匹の犬とM匹の猿がいるので犬と猿が隣り合わないように直線に並べる方法は何通り(%1000000007)あるかという問題。

NとMの差の絶対値が2以上のときは不可能。

NとMの差の絶対値が1のときは多い方から交互に並べる場合のみ。

N=Mのときは、犬から始めても猿から始めても良い。

あとはN!とM!を求めましょう。おわり。

D問題 Built?

N個の街があって、街の座標(a,b)と(c,d)の間に道を作るには、

min(|a-c|,|b-d|)円がかかります。街同士を繋げて全ての街を行き来できるようにするには最低何円必要かという問題。

x座標とy座標でソートしたものを各々作り、隣り合う点同士に枝を貼って最小全域木を求めればよいです。

実装下手くそすぎて泣きかけた。

E問題 Connected?

長方形の内部（境界含む）に数字が1~Nが2つずつ含まれているとき、長方形の外部に出ずかつ曲線が交わらないように同じ数字を結ぶことができるかという問題。

数字つなぎとかそんな感じのパズルに近いが、適当に曲線を書いていいので本質的にはかなり違いそう。

境界上になければ、空間を歪める感じで、同じ数字を重ねあわせることができるので、数字がともに境界上にあるときだけを考えれば良い。

辺に沿うように、座標軸をとって、辺上で現れる順番に数字の列を作りました。

後は交わらないようになっているかを考えれば良い。

盲目的に再帰をやったけど、stackを使えばいいというのはそれはそうなので非常に悲しい。

終了1分半前にギリギリ通して一安心。

順位 159位 パフォーマンス 2138 レート1993(+18)

地道に黄色に戻していこう！（溶ける時は一瞬）

AtCoder Grand Contest 016

参加しました

A問題 Shrinking

長さNの文字列tを長さN-1の文字列t'に変える操作を考える。

t'[i]はt[i]かt[i+1]を選ぶ。

このとき、全部が同じ文字に成るようにする最低回数を求めよ。

最初の文字列のi番目の文字のみになるような時の最低回数は貪欲的にできるので、全部の文字についてやりました。

B問題 Colorful Hats

1~N匹の猫が色のついた帽子をかぶっている。

i匹目の猫から見ると他のN-1匹はa_i種類の色の帽子をかぶっているとする。

{a_i}が与えられた時そういうパターンは存在するかという問題。

とりあえず考察。

(1) a_iで出てきていい数字は2種類まで(3種類以上あると無理)

(2) 2匹が同じ帽子をかぶっていると必ずその色はすべての猫から見える

(3)a_iで出てくる数字がk,k+1のときkの方の猫は全て別の色の帽子をかぶっている

以上で無理な場合を弾いていけば解けました。

C問題 +/- Recrangle

H*Wの行列が以下を満たすようなものを構成しろ（無理ならNo)

・行列の全要素の和は正

・h*wの部分長方形を取り出しても要素の総和は負

貪欲にh行w列ごとに-hwを配置していけばいいんじゃね？というノリでやったら無事死にました。

H=1,W=3,h=1,w=2で落ちるようです。( 2, -3 ,2 とすれば良い）

全然気づかなかったのでもうダメ。

D問題 XOR Replace

問題文は結構面倒なので省略。

a1,a2,....,x　の値のセットは常に一定なので、末尾とのスワップのみでb1,b2....bnを作ることを考えました。

多分方針はあってるような気がするけど、時間も足りず終了（後半が本質らしいのでやっぱ無理）。

順位　275位 パフォーマンス　1996 レート1975(+2)

精進あるのみ。

AtCoder Regular Contest 075

参加しました

C問題 Bugged

N問の点数がs_iで定められているとき、10の倍数でないような最大の点数を求めよ。

無駄にDPをして1ケースだけ落としました。

D問題 Widespread

N体の魔物のHPがh_iとする。爆発魔法が使えて、1体にAのダメージ他の全員にBのダメージを与えられるとき、何回使えば全員倒せますかという問題。

回数について2分探索してしまえばよい。

とりあえず全員にBのダメージを与えて、後何回A-Bダメージを個別に与えるかを計算しました。

F問題　Mirrored

正の整数nに対して左右に反転させて得られる整数をrev(n)としたとき、

rev(N) = N+DとなるようなNはいくつ存在するかを求める問題。

rev(N)-N= (10^m-1)x_1+(10^(m-1)-10)x_2...

的なことを考えて上から順番に決めていく方針をとりました。

サンプルが通ったので投げたら半分くらいWA。どこがバグってるのか分からず。

C,D書くの遅かったけどF問題解けたっぽいし投げるか！というクソプレイングをした結果、爆死しましたとさ。良い子のみんなは真似しちゃだめだぞ！

427位　パフォーマンス 1452  新レート 1973(-48)

青くなりました　ﾁｬﾝﾁｬﾝ。