名もなき未知

エンジニアリングとか、日常とかそういうのをまとめる場所。アクセス解析のためGAを利用、Googleに情報を送信しています。商品紹介のためAmazonアフィリエイトを利用、Amazonに情報を送信しています。記事に関しては私が書いていない引用文を除いて自由にご利用ください。

Code Thanks Festival 2015 参加記

AtCoder 競技プログラミング 旅行

長いので続きからどうぞ．

====

Code Thanks Festival 2015に参加してまいりました．
ずっとTwitterでブツブツ言っていたのが私です．（人の話を聞こう）

※学生のうちは

 

 

起床

6:30に家をでるつもりが，6:30に起きてしまう事故．
電車の時刻を調べると，11:15ごろ到着予定という，事故や乗り換え失敗で即TLE事案．超焦る．

 

到着するまで

yukicoder のアドベンドカレンダーの問題などを少しばかり消化．

#62902 No.312 置換処理 - yukicoder

受付までTLEの可能性は消えず，少しそわそわ．

あと，東京についてからですが，そういえばゆりかもめってなんだ？ って考えなおしてみると，コミケの時に乗るアイツでしたね…


そして，会場に到着して受付を済ませる．11:30になんとか間に合う．
駅から出てすぐのところに，宇宙ツイッタラーXさんが立っていて笑う．少しお話をして，会場に向かった．

 

コンテスト開始まで

挨拶とか諸注意とかあった．

コンテスト開始

メインコンテンツ．

とりあえず，A問題を開いて日本語が理解できず，B問題についても同様．
C問題読んだら一瞬で解けそうな感じがしたので，Cに着手．

C問題FA狙う気でテキストボックスコーディングをしたけど，結果は二番目だった．(2:24) 惜しい．

実装アルゴリズムはとりあえず挿入して，ソート，そしてfindなりindexなりで見つけるだけっていう単純なものです．

n = int(input())
li = [int(x) for x in input().split()]
i = int(input())
li.append(i)
li.sort()
print(li.index(i) + 1)

次にA問題に着手．
問題の読み違いをおこして，2WA．

絶対値を取って計算するだけでOKでした．
（何を勘違いしたのか，-100から100へのワープが無いと書いてあるのにもかかわらず，考慮しようとしてしまった屑）

A, B = int(input()), int(input())
print(abs(A) + abs(A-B) + abs(B))

で，B問題に着手したんですが…．

後のスクショ．

このミスが発生してしまった原因ですが，私がめんどくさがって文字列のまま処理してもこれ大丈夫じゃんと思ったら，ソートした際に昇順ではなく，辞書順になってしまっていていたことが原因．

言語仕様を忘れないように，ちゃんと覚えておきましょう（戒め）

Aのリストに取り出したボールがあれば，Bのリストを追加．
Bのリストに取り出したボールがあれば，Aのリストを追加．
その上で，重複分をsetで削除して，ソートして出力するだけ．
なんですよね…（実際11WAの原因の殆どが，ソートが辞書順だからでした）

al = [x for x in input().split()]
bl = [x for x in input().split()]
num = input()
res = []
if num in al:
    res.append(bl[0])
    res.append(bl[1])
if num in bl:
    res.append(al[0])
    res.append(al[1])
res.sort()
res = list(set(res))
res = [int(x) for x in res]
res.sort()
print(len(res))
for r in res:
    print(r)

ちなみにB問題で突っかかってる間にD問題，E問題が解けていました．
（あとコレ後で見返して思ったのですが，E問題実質10分で解けているので解く順番を変えていれば，E問題FAの可能性あったかもしれません．簡単な問題から解くという基本方針を焦ると忘れてしまう，私も本番に弱い子なのでした）

で，本来の道筋で行くと，C→A→B（解けてない）のあと，E問題に着手．
調べなければいけない文字列のリストから，指定された文字以外を取り除くようにし，加工した文字列を比較してYESとNO出すだけ，一瞬で実装できた．（それだからもったいない）

for _ in range(int(input())):
    s, t = map(str, input().split())
    res = ""
    for c in s:
        if c in t:
            res += c
    print("YES" if res != "" and t in res else "NO")


そのあとD問題．
問題文を読み，クエリの問題とか難しいからやめてくれ〜〜と思っていたけれども，クエリの数を見ると普通にやるだけで通ってしまいそうなことに気がつく．

