RUPC2018 参加記

RUPC参加前

twitterで今年もあるよとのことだったので参戦。 atnd.org

1日目-立命館大学セット

怒髪さん、masumiさん、ksawさんの4人でdmkmというチームで参加しました。
自分はC問題を担当していましたが、解法が舞い降りてこなかったのですぐ助けてした。弱いね。
結局解法を教えてもらったが実装できそうになかったので怒髪さんに投げた。
E問題はksawさんが6通り辺をはってダイクストラやるだけ、と解法を教えてくれたので実装するもWA。
初期化の値が小さかったみたい。見事な戦犯をかます。
自分の仕事は以上で、チームとしては全完を成し遂げた。
チームメンバープロすぎる。

1日目-懇親会

twitterでよく見かける人々と喋ったりした。 去年のようにキャベツが大量に残っていたわけじゃなく平和だった。

2日目-会津大学セット

2日目はtuki_remonさんとkeiさんでkankitukeiというチームで参加した。
由来はレモンとみかんで柑橘、keiさんなので系、で柑橘系( 個人的にめっちゃ好きなチーム名 )

自分はB問題を解いて、あとはFとG問題の考察をした。

Fは移動パターンが数通りしかないから筋肉で殴れそう。
実装バグらせそうだったのでtuki_remonさんに実装を任せる。

Gは1つのペアで条件が成り立つなら優先的に消していき、それ以外のもので一般マッチングすればいいのでは?みたいな気持ちになった。
一般マッチングをどう実装すればいいのかわからなかったのでkeiさんに実装を任せる。
二人ともAC。はいプロ。

考察を他人に教えるということに慣れてなかったので、つたない日本語で考察を二人に言って申し訳なかった...。

この日は6完で、個人的にRUPC史上最も活躍した日だと思ってます。(ほんまか)

2日目-懇親会

初めて酎ハイをジョッキ2杯飲んだけど全く酔った感じがしなかった

どっからどう見ても酔ってますね。はい。

3日目-北海道大学セット

3日目はjimmyさんとわたあめさんとでjwmというチームで参加。

A問題は、はいという感じだったので実装AC B問題はいつのまにかACされていた。

C問題はわたあめさんから解法を聞くも実装方法がピンと思いつかず、ひどいソースコードになってしまった。その上ガバガバ実装だったので助けてもらいながらコードを修正する。これでいけるだろうということで提出するもWA。コンテスト中にはACできず。

D問題はラスト1分を切っている状態でjimmyさんが通してた。プロ。

結局この日は3完。知識不足というか実装力のなさを痛感した。

終わってから番兵さんとTreeoneさんにC問題のコーナーケースを聞いて辛い気持ちになった。

その後

RUPC参加者とにぼ二郎食べに行くぞー!!と思ったら定休日だったらしく別のラーメン屋に行った。

最後に

チームを組んで競プロするのはやっぱり楽しかったし、自分よりはるかにできる人の考察を聞いたりするのはすごくタメになる。 それに競プロのモチベーションも高まったので参加してよかったと思う。

次に参加するときには青くなっていたいなぁ

webpackで「Module not found: Error: Can't resolve 'fs'」と出てきた時の対処法

エラーいっぱいでつらい

reactを使っていた時に踏んだエラーで、npm webpackしたら大量のエラーが出てきて、その大半がModule not found: Error: Can't resolve 'fs' ( ここの'fs' が 'net' とか 'tls' と表示されていたのもあった)。 とりあえず、 yarn add fs でnot foundなモジュールをインストールしたり、エラーが出ているモジュールを別のバージョンでインストールしたり試行錯誤してもダメだった。 ググってみたりしたけど、ググり力が低いため見つけるのに時間がかかった。

対処法

webpack.config.jsonに「target: 'node'」を追加すればいい。 たったこれだけでした。

原因

node.jsが使われている時は「target: 'node'」を記入しないといけなくて、自分はAPIを叩くライブラリを使っていたのでこのエラーが起きていたみたいですね。 自分はjavascriptしか書いてないと思っててもライブラリでnode.jsが使われていると言う落とし穴があるんですね。

詳しくはこのサイトに書いてます。
https://jlongster.com/Backend-Apps-with-Webpack--Part-I

ABC088 の話

タイポとか色々やらかして辛いコンテストでした

A - Infinite Coins

