最近出たコンテストの感想まとめ

まとめます。

 

1/13 第4回ドワンゴからの挑戦状 58位

歩きながらEを考えてたら解けちゃったので急いで机に向かってコーディングしました。実装下手過ぎて泣きました。最後CじゃなくてD解きに行けばよかったかもなぁ・・・

 

1/14 Atcoder Grand Contest 020 344位 

bitset高速化ほげぇ・・・

 

2/10 みんなのプロコン 2018 予選 37位

Cが出来そうになかったのでE問題を見たら有名定理っぽかったのでググって解きました。
まさかの予選通過。

 

2/11 第2回RCO日本橋ハーフマラソン 予選 38位

初のマラソンコンテスト参加。

A問題 適当に盤面選んでそれだけでやればそこそこ行くんじゃね?提出⇒1位!?!?
最終的にはA問題は9位まで落ちました。それでもビックリ。

B問題 何もわかりませんでした。

A問題のおかげでまさかの予選通過。去年の順位形式だとやばかったかも。

 

2/17 HACK TO THE FUTURE 2018 予選 70位

適当に貪欲で焼きなましでいいんじゃね?→なぜかスコアが出ない。上位陣何やってんだ???

indexが逆でした。分かり辛すぎる。そこそこ良いスコアが出ましたが、家族団欒の旅行中だったので途中で終了。もうちょっと頑張りたかったな。

ただ、貪欲の最中に高さを適当に調整するという脳がなかったのでもう頑張れなかったかも。

 

2/24 みんなのプロコン 2018 本選 30位

会場が高くてすげーって思いました。上位陣は完全に知り合いっぽくて結構居場所に困りました。懇親会?で電通大の人とお話しました。たまたま知り合いがいたのもちょっとびっくりしました。はい。

コンテストはまあ構成ゲーで構成するの楽しかったですね。ホウジョハバグバグ。

 

2/24 Atcoder Grand Contest 021 87位

A問題ちょっと不安になってB問題から手を付ける。

B問題は適当に大きな正100角形を作ってボロノイ図の面積を計算するコードを貼り付けました。どう動いてるかは知りません。

A問題は普通にやるだけでした。

C問題通している人が少なかったのとなんかバグらせそうだったのでD問題を考えました。
回文判定的なやつか~という気持ちになって区間DPかなと思ったらすぐ解けました。やったね。

C問題はどうせ3*3を含む感じのが例外だろうとは思いましたが実装方針が立たなかったので終了。

 

これにてまとめ終わり。

CODE FESTIVAL 2017 Final (Parallel)

参加しました。(久しぶりの更新)

 

その前に今年のコドフェス振り返り。

 

予選A

これはJAG夏合宿2日目夜に出ました。隣には住建という状況。

C誤読して大幅に書き直すはめになった記憶。Dは頭がバグって完全に停止しました。

住建はずっとデバッグで苦しんでたように見えました。

355位 通過できず。

koprickyは通過できる順位だったのに参加登録していなくて通過できず。

 

予選B

Cは直観ゲーだったはず。D問題に全然覚えがありません。確かどん詰まりしたと思います。

200位 通過できず。

 

予選C

Cまでは早く解けてるけど、Dで完全にストップ。予選BもCもDP苦手過ぎるに尽きる。

291位 通過できず。

パチコ様(pachicobue)が通過!めでたい!LINEグループ名を"コドフェス通過待ったなし!"にしといてよかったよかった。

 

CODE THANKS FESTIVAL確定!

 

そんなこんなでまあレート上がるかなって感じでParallelへ。

 

A問題 AKIBA

文字列にAのみ挿入してAKIHABARAにできるか判定する問題。

頑張って挿入しましょう(こういうの苦手でサブマリンしようかと逡巡)

B問題 Palindrome-phobia

a,b,cだけからなる文字列を並び替えてどの連続部分文字列も回文にならないようにできるか判定する問題。

まずaとbだけだと絶対無理だなと思う。aが連続,1個飛ばししてもダメだからaを最大限詰め込むとするとa○○a○○a...か。

b,cにも同じことがいえるからabcabcabcabc的な感じにすれば回文なしか。

max(aの数,bの数,cの数) - min(aの数,bの数,cの数) <= 1が条件だろ。

適当に出してみる。通る。やったぜ。

C問題 Time Gap

問題設定がややこしい。要するに二つの都市の時計の時刻の差がdの時、本当の時差は24-dの可能性もあるという話。

ある一人を基準に時計の時刻の差が全員分与えられているとき、二人の時差の最小値を最大化しろという問題(問題文を読んだ方が分かりやすい)

入力に同じ時刻の差の人が3人以上いたら絶対時差0の二人がいるな~