多分これはあまり早くない実装だとは思うけど，生徒ごとに知っている点数のデータとどの生徒がどの生徒の情報を知っているかの二次元配列を作っておき，点数を知った際はチェックを入れ，点数を記憶する．
出力については，知っている点数と全体から引いて残っている点数をうまく用いて計算する．ただし，すでにその生徒の点数を知っている場合は，その点数を答えなければいけないので，2次元配列で管理しているものをチェックしてから行う．最大として考えうる点数としては，推測する人以外の人が0点を取ったことにして，100点以上残っていれば100点だし，そうでなければ残った点数とした．最小として考えうる点数としては，推測している人以外の人が100点をとったことにし，推測している人以外の人で点数を埋めきれるなら0点，そうでないなら余った分を出力というようにした．

一発で通ってよかった．

N = int(input())
st = [int(input()) for _ in range(N)]
sumscore = sum(st)
table = [[st[i]] for i in range(N)]
knowtable = [[False for i in range(N)] for i in range(N)]
for i in range(int(input())):
    a, b, c = map(int, input().split())
    b, c = b-1, c-1
    if a == 0:
        table[b].append(table[c][0])
        knowtable[b][c] = True
    else:
        if knowtable[b][c]:
            print(table[c][0], table[c][0])
        else:
            knowpeople = N - len(table[b])
            res = sumscore - sum(table[b])
            minscore = max(0, res - (knowpeople - 1) * 100)
            maxscore = 100 if res >= 100 else res
            print(minscore, maxscore)

で，実際はこの後B問題をときました．

この時点で大体2時間が経過しており，一応みんなが言っていた5完は達成できたので，少し安心．


F，G，H問題を簡単に読み，F問題しかわかりそうになかったので，F問題に着手．
最初はなんかまじめに実の数を数えようとしていて，dfsを実装して，いろいろ試していましたが，ダメでした．
その後，紙にひたすら書きまくってシミュレーション．本当にプログラムを書いているというよりは，簡単な例でひたすら試行錯誤するゲームでした．


最終的には，1の実につながっている枝の本数をしらべて，それが1ならばA，そうでないなら，ちょっと分岐してあげるだけでOKでした．

N = int(input())
br = N-1
root = 0
for _ in range(N-1):
    s, t = map(lambda x: int(x)-1, input().split())
    if s == 0 or t == 0:
        root += 1
 
if root <= 1:
    print("A")
    exit(0)
else:
    if root % 2 == 1:
        print("A" if (br - root) % 2 == 0 else "B")
    else:
        print("A" if (br - root) % 2 == 1 else "B")

終了10分前にこの問題が解けたのですが，解けた瞬間に脳汁が吹き出すような思いになりました．すごく気持ちが良かった．多分このコンテストの中で一番興奮した瞬間だったんじゃなかろうか．

そして，G問題を見て，多分ダイクストラだなあと思って，H問題を見て，累積和使えそうだけど，オーダー的に間に合わないなこれww って言って，おしまい．6完でした．


総計20WAの31位，なんとか上半分に入れたので良かったです（Bのミスがなければ，当然もっと早かったわけですけど．．．）

当然最多WAだった．表彰してほしい（？）


まあ，私のコンセプトとして，時間内に解き切ることが大事だと考えているので，あまりWAの数とかは見ないようにしているから，これは当然の結果だったのかもしれない．
とにかくチャレンジして通ったらラッキーくらいで投げている時もあるので，行けそうな限りはとにかく挑み続ける．それでなんとかなったから，本当に良かった．

表彰と解説

表彰はとりあえず関係な…

と思ったら，某勉強会から仲良くしているいしづちゃんがD問題FAしてた．
てか，彼は今回活躍しすぎでしょ（途中まで5位以内に入ってたところを見ていた）

僕もFAスタンプ欲しかったです（本音）

chokudaiさんによる解説．
なんと，私の真正面でchokudaiさんが解説するという事が起こって，少しにやけた（私は会場真ん中の席，実質一番前でしたので，すごく良く見えた）

とりあえず解けた問題については，自分の解いた方法が想定されたものだったのかを確認．D問題の最小値，最大値の取り方，E問題の解法が若干怪しかったかも．（D問題の最小値最大値はもう少し綺麗に計算できるかも）

G問題はなんとなく言っている意味がわかったけど，グラフにこれまで着手していなさすぎて，データをどうもたせるのかがまだ良くわかっていなくて，理解できたけど，実装できそうにないです…．
H問題は自分が想定したところとしゃくとり法を使うところまでは覚えているけど，そこからの処理をいまいち覚えていないw

