Tsuna lab

国の端っこで動物の研究しながら競技プログラミングなるものをしてみます

ZONeエナジー プログラミングコンテスト “HELLO SPACE” の感想

ZONeエナジー プログラミングコンテスト “HELLO SPACE”に参加してきました;;このコンテストは新発売の"ZONe mad_hacker Ver.1.0.0"の広報も兼ねているということで、ちゃんと近所のセイコーマートで購入して参加しました。結果はA,B問題の2完で少しレートが上がりましたが、残念ながら前回失った分の借金は返せませんでした;;

f:id:naturence:20210501233819p:plain

A - UFO襲来

ストーリー:UFOのせいでコンテスト中止→ZONeを買いに行く

atcoder.jp

与えられる文字列の中に"ZONe"という文字列が何個含まれるか出力せよという問題。pythonではcountという関数で特定の文字列が何個含まれるか調べることができるので秒殺。(1分38秒) やっぱりpythonしかかたん。

B - 友好の印

 ストーリー:UFOの操縦プログラムをKARATEで破壊する

atcoder.jp

 自分とUFOの間に障害物が何もなくなるように自分の高度を変えるとき、その高さの最小値を出力せよという問題。自分のいる位置は一番高い障害物とUFOの位置によって定まるため、すべての障害物とUFOを結ぶ線分のうち一番大きいy切片を出力。二点を通る直線の傾きを(xの増加量)/(yの増加量)と書いていることに気づかず時間を溶かしてしまいました。ここまでで12分5秒。もうすこし縮められたはず・・・!

C - MAD TEAM

ストーリー:MADな仲間が欲しい→AtCoder上の競プロer

atcoder.jp

5つのパラメータが与えられたN人から3人選んでチームを作る。チームの能力は各パラメータの最大値で定義され、チームの能力のうち最小のパラメータが最大値を出力せよという問題。最小値の最大化は決め打ち二分探索だと競プロ典型 90 問の1問目でやったので実装しようとするも、二分探索のcheck関数で各能力をどう評価するかのところで詰まってしまい、D問題へ移動しました。二分探索だと気づけただけでも成長できてると思います!

D - 宇宙人からのメッセージ

ストーリー:メンバーがそろった(揃えられませんでした)→暗号解読しよう

atcoder.jp

今回の戦犯

与えられる文字列に従って操作を行い、得られる文字列を出力せよという問題。今回の操作は、文字が"R"だった場合は文字列の反転、そうでない場合はそのまま追加。ただし、生成した文字列に連続する文字があればそこを削除する。

 文字列の反転する操作がある場合は、実際に反転はせずに反転しているかの記録だけ行うと早く計算できるやつだと気づきとりあえず実装。(先週のABCでもでてた)連続する2文字を消す操作は問題文通り文字列の生成を行った後に行いました。300点問題ならこれで通るだろうと思って投げるもTLE。

文字列での操作が遅いのかと思いリストに変更してもう一回投げる。これもTLE。これはどこかのパートが根本的におかしいと思ったので、文字列の生成のパートを見直し始める。ここで、与えられる文字列を"R"で分割して配列に入れ、その配列のサイズの偶奇によって文字の削除前の配列が簡単に生成できることに気づく。この生成した文字列を元にさっきと同じ削除の操作を行って投げてみる。ちょっとだけ早くなるも結局TLE。

TLEの原因が削除操作だと気づき文字列の生成する操作と同時に削除する操作も行うことを考えるも、時間がたりずにコンテスト終了。ちなみにこの回答もTLEでした。

正解するためには

  • 文字が連続するときは文字を追加する代わりに削除(これは気づいた)
  • 反転操作は実際に行わずに追加位置を変更する(これも気づいた)
  • dequeで生成する文字列を管理することで文頭文末の操作を高速化(全く気づけなかった)

の3つが必要だったみたいです。dequeは何度か見かけたことはあったのですが、いまいちその恩恵が分からず使う発想に至りませんでした…。これで次回から使える武器が増えたので儲けものです!

まとめ

ウッキウキでZONeの新商品まで買いに行ったのに2問しか解けなくて若干恥ずかしいですね。今回は数学的な考察が出来なかったわけではなく、単純な知識不足だったので精進していけば全然克服できると思うのであまり負の感情は湧いていません。知識を定着するためにもコンテストで得られた知見もブログにまとめていこうかなぁと思っています。

 

おまけ

コンテスト中、隙あらばエナジードリンクってカフェイン と一緒にアルギニンが入ってるけど、どんな作用機序で覚醒作用につながるんだろうと考えてたんですが、アルギニンによって産生されたNO(一酸化窒素)が1.脳の血管を拡張して血流改善2.神経伝達物質として働くことが原因と考えるのが今のところ妥当っぽいですね。(そんなんでいいのか)ちょっと調べたかぎりでは、カフェインと一緒に加える理由としてはカフェインがアルギニンの分解を抑制することでアルギニンがちゃんと働けるようにするためって感じでした。この論文、2009年のものだけど現在は作用機序がちゃんと解明されているんでしょうか?(そもそもそんな状態で製品化ってできるんですかね?)

アルギニンとカフェインを一緒に加えるとNOの量が増えるよという論文↓

pubmed.ncbi.nlm.nih.gov

アルギニンとカフェインを一緒に加えるとアルギニン分解酵素の活性が落ちるよという論文↓

pubmed.ncbi.nlm.nih.gov