貪欲に配置するのが最適じゃね?

適当に書いて出す。通る。やったぜ。

 

D問題 Zabuton

n人がいてそれぞれの身長(座布団基準)とその人がつみあげる座布団の枚数が与えられる。その人の身長よりその時の座布団タワーが低ければ全部一気に積むけどその人の身長より高い時は1枚も積み上げられません。並び順を上手くやると最大何人の参加者が詰めますか?という問題。

一年前のコドフェスで楽しそうに競プロ強者数名が食事の配給所の座布団を積んでいたところから問題が作られたのか?と思った(そもそもそれ以前から座布団を積み上げる文化が競プロ界隈にあるのか???と思ったりもする)

最初どこまで積み上げられるかという話だと思って早とちり(多分これの方がむずい)。

とりあえず何らかのソートを行って、dpだなという雰囲気を感じる。

とりあえず身長でソートして、dp[何人目][その人含め何人詰んだか]をやる。WA

身長低い人が無茶苦茶積むような状況がダメなケース。

とりあえず積む枚数で人をソート。これもWA

JAGの時にもあった(身長+積む枚数)でソート。これが通る。やったぜ。

正当性なんて考えてません。

 

E問題はパス

F問題 Distribute Numbers

入力なしの構成ゲー。

N枚の紙に1枚につきK個の相異なる数字を書き込み、相異なる2枚の紙を取ってくると必ず1つだけ数字が一緒のものがあうようにしたい。

但し全体では1~KをN個ずつ書かれていないといけない。

N=3,K=2だと

12

23

31

的な感じ。1000<=N<=2000になるようなケースを1個提出する問題。

Kをベースに考える。

K=3の時

123

145

167

をまず書く。後は

246

257

347

356

とすると上手く行きます。ハハーンなるほどとなる。

最初のK枚は1を共通のものにしてガリガリ作ります。その後は最初のK本の紙をみて

そのまま下に読む、1個ずつ横にずらしながら読む、2個ずつずらしながら読む...

とやっていくとK-1素数なら上手く行くんだなぁこれが。

 

なおここから怒涛のデバック地獄。この程度の実装でバグらせまくるのは本当に悲しみしかない。

G問題 Mancala

問題省略。

操作を1回やると1個ずつ全体から石が減っていくので、何回操作できるかを考えましょうという話。i番目のマスが何回操作できるか考えるとそれより前の1~i-1番目の情報は要らないので、後からDPしましょう!

解法はほぼ分かってたんだよ分かってたんだよ!!!

これも簡単な実装のところでバグバグの実を食べました。実装力。

 

得意系の問題が並んでいたように思うので、G通して気持ちよくなりたかったです。

parallel 26位 パフォーマンス2564 レート2151(+58)

 

最近調子がいいので週末のTHANKSはやったるで~~~

kopricky,smikenに負けないように頑張ります。

JAG夏合宿2017 参加記 part1

3日間泊まりで参加しました。

 

~遡ること一か月前~

院試の発表まだだけど家で落ち着いている気分じゃないし大阪旅行に行こう!

ということで、急遽ICPCチームメンバーのpolyominoと大阪旅行に行くことに。

大阪旅行2日目。

実家に帰っていたパチコ様(pachicobue)とUSJへ。フライングダイナソー考えた奴頭おかしい。コースター系多すぎてぐったりしました。

夕飯は前日夜量が少なすぎて失敗した串カツのリベンジ。その席でのこと。

ホハム(mtsd)「JAG夏合宿行こう!!!」

ICPCでのキャプテンhyksmは行かないとのことだったので、パチコ様を半ば強引にチームに誘ってその場で参加登録させました。めでたしめでたし。

 

~1か月後~

全然コード書いてない!!!!!やばい!!!!!

院試発表が終わってからというもののチームメンバー3人とも全然コーディングしていないということが発覚。

全員実装力が低いのでどうするどうするという話に。結局どうしようもないという結論で合宿日へ。

 

~1日目~

住建(smiken)と昼ごはんは代々木商店へ。懐かしい感じがしました。

その後オリセンへ。懐かしい感じがしました。

そんなこんなでチーム集合。まさかのパチコ様のみ宿泊しないことが発覚するなど。

パチコ様は1995年生まれなので、うちのチームIQ94じゃないじゃん!という話に。

じゃあIQ94.333333にしよう!としたが、Atcoderでは.(ドット)が使えません。。。

よってIQ_about_94ということになりました。

そして初めての5時間セットへ・・・。果たして手持ち無沙汰になってしまうのか・・・

 

Japan Alumni Group Summer Camp 2017 Day 1 - Japan Alumni Group Summer Camp 2017 Day 1 | AtCoder

 

配られたものをとりあえず分配することに。

 

