AtCoder Regular Contest 083

参加しました。

 

C問題 sugar water

100aか100bの水を入れる、もしくはcかdの砂糖を入れるを繰り返してf以下の重さの最も濃い砂糖水を作れ(ただし、100に対してeしか砂糖は溶けず溶け残りがあってはいけない)という問題。

 

不等式をきちんと立ててa,bのありうる値を全部やればいい。

0gの砂糖水は僕は存在すると思います(1WA)

 

D問題 Restoring Road Network

N個の都市があり、N*Nの行列Aが与えられた時、Au,vが都市uから都市vへの最短距離に成るような構造はありますかという問題。あったら道の長さの総和の最短を計算せよ。

 

u,vに対してAu,v=Au,w+Aw,vみたいなwが存在したらその時点でu,v間に道はなくていいねという感じ。N<=300なのでu,v,w全部について試して、可能な限り道を消す。

その後、作ったグラフに対してワーシャルフロイドをして、本当に行列Aのようになっているか確認すれば良い。

 

E問題 Bichrome Tree

もうなんか面倒なので問題の内容省略。

各頂点について(Xi,Yi)みたいな感じのものでYiが最小に成るものを計算し、ナップザックに帰着しました。

バグらせました。

for(int i=n;i>=1;i++){

 

直したら通りました。はいさようなら。

 

179位 パフォーマンス2071 レート1987(+10)

 

来週こそ黄色へ

 

Atcoder Regular Contest 80

参加しました。

 

C問題 4-adjacent

長さNの a=(a_1,a_2,...,a_N) の数列を並び替えて隣り合う数の積が4の倍数になるようにできるかを判定せよという問題。

 

4の倍数がp個、4の倍数でないが2の倍数であるものがq個とすると、

2*p+1>=Nかq+2*p>=Nなら達成できるのでそれを書くだけ(適当に並べればいい)。

 

D問題 Grid Coloring

縦H横Wのマスと色iで塗りたいマスの数a_iが与えられたときに、同じ色は連結であるような塗り分け方を一つ求めろという問題。

 

1行目の一番左から順に折り返すように色を塗っていけばいい。

 

E問題はsegtreeを始めて書きました(バグらせました)

 

以上。

 

225位 パフォーマンス1993 レート1977(+1)

減らなかったのでオーケー

AtCoder Regular Contest 079

参加しました。

C問題 Cat Snake and a Voyage

N個の島にM種類の定期船があって1とNをつなぐ定期船がないとき、2種類の定期船を使って1からNへ行けるか判定する問題。

 

1と直接つながっているかとNと直接つながっているかを調べて、どっちともつながっていたらPOSSIBLE。そうでなければIMPOSSIBLE。

 

D問題 Decrease (Contestant ver.)

長さNの非負性数列{a_i}に対し、数列の最大値がN-1以下になるまで以下の操作を繰り返し行う。

・数列の最大の要素を1つ選んで、この要素を-N。それ以外を+1。

ちょうどK回で操作が終わるようなNと数列{a_i}の組を一つ求めよ。という問題。

 

Kの値がむちゃくちゃでかいので構成は簡単にできるんだろうなと思った。

とりあえず1回につき全体の和は-1されていくのでその方針で考えていくことに。

m,m,...,mに対してN回操作を行うと、m-1,m-1,...,m-1になるので、この方針で考えた。

全ての操作後、n-1,n-1,...,n-1に成るような数列を考える。n=50とする。

まずn-1+k/n,n-1+k/n...,n-1+k/nにして残った回数k%n回について逆操作を順にやっていけば出来上がり。(制約条件に引っかかって1WA)

 

E問題 Decrease (Judge ver.)

D問題の逆で、数列が与えられた時に操作回数Kを求める問題。

 

a_iについて他の項は考えず何回Nを引けばN-1以下になるかv_iを計算。その和をSとする。

そのような操作を全部やると、

a_i = a_i - v_i*N + (S-v_i)

これをS=0になるまで繰り返した。

 

F問題はまあグラフの操作ができないマンでした。

 

順位 84位 パフォーマンス 2486 レート 1976(+77)

 

黄色チャンスですね!(m期ぶりn回目)

Atcoder Grand Contest 18

参加しました。


A問題 Getting difference

箱にN個のボールがあって各ボールにはA_iという数字が書いてある。以下の操作を行って数字Kが書いてあるようなボールを箱に入れることができるか?

・箱から二つボールを取り出して、その差の絶対値を書いたボールと共に箱に戻す

 

問題文をまず誤読して、箱から取り出したボールはもう使えないのかと最初思っていました。

最初に、{A_i}の最大値よりもKが小さいかどうかチェック。

{A_i}の最大公約数を調べて、Kがその倍数なら作れます。

終わり。

 

B問題以降は消え去りました。完。

 

順位531位 パフォーマンス1516 新レート1899(-37)

 

レートがみるみる溶けていくぅ~~~

 

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を考える。

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

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

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

polyominoとDを考え始める。2部グラフでどうにかする?無理そう、流石にDじゃでないだろみたいな感じでやっぱ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神がいないので、もっと研鑽を積んで実装の鬼になろう(か他のプロを呼んできたい)と思います。

 

 

おまけ。

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

f:id:mtsd_programming:20170715134707j:plain

 

う~んw終わり!w

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問解けたらうれしいなって感じの目標で。

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

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