でも，時間をかけて考え抜けば，2つともそのうち解けるような気がした．
解けていれば焼き肉は確定したわけだし… くやしいよね．
実力不足なのは，わかっていたけれども！ もっとつよくなりたい．

そしてライブコーディングが始まる．G問題．
タイピングはや…！
って感想が真っ先に．

あとやるだけっていう話があったけど，chokudaiさん結構苦戦されていましたね…

あとマイク台がなくてあたふたしてる様子が，正面からよく見えたので（私最前列だったので）少し面白かった．

 

懇親会

誰にあったのかよく覚えてない（興奮しすぎていたので）
DDRと太鼓の達人はダメです（どっちもあまりプレイしたことがない）
ビートマニアにしよ？（ビートマニアもそんなにうまくないですけど）

あとちょくだいさんのDDR，太鼓の達人の様子見ていましたけど，結構うまくてびっくりした．次回までに練習しておかないと（ただ，バー無しはきついので，家庭用DDRはやっぱり別物）


書道コーディングは2つくらい投稿しておいた．

あと，C++むーりーって言ってたら，私も無理ですよ！ pythonで解いてます！ って人がいて共感した．自分以外にpython書いてる人がいるっていうのはちょっと感動です．今回の会場ではいないと思っていたから．
ちなみにコード見ればわかりますが，6問全て結局pythonで通しています．

川柳．

これ具体的にはこの問題のことを言ってる．arc036.contest.atcoder.jp

この際Javaなら通ってpythonでは通らないつらい経験をしたのでした．
といっても多倍長整数扱えるから，脳筋解放できてる時もあるので，一概にいい悪いと言えないんですけどね．（結局時間内に間に合うように，できるだけ短く書ける言語がベストということ，私はそのためならどの言語でも書く気でいる）

それと懇親会では，chokudaiさんとめぐるちゃんの話をしたり，notさんやけんしょーさんなどなんか雲の上の人たちとお話できたり，某勉強会でお会いしたLay_ecさんとか，ENIXERvsREXINEさんとか，宇宙ツイッタラーXさんとか，あと高和さんとかその他のフォロワーさんともちょいちょいお話したりと，楽しかった．けんしょーさんがAtcoderマンになってるのめっちゃ面白かった．これが，やるだけ… やらない人との違い…！
リクルートのお姉さまがたも少し変わった人が多くて，面白かったです．

私は基本的にいしづくんとお話しながら楽しんでましたけどね．彼，川柳でも表彰されるし，今回大活躍すぎるでしょ（めっちゃ持ち上げてる）

タンブラーは最後の一個を無事ゲット．

あ，ちなみに先ほどおうちに帰って開けてみました．
うん，今度から多用します．

ただ，タンブラー取りに行くためにピザ1枚しか食べられなかったことと，寿司の存在を認知できなかったのが非常に残念．

タンブラー優先探索と揶揄されるなど（）


 

まとめ

オンサイトは新鮮で，非常に楽しかったです．ネットでごちゃごちゃとプログラムの話をするのも好きなのですが，リアルであうとやっぱり違うw
私は話し下手なので，少し引っ込み思案になってしまいましたが…＞＜ それでも頑張っていろいろな人とお話したつもりです．
学生のうちはこれでもう参加する機会がなさそうですが，来年以降は東京にいる予定なので，そういうイベントにちょくちょく参加したいですね．
（できれば主催できるような能力がつけられるといいんですけどね，私はまだ問題を作り始めたところなので，2年位先になりそうですけど）

とても良い刺激になり，若干モチベーション落ちかけていたんですけど，これまで解けなかった問題に挑戦してみようとか，そういうモチベーションがかなり上がってきました．
CodeForcesをまずは青コーダーになることがひとまずの目標です．しばらく参加できていないんですが，topcoderよりは出やすいかなと．（topcoderは未だにシステムが良くわかっていない）


そんなわけで，長くなりましたが，この辺りで締めさせていただきます．*1
オンサイト，また参加したいゾ！！！！ そのために参加しても恥ずかしくない実力をつけていきましょう．
夢はでっかく，最強のpython使いで！

追記

忘れてた．

*1: 本当はこの後，東京観光の話を書こうと思いましたが，この時点で9000文字を超えているので，次の記事に分割いたします．