とりあえずA問題を僕が見てこれは簡単!もう書いちゃうと宣言。

パチコ様はB問題を読む。

polyominoは僕にパソコンの使い方を教えながらそれ以降の問題を確認。

A問題 しりとり

n個の単語のしりとりの文字の総数の最小値を求める問題。

直観的にa→ab→b→...→z→za→(2文字のもの全て)→(3文字のもの全て)→...

でokと即決。あとの二人のコーナーケース大丈夫?って目線を受けながらもコーディングへ。

26^mを計算するのに電卓使いたいって言ったらpolyominoがpythonを起動してくれました。

AC (12:18)

そうしてる間にpolyominoから「これ数学だからやって」とパチコにC問題が投げられて、パチコが数学を解いていた(三角形の相似をわちゃわちゃやっていた)。

答えを出力する感じでAC(20:36)

このタイミングで順位表を見てみるとA問題がFAであることに気づく。おかしいなと思って表をよく見るとまだ見てすらいなかったJ問題クッパを他のチームが解きまくっていて、焦って問題文を読み始める。

J問題 クッパ

約数の和が98になるような正整数を全て求めよ。

こんなん算数やんけやるだけやるだけという気持ちになって、約数の和の公式を使って手計算。52が出てくる。52だ52だと伝えてtextで52を提出。WA。

あれれ???改行してないんじゃね???2WA

あ、97は素数!!!! AC (25:01)

はい。やらかしました。(適当にぶん投げていたけど、ペナルティが20分ということに後から気付いて後悔)

普通に回せばよかったのでは・・・

 

その後、各自がどの問題を解こうかと模索。とりあえず解けそう(他チームが解いてそうな問題)

mtsd H問題 イベルタル 

パチコ B問題 リス K問題 パンプキン

polyomino E問題 ベクトル式 F問題 部分文字列

あたりを考え始める。

僕はH問題をマス目を書いて最小値を埋め始める。

その間にパチコ様がK問題は和でソートすればいい!と主張。すぐに理解できず、マジ???ってなり、とりあえず書いてくれと言って書いてもらう。AC(48:54)

polyominoによるとEはやりたくない。Fはライブラリがない可能性があるので険しいかも。ということになり、とりあえずパターンが見えたHを定式化して倒しに行く。

僕が式を求めてその間にpolyominoがコードを書く。連携が上手く行った。AC(67:22)

 

ここからどれを解けばいいんだ~となる。
G問題は見るからにヤバそうだし全然通されてないので読みもせず。同様にI問題もパス。

C問題も数学っぽいけど全然通されてないし、FFTとかそういう類の匂いを感じスルー。

E問題は時間内に通せるか危険。残るはB問題リス、F問題極小部分列。

パチコがFは端から貪欲でよさそうと実装を始める。

その間にB問題をpolyominoと考え始める。

全員到着したときの順番が分かっていれば上手く行くか?

まずどうやってその配列を生成するか?

を考え始める。polyominoがこういうのはクエリを後ろから処理すればいいというのでその方向性で考える。すでに後から何番目までに何個埋まってるのかが分かってればよくない?という話になりこれ典型BITだよとpolyominoが指摘。じゃあ後半もBITで貪欲かよっしゃ解けた解けた!と喜ぶ。

 

 

F問題の方の実装が終わったというので、テストケースを実行するとなんかあってない。

部分文字列としてはあってるけど最短のものを出力できてないという話に。

適当に後ろからもう一回貪欲で回せばいいんじゃん?と言ってみたらそうっぽいなという話に。

実装したら上手く行ってそうなので投げる。AC(128:54)

 

後50分。B問題絶対通すぞ!という感じになる。

BITを蟻本から書き写す。ワチャワチャ実装。0-indexと1-indexで大混乱。35分くらいたってようやく動いたので提出。→WA

配列足りてないぞ!直せば通るだろ→半分くらい通るもWA

よく考えると後半は貪欲じゃない!と分かり、どうしよどうしよとなる。

パチコ様参戦。前からi番目にいるのが何番目に来たやつかは分かっていて、この番号が昇順になるように取っていけばいいんだけど・・・と伝えると、それただのLISやんと言われる。

あっそうじゃんとなり、また蟻本書き写し。ぎりぎりAC(174:58)

 

終了。7完。無駄ペナを積んでしまったけど、チーム的にはキャプテンを失った割にかなり上手く行って大満足。

 

パチコはそこそこ遠いのに宿泊なしで帰宅。あとの二人は今回単独参加の住建と一緒にダラダラ。あんまり他チームと交流できなかったのが残念。

 

 

 

ここまで書いていたのが2週間前。大分忘れてしまっていてpart2以降があるかはわかりません!part1完!

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)

 

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