dohatsutsu’s diary

日記を書いています。

【No.006】「 つくば大会参加記2」

箇条書きで適当にコンテスト以外の思い出を書いていきます。

 

土曜日

  • 秋葉原駅でチームchikOkUの人達を発見。
  • つくばエクスプレスでyosupotさんを発見。
  • つくば駅につくと、chokudaiさん達を発見。
  • chokudaiさん達の後をついていったら（一度道を間違えたけど）無事に会場に到着できた。
  • jagの人が沢山いて驚く。
  • 知っている人に真面目な顔で英語で話しかけられるとドキッとしてしまう。
  • 練習セッションでは消したはずのCapsLockの存在が一番つらかった。
  • また、再帰関数によるスタックオーバーフローが発生する境界を探そうとするも失敗。

日曜日

  • 体育館の中に入る前に、貴重品をココーチの先輩に預かってもらった。
  • このとき後輩が学生証を預けてしまい、ちょっとしたハプニングが起きた。
  • コンテスト終了直後、後輩とK問題について話していたらshiotaさんに注意されてしまった。
  • コンテストの講評が始まるまで、順位表の凍結解除により順位が下がってしまわないか不安でしょうがなかった。
  • 表彰されるとき何か一言を喋ることになるとは思っていなかったから固まってしまった。
  • 6位の商品として「けん玉」を入手。
  • 懇親会ではいくつかのブースを回ってグッズを手に入れた。
  • 宿泊施設に到着してからは電話で先生への報告とけん玉の写真撮影をした。

【No.005】「ACM-ICPC アジア つくば大会 2015 参加記」


コンテストの感想 （完全に僕目線です）

・まず先輩が環境設定等を行っている間にA問題を読みました。

・数分後、先輩に環境設定が終了したことを告げられ、すぐにA問題の実装を開始しました。

・とくにバグることもなくAC

・振り返ってACしたことをチームメイトに話すと、D問題を読んでほしいとのことだったのでマシンを先輩と交代しD問題を読みはじめました。

・D問題は似ている問題が去年の天下一予選で出題されていたことを思い出し、すぐに解法が分かってしまいました。

・先輩がB問題をACした時、僕は約半分の紙コーディングが終了した状態で、後輩はまだC問題を考えている途中だったため、とりあえずD問題の実装を行うことにしました。


・D問題の実装の約7割が終了した時、C問題が解けるという話を先輩から聞いて、とりあえず書き掛けのD問題のコードを印刷してマシンを交代することにしました。

・印刷したコードを読み返していると、終わりの角度ではなく始まりの角度でソートしているというバグを発見しました。

・後輩がC問題のデバッグをしているようだったのでマシンを交代してもらい、紙コーディングしたD問題を書き写しつつソートのバグを修正してACしました。

・実はこのとき、6つあるサンプル入力のうち最初の3つだけを試してから提出していました。（隠された残り3つのサンプル入力の存在に気付いたのはAC後）

・そのあと後輩とマシンを交代したらすぐにC問題もAC。

・順位表を見るとなんと2位に

・先輩に状況を確認すると、E問題とF問題が読めただけでまだ解法ができていないとのことだったので、まずその2つの問題概要を説明してもらいました。

・概要を聞き終わった後、E問題が桁DPっぽいことに気づき、実際にどのくらいの状態数になるのかという情報を空いていたマシンを使って試してみることにしました。

・各桁を掛け算した値の種類が意外と少ないため桁DPで解けることが発覚し、僕がE問題を実装することにしました。

・はじめに僕が先輩に実装をお願いしたものの、先輩がマシンの前に座ってから数秒後に「やっぱり僕が実装します」と言って自分に代わってもらいました。
（先輩と比べて僕の英語を読むのがとても遅いため）

・しばらくしてコードが完成したもののサンプル入出力が合わずどうするか迷っていたとき、ちょうど後輩がF問題の解法を思いついたらしいのですぐにマシンを後輩と交代
して自分は紙デバッグを行うことにしました。

・印刷したコードを先輩に説明しながら1行ずつ読み返していくと、入力を整数として読んでいるために020という入力が20という入力になってしまうことを先輩に指摘されま
した。

・Fを書いている途中の後輩に少しの間だけ交代してもらい、E問題を修正して提出するもTLE

・手元だと最大ケースっぽいサンプル入力がほぼ1秒で終了しているので、とりあえずの高速化としてmapをunorderdmapに変えてみたらACしました。

・その後、僕と先輩でG問題の考察をしている間に後輩がF問題をAC

・その後、先輩がG問題の解法を思いつき、先輩が実装をしてAC

・あまりもの嬉しさにハイタッチ

・後は残った問題をいろいろ考察したり愚直解を作っていろいろ試したりしていたらコンテスト終了