https://beta.atcoder.jp/contests/abc088/tasks/abc088_a

(N % 500 <= A)が成り立てばYesを出力すればよいよい

int main(){
    int n, a;
    cin >> n >> a;
    n %= 500;
    if(n <= a)cout << "Yes" <<endl;
    else cout << "No" << endl;
    return 0;
}

B - Card Game for Two

https://beta.atcoder.jp/contests/abc088/tasks/abc088_b

両者とも最大になるようにカードを取っていくのだから当然数字が大きいカードから取っていくのでそれをシュミレーションする。

int main(){
    int n;
    int a[105];
    cin >> n;
    int aa = 0, b = 0;
    rep(i, n)cin >> a[i];
    sort(a, a + n, greater<int>());
    rep(i, n){
        if(i % 2 == 0)aa += a[i];
        else b += a[i];
    }
    cout << abs(aa - b) << endl;
    return 0;
}

C - Takahashi's Information

https://beta.atcoder.jp/contests/abc088/tasks/abc088_c

a1, a2, a3の値が決まったとすると、b1, b2, b3がどんな値を取っても a1 と a2 を使ったマスの差はどの行を見ても同じで、同じく a2 と a3 を使ったマスの差もどの行を見ても同じである規則性(?)がある。

int main(){
    int c[4][4];
    rep(i, 3){
        rep(j, 3){
            cin >> c[i][j];
        }
    }
    
    if(c[0][0] - c[0][1] == c[1][0] - c[1][1] && c[1][0] - c[1][1] == c[2][0] - c[2][1] &&
       c[0][1] - c[0][2] == c[1][1] - c[1][2] && c[1][1] - c[1][2] == c[2][1] - c[2][2]){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
    return 0;
}

if文が長くなってすっごい見づらいな...

D - Grid Repainting

https://beta.atcoder.jp/contests/abc088/tasks/abc088_d

自分の大好きなアルゴリズムはBFSなのででてきたときは興奮した:dohentai:
や、BFSって真面目にコツコツとする感じが可愛いでしょ?可愛いですね。

BFSでスタートからゴールまでの最短距離を計算して、(' . 'の数 - 最短距離 - 1)が最大スコアになる。 最後の -1 はゴールの部分は' . 'にしておく必要があるからです。

int h, w;
int d[55][55];
char s[55][55];
 
void BFS(){
    rep(i, 55)rep(j, 55)d[i][j] = INF;
    d[0][0] = 0;
    queue<int> q;
    q.push(0);q.push(0);
    while(q.size()){
        int x = q.front(); q.pop();
        int y = q.front(); q.pop();
        for(int i = 0;i < 4; i++){
            int xx = x + dx[i];
            int yy = y + dy[i];
            if(0 <= xx && xx <= w && 0 <= yy && yy <= h && s[yy][xx] == '.'){
                s[yy][xx] = '#';
                d[yy][xx] = min(d[yy][xx], d[y][x] + 1);
                q.push(xx);q.push(yy);
            }
        }
    }
}
 
int main(){
    int cnt = 0;
    cin >> h >> w;
    rep(i, h)rep(j, w){
        cin >> s[i][j];
        if(s[i][j] == '.')cnt++;
    }
    h--; w--;
    BFS();
    if(d[h][w] == INF)cout << -1 << endl;
    else cout << max(0, cnt - d[h][w] - 1)<< endl; 
    return 0;
}

今年一年のふりかえり

1月

  • すこし競プロにハマりだした
  • 初めてABCで全完してはしゃぎまくってた記憶あり

2月

  • 期末試験にTLEして追試した
  • RUPCに参加することが決まってABC-A問題B問題埋めが始まる
  • それしか覚えてない

3月

  • RUPCに参加。完全に競プロにハマった
  • この時初めて競プロで美味しいご飯が食べれた

4月

  • 2回生になったけどhogeって感じだった
  • 競プロ1回生が多くて生き残りが多くなりそうな気持ちになる

5月

  • 某社にインターンのプログラミング面接をする。落ちたけど、すごいいい経験になった
  • AOJ-ICPC埋めしてた
  • いいねされた数だけAtCoderでACするがスタート

6月

  • AOJ-ICPC埋めの難易度が上がってきて辛くなってくる

7月

  • ICPCに参加。
  • 期末めんどくさかった

8月

  • twitter apiを使ったwebアプリを作った。

9月

  • AtCoder で水色になった
  • ナナチかわいい

10月

  • 何も覚えてない...

11月

  • TOEICでそこそこの点が取れた
  • 講習会でBFS回を担当した。講習会難しい...

12月

  • もう一本webアプリを作り始める。

まとめ

激動の一年でした (小並感 ( みかんだけに(は?) ) )

さて、競技プログラミングの季節になりました

OIT Advent Calendar 2017

この記事は、 OIT Advent Calendar 2017の7日目の記事です。

簡単に自己紹介

大阪工業大学2回でIS科の者です。 emacsとneovimが好きでVisual Studioも好きだし、sublimeTextも案外嫌いじゃない、ただの浮気者です。 競技プログラミングチームとHxSに所属していて、🔥精進🔥したいなーと思いながらオフツゥンから出られない毎日を送ってます。 最近はwebアプリ作ったり、courseraで機械学習勉強したりしてのんびり過ごしてます。 ナナチかわいい

競技プログラミング #とは

与えられた問題をプログラミングでどれだけ多く、早く、正確に解けるかを競う競技です。 これだけ見たら、「なんかハードル高そうだなぁ...」と思う人がいるかもしれませんが、実際そんなことはなくて弊学で言えばC演習Ⅰが理解できれば大丈夫です。競技プログラミングをするにあたって必要な知識はfor文、while文、if文が使えれば競技プログラミングはできます!やったね!!!

どんな人にオススメ?

パズルとか数学とか好きな人は多分面白くできると思う。 あとは、プログラミング言語勉強したけど使える場所がないとか、単純にプログラミングするのが好きな人も楽しくできると思う。 あと、就活意識してる人もオススメできそう。最近は企業コンテストもあってドワンゴとかコロプラ主催のやつもある。ちなみにこれは上位に入ったら1次面接免除みたいな制度もあるみたい。 自分はパズルとか数学とかは苦手です。単純にプログラミングするのが好きなのでやってます。 いや、競技プログラミングは本当にプログラミング欲を満たしてくれるんですよ...素晴らしい... (だからみんなもやろうな??)

どんな力が身につくの?

自分がやった感想としては、自分の考えてる処理をソースコードにする能力とアルゴリズム力( ほんまか )がついてる気がします。 ( タイピングスピードも心なしか上がった気がする...) 競技プログラミングは色々な問題を解くので、「あ!これ競技プログラミングでやった処理だ!」みたいなことが時々あります。

競技プログラミングのサイトまとめ

AtCoder

f:id:mkan_0141:20171206203851p:plain 日本のプログラミングコンテストサイト。ほぼ週1(土日のどちらかで時間は夜9時から)でコンテストが開かれてるので参加しやすい。 使い方は

Atcoder - プロコン(競プロ) Wiki*

を参照してください。初参加の人はAtCoder Beginner Contestに出るといいです。 ちなみにさっき言ってた企業コンテストはこのサイトで行われます。

AizuOnlineJudge

f:id:mkan_0141:20171206204604p:plain プログラミングの問題が大量にある。上手く使えばプログラミング演習のテスト勉強にもなるし、実力もつくので良い。

まとめ

競技プログラミングを始めよう!!!!!

ICPC2017国内予選参加記

人生2回目のICPC国内予選

odanさん と たいちょーさん と「itokzn」というチームで組んで3完66位でした。

チームの方針はA,B,C問題を一人ずつ解いていって、D問題をみんなで考えるみたいな感じだった。

 チルタリスはマスコット(n回目

 

開始前

私の大学は4限の授業終了時間が4:30分というICPCに厳しい時間割なので、先生に事情を話し授業の途中で抜け出しました。(先生優しかったのでよかった

その後食料を調達し、チームの方が集まっている研究室に突撃。

始まるまでは、「この団体名どうする?」とか「チームで共有できるライブラリ欲しいよねー」みたいな話をしてた。

 

---コンテスト開始--- 

A問題

たいちょーさんがすんなりと通す。

全探索するだけみたいな感じだったらしい。

 

B問題

B問題は自分が担当。

A問題が解き終わるくらいに大体の問題が概要が理解できたけど、実装するのが難しそうだったので相談。実装方法を教えてもらい、とりあえず書いてみるがsampleで撃沈。

ソースコードを印刷してC問題担当のodanさんに交代する。

sampleが通らない理由はすぐにわかって、文字列定数の意味をちゃんと理解できていなかった...

PCを代わってもらい、ちゃっちゃと直してsampleが通ったので投げたら通る。

 

人生初ICPCでACできたので非常に嬉しい!(けど提出した時赤字でAccept的なの出てきたから焦った。赤文字は間違っているというイメージが強かったので...)

 

C問題

実装辛そうでsampleが通らなかったみたいだが、すぐに修正してACした。

odanさんの「これだから人間の書いたプログラムは...」という発言に爆笑してた。

 

この時点で1時間ちょっとだったのでチーム的にはいいペースだった。

D問題

最小費用流かDPかみたいな話をしていてDPだと厳しそうという結論に至り最小費用流で解くことを決める。自分がライブラリを写している間に、二人がいろいろ考察していたが、sampleが通らず時間切れ。

 

感想

自分が担当したB問題がバグらせなければもう少し順位が上がっていたと思うので、もっと実装力つけたい。

D問題の考察に参加できなかったのは完全に実力不足。やっぱり蟻本は中級編くらいまで読んで理解しておかないとなぁという気持ちになった。

来年は自分がD問題解いてやるぞくらいの勢いで精進していきます!

 

来年は4完して本戦に出るぞー!

立命館大学競技プログラミング合宿2017 参加記

合宿の写真があまりないので悪しからず...

大学到着まで

湖西線トラップに引っかかりそうだったが、大阪駅から南草津まで一本でいけたのでなんとか駅にたどり着けた。

南草津からはodanさんと冷雨さんと合流して大学まで行った。

 

人生初立命館大学だったけど、これは広すぎて迷子になりそう笑

いったい自分のところの何倍の敷地面積だよとかこれが大学かとか思ったり思わなかったり

 

1日目

自分は、btkさんとgachoさんとBGMというチームで参加。

自分はA問題を担当。しかし、解法が自信なかったのでbtkさんに質問し解法を教えてもらい、書く。提出→AC

初オンサイトだったので風船もらえた時は感動した。

ここから先はbtkさんとgachoさんが解いて、自分は座るだけみたいな感じでした。(申し訳ない)

btkさんが解いている間にgachoさんから最小費用流について教わった。優しい。

 

コンテスト終了後スポンサーセッション

kenkooooさんの話が面白い笑

競プロを生かせる仕事の一例を聞けてためになった。

 

コンテスト終了後、懇親会へ

しかし、周りに知り合いがなかったので、キョドっているとnoyさんが声をかけてくれて色々話した。

その後、c7c7さんとつたじろうさんと色々話しながら、c7c7さんとキャベツを食べまくってた。c7c7さんのキャベツ摂取量まじやばい

 

懇親会終了後ホテルへ

泊まったホテルはアーバンホテル南草津で部屋が綺麗で良かった。

宿泊はアーバンホテル南草津がおすすめ!

 

二日目

NCAさんとyebityonさんでGumikanstarというチームで参加。

A問題担当し、見事戦犯になる。

自分がA問題を悩んでいる間に、二人がB,C,EをACして(この間にもA問題手伝ってもらっていた)A問題を手伝ってもらう。全探索してみるもWA.。解説を聞くとあぁなるほどなって。

 

コンテスト終了後懇親会(魚民)へ

この日の懇親会費はRCOさんが出してくれた(ありがとうRCO!)

yazatenさん、pulmnさん、kzyKTさん、NCAさんと相席でプロが集まった感じだった。

来年は酒飲める年齢なので、もし来年も魚民なら青汁サワー飲んでみたいなぁ

 

三日目

三日目は怒髪さんとこんぶさんとtemmie というチームで参加。

自分は怒髪さんに教えてもらいながらAとC問題を解く。プロだった。

それ以降解ける問題がなかったので、あとは座るだけでした。(申し訳ないです)

 

合宿終了後

帰りに、naimononさんと色々喋り、一緒ににぼ二郎に行くことに

にぼ二郎めっちゃ美味しかった。(NCAさんが懇親会後でも行きたいって言っていた気持ちわかる)

 

 

感想

初めてのオンサイトで、知らない人だらけで緊張していたけど、みなさんすごく優しかったのですぐに馴染めました。現段階では実力、知識不足でほとんど問題が解けなかったり、考察に参加できなかったりしていたので、もっと実力をつけなければいけないなと感じました。脱戦犯!!