・凍結前の順位は6位、そして最終結果も6位でした。


個人的に、この結果の要因は問題担当の割り当てが良かったことだと思います。


それぞれが実装を担当した問題は

先輩:B,G

僕:A,D,E

後輩:C,F

でした。

・面白いことにB問題を読んだのは後輩で、C問題は先輩ですが、B問題を実装をしたのは先輩で、C問題は後輩でした。

・偶然僕が読んだD問題は、ほぼ似ている問題を知っていたため絶対に解ける自信があり、チームメイトに問題概要を伝えることもありませんでした。

・E問題、F問題、G問題はそれぞれ解法を思いついた人自身が実装を担当しました。

・完璧に3人にバランスよく問題を割り当てることができたため、負担が多くなってしまった人が途中で疲れきってしまうことが無かったのも大きい気がします。

 

【No.003】「模擬地区予選参加記」

2015/Practice/模擬地区予選/案内 - ACM-ICPC Japanese Alumni Group

東京オンサイトに参加しました。

 

最終的な結果は6問ACによる18位でした。個人的にはもうちょっと上の順位を取りたかった・・・。

僕が実装を担当したのはA問題だけで、それ以外の問題については解法を考えるだけでした。

 

○A問題について

唯一実装を担当した問題です。21分51秒かかりました。もっと問題文の解釈のスピードを上げたいなと思いました。また、コンテスト終了後、dpをしなくても解けることに気づき少し悲しくなりました。

 

○B問題について

後輩が全探索ではなく貪欲法で解こうとして苦戦していることに気づきました。

全探索のコードに書き直してもらった後、デバッグの手伝いをしました。int型でオーバーフローしている箇所を発見し、修正してもらったらACしました。

 

○C問題について

削除したいファイルが隣り合っている場合、名前が長い方のファイルを無視してもよいという法則を僕が見つけたら、先輩がそれをヒントに解法を考えて実装してくれました。

 

○D問題について

ほとんどC問題と同じように先輩といろいろ議論していたら先輩が解法を考えて実装してくれました。

 

○E問題について

この問題に挑戦している途中でコンテストが終了してしまいました。

とりあえずこの問題についてはあとで復習したいです。

 

○F問題について

後輩と先輩が解いてくれました。

 

○H問題について

先輩から問題概要を教えてもらいました。

遅延評価セグメントツリーが得意な後輩と一緒に考えることにして正解でした。僕は遅延評価セグメントツリーを書いたことがないので後輩に実装してもらいました。

 

 

今日はとても疲れました。眠いです。

【No.002】「1つの直線とx軸の交点を求める」

y座標が異なる2つの点が与えられたとき、その2つの点を通る直線とx軸の交点を求める関数を書こうとしたとき、2つの相似な直角三角形をイメージしたら思っていたより綺麗に書くことができました。詳しい解説は省略します・・・。

 

#include<bits/stdc++.h>
using namespace std;
typedef complex<double> P;
 
P calc(P a,P b){
  return a+(b-a)*imag(a)/imag(a-b);
}
 
 
 

【No.001】「コードフェスティバル参加記」

0日目の主なできごと

・移動の途中で大学の後輩と合流しようとしたら無駄に時間がかかってしまい、会津若松駅を出てから前泊のホテルに着くまでに5時間もかかってしまいました。

 

1日目の主なできごと

・会場についてから開会式が行われるまでの間、会場を散策していたらタイピングコーナーでchokudaiさんを見かけました。

・kyuridenamidaさんにパソコン甲子園2015のパンフレットを見せたら笑っていました。

・本戦ではH問題の解法がすぐに思いついたことが影響し、26位をとることができました。

・青木さんのトークライブを聞いて、「家の環境によって子供の成績に大きな差が出ることは間違いないけれど、完全に決まるとまではさすがに言い切れないのでは？」と思いました。

・エキシビジョンマッチをちょっとだけ抜け出し、人がいないDDRと太鼓の達人をプレイしてスタンプラリーを進めました。

 

2日目の主なできごと

・あさプロは26位でした。参加賞のタオルをゲットしました。

・rng_58さんのトークライブのスタンプを押してもらったところで、スタンプラリーの景品のタンブラーを入手しに行きました。

・早解きリレーでは12位でした。自分が担当した問題をバグなく実装できてよかったです。コードフェスティバルの全コンテンツの中で、このリレーが一番楽しかったです。

・ハッピーアワーでDDRのハイスコアが表彰されているのを見ても違和感を感じませんでした。

・最後にドローンで写真撮影をしました。

 

感想

・ どのコンテンツも楽しくて、来年も開催されるのなら是非参加したいです。そしてもっと上の順位を目指したいです。