2017-11-02

運を引き寄せた話。(DDCC2017予選通過！)

DDCC2017の本戦に、出場できることになりました！！

#DDCC2017 の本戦に出られることになりました！！予選は222位でした。本戦通過かどうか分からなくて問い合わせたのですが、なんと私には『手違い』で連絡が漏れていたみたい。多分問い合わせなかったら本戦出れなかったので、問い合わせて本当に良かった。
— prd_xxx (@prd_xxx) 2017年10月26日

※Twitterアカウントを急遽作ったのでよろしければフォローお願いします。

今日書きたいことは上のツイートに割と凝縮されていて、私がアクションを起こさなければ、本戦のチャンスを逃していたということになる。

幻の切符

出場枠は、2019卒100名、その他一般枠100名。
少し就活生に有利になっている。(企業がやってるから、それはそうよね)
むしろ、就活生以外に100人も枠をもらえるなんて、かなり太っ腹だと思う。

2019卒とその他の人口比は分からないけど、仮に2:8だとしたら、一般枠のボーダーはだいたい125位ぐらいかな、と思ってた。
つまり、私の222位という順位では、2019卒除いて80人ぐらい辞退してくれないと回ってこない、絶望的な遠さだった。
私が本戦に出れることになったのは、これだけでも相当な奇跡だとわかる。
実質、回ってくることはないだろうと、諦めていた。

Web予選から2週間後くらい、たまたまTwitter上で「DDCCのボーダーラインがかなり繰り上がっている」という話題を目にした。
(Twitterアカウントは当時なかったけど、コンテストのたびに検索したりして勉強させてもらってた)
そこで、DDCCでさらに検索すると、一般枠は221位まで通過しているらしいとの情報を得た。
あれ、自分、何位だっけ？と順位表を見て、心臓が飛び出た。

祈った日々、悶々とした日、踏み込んだ日

当然それからというもの、通過メールが来てないか、敏感になる。
仕事から帰っても正直過去問を解くどころではなかった。

そしてその日はきた。でも、こなかった。

223位の方が、Twitterで通過報告をしていた。
思わずガッツポーズが出た。

でも、私のメールボックスには来ていない。
もちろん、Twitterで何人かが注意していたプロモーションタブも見たし、念のため持ってるGmailアカウントは全部みた。
まあ、明日になれば大丈夫だよね、のノリでその日は寝た。

翌日、やっぱり連絡は来ていない。
何かがおかしい。ざわ... ざわ...

色々と疑心暗鬼になってしまう。
もちろん仕事は集中できない。
私も通過メールを受け取って、ヨッシャー！と歓喜し、本戦対策に入りたいのに。

いざ問い合わせようと思ったとき、窓口は電話しかなく、平日の10-17時だけだったことを知った。
時刻は19時。なんたる不覚。

翌日。昼休み、やっぱり通過メールは来ていないことを確認し、運営へ電話。

まずは「本戦通過の状況について確認したい」と伝えた。
「19卒はまた繰り上げ者が出たところだが、一般枠100人はすでに出場者が決定した」の情報を得た。
ワオ！そんなこと、あってはならない。

ボーダーラインについても聞くと、一般枠は220位までの人にご案内しましたとのこと。
(あれ、持ってる情報と違うぞ？？)

はあ、そうですか。。
(いや、そうじゃない！根暗サーチで仕入れたネタをぶつけるとき！)

「私は予選222位のprd_xxxですが、Twitterで223位の方が通過報告しているのを見ました。順位の入れ違い等起こってないでしょうか？」
「本当に220位までで終了、なら納得できるのですが。本当のボーダーラインはどこでしょうか」

申し訳ありません、調べて折り返します、とのこと。
クソ！と思ったが、同時にしてやったりという気持ちに少しなった。

だがまだ安心はできない。
やはり仕事は集中できない。
疑心暗鬼になりすぎて、自分という存在がもみ消されるのではないかとも思った。

17時前、電話がきた。
とても低姿勢な話しぶりの女性に説明を受けた。
「『手違い』がございまして、通過の連絡を差し上げたつもりが、行き届いていませんでした」
「prd_xxx様に本戦に出場していただきたく思います」

やった！2回目の本当のガッツポーズでた。

自分がクレーマーだったら、
「なぜ手違いが起こったのか」「なぜ折り返しの連絡に時間がかかったのか」等、追求してたかもしれない。
でも、DDCC本戦に出られることの喜びに比べたら、どうでもよくなった。
なお、本当のボーダーラインは、やはり223位とのことだった。

予選は終わっていたので成績は変えられないけど、執念で運命を変えた。

何もしなければ本戦に出られなかった世界線に落ちるところだったけど、それを捻じ曲げて自分の行きたい世界線を引き寄せた。

夢が現実になるって、こんな感じなのか。

不思議な縁

前の記事でもさらっと触れたのだけど、講演がかなり楽しみ。

3者とも、画面の向こうでしか見ない、凄すぎる人！！
凄すぎて凄さがわからないレベルを凌駕した凄さ。
いや、表現できる語彙がない。ヤバイ。

私は2012年あたりから、観る将棋ファンになった。
電王戦がはじまって、米長永世棋聖とボンクラーズが戦った頃から。
コンピュータvs棋士の構図を通じて、棋士のひたむきな姿勢に惹かれていった。

コンピュータ将棋プログラムはだいぶ昔にBonanzaのソースを読もうとしたことがあったけど全然解読できなかった。
私のような挫折だらけのプログラマからしたら、山本さんみたいにコンピュータ将棋で世界一になって維持し続けるなんて、想像もつかない。

西尾先生も、YouTubeの四間飛車講座がわかりやすくて、お世話になった。
棋士の時点で凄すぎるのだけど、棋士の中でも研究熱心と慕われてる上に、ギター極めたりとかしてる。

そして言わずと知れたchokudaiさん。AtCoder作ってる神。
競技プログラマの憧れ。

もちろん、本戦の大会も楽しみ！(こっちがメイン)
というか、明日、いつも順位表でしか眺めない猛者達と同じ舞台に立てる(座れる？)ってのが、本当にヤバい。
自分がこの中に混ざっていいのだろうか、という気持ち。

いやー本当に楽しみ！
エンジョイ勢(?)なりに、いつも通りの力を出せるように頑張りたい！
奇跡に感謝。

以上、拙文・長文でしたが、読んでいただきありがとうございます。
それでは明日よろしくお願いします！！

2017-10-26

CODE FESTIVAL 2017 qual C

コンテスト参加記

3日ぐらい前のやつ。

ところで、先日のDDCCの本戦、辞退者が多くてどんどんボーダーラインが繰り上がってる、と風の噂。
行けたらぜひ本戦行きたいので、かな〜り気になってる。
ちなみに10/26 1:00現在、予選222位の私には連絡なし（´・ω・`）

結果

A,B,Cの3完。タイム19:43。395位。
パフォーマンス1782(highest!)、レート1303→1367(highest!)(+64)

A,Bで少しモタついてしまい600位ぐらい → Cで冷静に挽回できて300位ぐらい。
あとはDの700が難しく、あまり順位が下がらず救われた。(救われてはいけない)
どうも、あるレベル(400-500点?)より難しい問題だと、手も思考もフリーズしてしまうのをなんとかしたい。

A - Can you get AC?

2〜5文字までの入力があって、文字列'AC'を含むかどうか。

S = input()
print('Yes' if 'AC' in S else 'No')

はい。
なんだけど、python のinのイディオムが咄嗟に思い出せずにググった。。
ゴリゴリとforループ回した方が早かったかも。
ど忘れコワイよー。

B - Similar Arrays

整数の数列が入力として与えられて、各項が±1の範囲の整数になってる数列を「似ている」数列と呼ぶとき、
似ている数列の中で、全ての項の積が偶数になるものがいくつあるか。

これ、最近の200点にしては難しかったので、焦った。体感300点ぐらい。

N = int(input())
src = list(map(int,input().split()))
 
whole = 3**N
even = 0
for i in range(N):
    if src[i]%2 == 0: even += 1
 
print(whole - 2**even)

コード自体は、一言で言うと、
偶数の数を数えて、3^Nから2^[偶数の個数]を引いてるだけ。

なぜそうなるのか。プチ解説

各項、+1,±0,-1の3通りが許されるので、「似ている」数列は全部で 3^N 通りある。
この問題は偶奇だけを考えれば良いので、似ている数列では、
「奇・偶・奇」または、「偶・奇・偶」がN個並んでいることになる。
内訳は、数列に偶数がe個あったとすると、
「奇・偶・奇」がe個、「偶・奇・偶」が(N-e)個になる。

整数どうしの積は、
奇数同士はいくら掛けても奇数 ↔︎ 偶数が1つでも含まれていれば偶数
という性質がある。
これを使って、全体から「奇数のみからなる数列の個数」を引く と良さそう。

「似ている」数列の中から、奇数のみからなる数列を作るには、

(N-e)個の「偶・奇・偶」については、真ん中の奇数を取るしかない。1通り。
N個の「奇・偶・奇」については、どちらかの奇数が選べるので、2通り。

奇数のみからなる数列は、
1^(N-e) * 2^e = 2^e 個。
つまり、答えは全体から引いて
(3^N - 2^e) 個。

ちなみに、Nが10と小さいので、3^Nを全探索しても良い、という問題でした。

C - Inserting 'x'

文字列が与えられて、'x'と言う文字を何回か挿入して回文になるなら、その最小回数を出力し、回文にならなければ-1を出力する問題。

これはB問題とは逆に、400点にしては少し簡単に感じた。
むしろBより楽だったかも。

S = input()
l = 0
r = len(S)-1
cnt = 0
while l < r:
    if S[l] == S[r]:
        l += 1
        r -= 1
    elif S[l] == 'x':
        l += 1
        cnt += 1
    elif S[r] == 'x':
        r -= 1
        cnt += 1
    else:
        cnt = -1
        break
print(cnt)

コード見てもらえばわかると思うけど、lとrの添字を文字列の頭とお尻に設定して、そこから挟み討ちのようにlは増やし、rは減らしていく方針。
途中、lまたはrのうち一方が'x'だったら、'x'のカウントを1増やして、'x'だったほうの添字を進める。
lとrが異なっててどちらも'x'でないときは、いくら'x'を挿入しても回文になり得ないので、-1。

whileの終了条件が少し不安なままsubmitしてしまったのはちょっと秘密。
実際はもしl==rだとしても同じ文字を参照するから変にカウントは増えない。大丈夫。

ところで、これはしゃくとり法の一種なのかな？

よくあるしゃくとり法って、頭をr、お尻をlって決めて、しゃくとり虫みたいにlやrを進めていくイメージ。
今回のやつは、
ビヨーンと最大に伸びきったしゃくとり虫が、縮んでいって最後には無になるイメージ。

しゃくとり法は単純な割に、実はO(N)と知って、あなどれないと思った。
この手の問題のときには優先的に思い浮かべることにしてる。

2017-10-19

Atcoder Beginner Contest 075

ABC コンテスト参加記

5日ぐらい前のやつです。

結果

A,B,Cの3完。タイム23:33。302位。
レート変動なし。

感想

水色コーダーになってから初めてのABC。
これから青コーダーを目指すにあたってサクッと全完する... つもりが、
D問題で迷宮に陥り、時間切れ。
精進しなきゃ。。

A One out of Three

A - One out of Three

素直にif-elseする問題。(説明になってない)

A,B,C = map(int,input().split())
if A == B: print(C)
elif B == C: print(A)
else: print(B)

すごいと思ったのが、if文を使わずにXOR演算で print(A^B^C) みたいに解いた人がいたらしい。
確かに、同じ数を偶数回XORするとその数は消えるから、答えが残るね。
絶対に思いつかないな〜。

B Minesweeper

B - Minesweeper

いわゆるマインスイーパの爆弾の位置が与えられて、空きマスについて、8近傍に爆弾がいくつあるかを求める問題。

これも基本的なif-elseとfor文が使えればできそう。
でもABCのBにしては実装量が少し多い。

H,W = map(int,input().split())
src = [input() for i in range(H)]
 
ans = []
for row in src:
    ans.append(list(row))
 
dxy = [(-1,-1),(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1)]
for y in range(H):
    for x in range(W):
        if src[y][x] == '#': continue
        c = 0
        for dx,dy in dxy:
            if x+dx < 0 or x+dx > W-1 or y+dy < 0 or y+dy > H-1: continue
            if src[y+dy][x+dx] == '#': c += 1
        ans[y][x] = c
 
for row in ans:
    print(''.join(list(map(str,row))))

2行目のsrcに文字列の配列を読み込んでいるけど、
Pythonだとsrc[0][1] = '1'みたいな文字列への代入ができなくて、
仕方なく答えを書き出す用のansという配列の配列を用意してる。
最終的にansを結合して出力してる。(なんか微妙な気が。。

あとは、8近傍の調べ方がいくつかテクがあるっぽい。
解説のソースコードを抜粋すると、↓の書き方だった。

const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};

でもこれ、うまく説明できないけど、なんかモヤっとする...。
dx[i]とdy[i]はセットで意味をなすので、(dx[i],dy[i])みたいにまとめたいと思ってしまう。

というわけで、せめてもの抵抗として(笑) (dx[i],dy[i])とタプルでまとめたコードを貼り付けた。
でも、カッコで囲ってるぶん、タイプ数が少し多いような。
競プロは早さを競うのだからうだうだ言ってられませんがな。

次からは素直にdxとdyでやるか。(ズコー

ちなみに、上で載せた私のコードは実はブログ用に書き直してて、本番でAC取ったのは愚直なif-elseの山。

(おまけ)ACは取ったけど載せるのをためらったコードは↓
Submission #1682548 - AtCoder Beginner Contest 075

C Bridge

C - Bridge

二重辺や自己ループのない無向連結グラフがあって、取り除いたら連結じゃなくなる辺がいくつあるか。
以下私の回答。

N,M = map(int,input().split())
es = []
for i in range(M):
    a,b = map(int,input().split())
    a,b = a-1, b-1
    es.append((a,b))
 
parent = None
def root(a):
    if parent[a] == a:
        return a
    else:
        parent[a] = root(parent[a])
        return parent[a]
def is_same(a,b):
    return root(a) == root(b)
def unite(a,b):
    ra = root(a)
    rb = root(b)
    if ra == rb: return
    parent[ra] = rb;
 
ans = 0
for i in range(M):
    parent = [k for k in range(N)]
    for j,e in enumerate(es):
        if j == i: continue
        a,b = e
        unite(a,b)
    a,b = es[i]
    if not is_same(a,b):
        ans += 1
print(ans)

Union-Findを使って解いた。
Union-Findは、競プロ歴5ヶ月の私が知ってる知識をざっくり説明すると、

グラフのある頂点とある頂点が繋がってるかどうか高速に判定するよ
辺がない状態から、辺を追加しながら構築するよ。構築の途中でも判定できるよ
判定も追加もほぼ定数時間(ちょうはやい)。アッカーマン関数(とてもでかい)の逆数だとか
初期化するのだけO(N)かかるよ(N:頂点数)

上記コード中に出てきたroot()、is_same()、unite()がUnion-Findだけど、
スニペットに入れてたやつそのままなのでかなり楽できた。

あとは、全ての辺をループして、辺eを除いたグラフでUnion-Findを構築して、
辺eの両端が繋がってるかを判定していけばいい。

計算量は、辺ごとにUnion-Find初期化+構築でO(N+M)なので全体でO(M(N+M))かな？
NもMも小さいので大丈夫！

ちなみに、想定解ではUnion-FindじゃなくてDFSで解いてたみたい。
DFSは思いつかなかったので両方思いつくようになりたい。

2017-10-13

2部グラフ判定問題

アルゴリズム

(2024/03/14 更新) 本記事で扱われているコードの上位互換となるコードを書きましたのでご確認ください
グラフの各連結成分が二部グラフかどうか解析するモジュールを書いた - ごりちゃんがゆく

先日のコドフェで、2部グラフってのを扱う問題が出たので、勉強してみた。

2部グラフとは

(雑な説明、ご容赦ください)
いくつかの頂点があって、それらを辺で繋いで考えるモデルをグラフという。
棒グラフとか、円グラフとか、折れ線グラフとかのグラフではなくて、「グラフ理論」のはなし。

グラフ理論のグラフにも種類があって、2部グラフはその中の1つ。
どんな特徴があるかというと、頂点を2つのチームに分けたとき、「全ての辺が、自分チームと相手チームを結んでいる」ように分けることができる。

2部グラフの例
2部グラフじゃない例

例えば、男女の複雑な三角関係や四角関係(!?) を図に書いたとき、男女間でしか線が引かれていなければ2部グラフと言える。
男男間、女女間にも線が引かれていれば、2部グラフじゃないかもしれない。
かもしれないと言ったのは、別の何かしらの基準で(例えば右利きの人と左利きの人みたいに)チーム分けしたときに、「全ての辺が、自分チームと相手チームを結んでいる」ふうにできれば、2部グラフだから。

よく考えたら、三角関係が含まれていたら、2部グラフになり得ないっすね。^^;

2部グラフ判定問題の解き方

2部グラフ判定問題とは、与えられたグラフが2部グラフかどうか、という問題である。
「蟻本」の94ページに、C++のコードが載っていたので、意訳してpythonで書いてみた。

全ての辺において、一方が黒、もう一方が白となるように頂点を塗ることを考える。
2部グラフの場合、ある頂点の色が黒だとすると、そこに隣接している頂点は一意に白と決まる。
最初は適当に1箇所を黒で塗って、あとはDFS(深さ優先探索)で白、黒、白... とどんどん塗っていって、矛盾がなければ2部グラフ。

難しそうに思えて、意外と単純！

# 再帰の深さが1000を超えそうなときはこれをやっておく
import sys
sys.setrecursionlimit(10**7)

# 入力のつもり。esはよくある隣接リストで辺を表したもの。
N = 5
#es = [[1,2,3],[0,2],[0,1],[0,4],[3]] # False
es = [[1,3],[0,2],[1,3],[0,2,4],[3]] # True

#n個の頂点の色を初期化。0:未着色、1:黒、-1:白
colors = [0 for i in range(N)] 

#頂点vをcolor(1 or -1)で塗り、再帰的に矛盾がないか調べる。矛盾があればFalse
def dfs(v,color):
    #今いる点を着色
    colors[v] = color
    #今の頂点から行けるところをチェック
    for to in es[v]:
        #同じ色が隣接してしまったらFalse
        if colors[to] == color:
            return False
        #未着色の頂点があったら反転した色を指定し、再帰的に調べる
        if colors[to] == 0 and not dfs(to, -color):
            return False
    #調べ終わったら矛盾がないのでTrue
    return True

#2部グラフならTrue, そうでなければFalse
def is_bipartite():
    return dfs(0,1) # 頂点0を黒(1)で塗ってDFS開始

print(is_bipartite())

ちなみに、2部グラフは英語では、bipartite graph というみたい。
biは"2"、partiteは "partに分ける"ってことかな？(適当)
is_nibu() とかでもいいんだけど、なんかダサかったので(笑)

おまけで、再帰なし版も載せておきます。

# 入力のつもり。esはよくある隣接リストで辺を表したもの。
N = 5
#es = [[1,2,3],[0,2],[0,1],[0,4],[3]] # False
es = [[1,3],[0,2],[1,3],[0,2,4],[3]] # True

#n個の頂点の色を初期化。0:未着色、1:黒、-1:白
colors = [0 for i in range(N)]

#2部グラフならTrue, そうでなければFalse
def is_bipartite():
    stack = [(0,1)] # (頂点、色)のタプルをスタックする。最初は(頂点0, 黒(1))
    while stack:
        #スタックから最後に追加された(頂点, 色)をpop
        v,color = stack.pop()
        #今いる点を着色
        colors[v] = color
        #今の頂点から行けるところをチェック
        for to in es[v]:
            #同じ色が隣接してしまったらFalse
            if colors[to] == color:
                 return False
            #未着色の頂点があったら反転した色と共にスタックに積む
            if colors[to] == 0:
                 stack.append((to, -color))
    #調べ終わったら矛盾がないのでTrue
    return True

print(is_bipartite())

DFSを初めて覚えたとき、再帰なしのコードで覚えたので、こっちのほうが個人的に馴染みがある。
再帰は深さとか気にしなきゃいけないし、動きをイメージしづらいし、デバッグしづらい、って意識があって、あんまり書きたくないと思ってた。
でもこうやって比較すると、なるほどこのDFSだと再帰のほうがコードがすっきりしてる。
(イメージのしづらさとかは置いといて)
引き出しは多いほうがいいから、両方書けるようになっておこうっと。

実践例

さて、これでようやく、先日のコドフェ予選BのC問題が解けるようになりました。
問題はこちらです。
C - 3 Steps

(意訳)
N <= 10⁶ 頂点を、M <= 10⁶ の辺で結んでいる。
連結な無向グラフで、自己辺や多重ループはない。
3つの辺を経由してたどり着ける(＝あいだに2頂点を経由する)2点を全て結ぶように辺を追加するとき、最大で何本の辺を追加できるか。

これ、解く方針がわかりませんでした。
N,M <= 10⁶ のサイズがネックで、私の思いつく解法だとどうしても間に合わない。
(全ての頂点から伸びてる辺、のそのまた先の伸びてる辺、を調べるだけで、 O(NM) ぐらい？にはなってしまう気がした。)
小手先の工夫でゴリゴリやって倒せる相手じゃなかった。

解説を見たら、魔法みたいな解法がありました！
どうも、探索で解くというよりは、グラフの性質を使って解く模様。
より詳しくは、解説を見てね。~~(私レベルには若干わかりづらい)~~

まず、距離が3辺離れた点を繫ぐということは、距離3が1になり、
同様に距離が奇数離れた点の間は2ずつ縮めることができて、そのうち辺を繋げる！
なるほどなぁ。。気づかなかった。。

そして、ここで、2部グラフが登場する。
2部グラフの場合、自分チームと相手チームを結んでいる辺しか存在しない。
どの頂点からも、奇数個の辺をたどって行ける頂点は相手チームで、偶数個の辺をたどって行ける頂点は自分チーム。
もちろん1辺の両端は異なるチームだし、3辺離れた頂点同士も、異なるチームになる。
とすると、この問題のルールにおいては、同じチーム同士はどうやっても結べない！

反対に、2部グラフでなければ、どこかしらの2点間は
奇数個の辺をたどっていくルートと、偶数個の辺をたどっていくルートが存在する
ということだから、全ての辺は、いずれ繋ぐことができる！

なので、結論は

2部グラフなら、黒・白と塗った頂点数をB,Wとして、B*W - M本。
2部グラフでなければ、全頂点間が結ばれるので、 N(N-1)//2 - M本。

になるらしい。
すっごーい　！！

早速、上で書いたコードをぺたりと貼り付けて、ACもらってきました！

import sys
sys.setrecursionlimit(10**7)
 
N,M = map(int,raw_input().split())
es = [[] for i in range(N)]
for i in range(M):
    a,b = map(int,raw_input().split())
    a,b = a-1,b-1
        es[a].append(b)
        es[b].append(a)
 
colors = [0 for i in range(N)]
 
def dfs(v,color):
    colors[v] = color
    for to in es[v]:
        if colors[to] == color:
            return False
        if colors[to] == 0 and not dfs(to, -color):
            return False
    return True
 
def is_bipartite():
    return dfs(0,1)
 
if is_bipartite():
    b = (sum(colors) + N) // 2
    w = N-b
    print(b*w - M)
else:
    all = N*(N-1) // 2
    print(all - M)

なお、2部グラフ判定のところ、再帰版ではAC取れたけど、
再帰なし版もsubmitしたら、テストケースが1つTLEだった。
ステップ数はさほど変わらないような気がするが、、ナゼだ。。
どなたか分かる方、ご教授ください。。。(考察放棄)

この問題のキモ

この問題、見抜かなきゃいけないことがたくさんありました。

N,M <= 10⁶ のサイズは、工夫したところで、隣の隣の、、みたいな探索は到底できないこと。
グラフの性質を使って計算で解く問題ということ。
奇数個離れた頂点なら、いずれ、全て結ぶことができること。
2部グラフかどうかで答えの方針が変わること。

2部グラフを知っていなきゃ解けない問題だったのだけど、
知らなかったとしても、3番目のポイントまで見抜いていなければ、どのみち解けなかったという。

ぐぬぬ。
精進します！

2017-10-09

CODE FESTIVAL 2017 qual B

コンテスト参加記

結果

A,Bの2完。タイム06:25。549位。
パフォーマンス1598、レート1259→1303(+44)

C,D問題、むずかった。。
そして全然できなかったのにレート上がっちゃった。
少し腑に落ちないと思ったけど、結局どちらも自力でできる内容じゃなかったので、ある意味実力通りか。
どうやったら、あの問題から、2部グラフなんて思いつくようになるんだろう。。。
というか、2部グラフってものは蟻本でさらっと出てきただけで存在を忘れてたし、使ったこともなかった。
次は絶対に解けるようにしとこう。

A XXFESTIVAL

A: XXFESTIVAL - CODE FESTIVAL 2017 qual B | AtCoder

末尾の8文字を除いてprint。

S = input()
print(S[:-8])

B Problem Set

B: Problem Set - CODE FESTIVAL 2017 qual B | AtCoder

N問の問題セットがあって、その中にM問の指定された難易度の問題が含まれているか。
以下、私の回答

import sys
from collections import Counter
 
N = int(input())
s1 = list(map(int,input().split()))
M = int(input())
s2 = list(map(int,input().split()))
 
c1 = Counter(s1)
c2 = Counter(s2)
 
for k,v in c2.items():
    if k in c1:
        if v > c1[k]:
            print('NO')
            sys.exit()
    else:
        print('NO')
        sys.exit()
print('YES')

pythonのCounterモジュールを使った。(個人的によく使う)
l = [10,20,30,20] みたいなリストを、Counter(l)とかやると、
{10:1, 20:2, 30:1} みたいなdict型に集計してくれるすごいやつ。
key:valueのうち、keyの方がもともとの要素で、valueの方が集計した個数。(たまに、どっちか混乱する。)

c2.items() でM問の必要な方をループして、N問の用意してある問題セットに1つもないか、問題セットが足りなければNOを出力。
ループが最後まで行けばYESを出力。
こんな感じでしたー。

2017-10-08

DISCO presents ディスカバリーチャンネルコードコンテスト 2017 予選

コンテスト参加記

概要

2019卒枠が100人と、その他の100人が本戦に進めるコンテスト。
本戦の告知(DDCC | ディスカバリーチャンネル)を見たら、イベントがすごく豪華。
特に対談のメンバーがすごい。皆憧れの人ばかり。
(将棋界と将棋プログラムのトピックは、ここ何年か、個人的に追いかけているので)
厳しいだろうけど、何としても本戦出たい！って思いで参加しました。

結果

A,B,C の3完。タイム10:20。222位。
C問題までは自分的にベストなパフォーマンスだった。
D問題は1submitしたけど、考察力が足りずWA+TLE。
その他枠の人、100人ぐらい辞退してくれないかな〜？？。。
まあ、そんな訳ないので、来年までに力をつけてリベンジするか。。

A,B問題

特に難しいポイントがないので省略。
ダースの12倍がグロス、その12倍がグレートグロスという単位があるのを初めて知った。

以下、私の回答
A - DDCC型文字列
http://ddcc2017-qual.contest.atcoder.jp/submissions/1656175

B 鉛筆
http://ddcc2017-qual.contest.atcoder.jp/submissions/1656644

C 収納

C: 収納 - DISCO presents ディスカバリーチャンネルコードコンテスト2017 予選 | AtCoder

N <= 100000 本の棒があって、長さCのケースに収納していくとき、ケースの最小数を求める。
ケースには1本か2本入れられて、2本入れる場合は[2本の和 + 1]の長さが必要。

以下、私の回答

N,C = map(int,input().split())
src = [int(input()) for i in range(N)]
src.sort()
 
l = 0
r = N-1
ans = 0
while l <= r:
    if src[l] + src[r] + 1 <= C:
        l += 1
    ans += 1
    r -= 1
print(ans)

ソートして左右から貪欲でいけた。
一番長いのを一番短いのと一緒に詰めることができれば、2本しまう。
そうでなければ、一番長いのを1本しまう。

例として、入力例1の C=10, L=[2,8,4,5]の場合。

ソートする。L=[2,4,5,8]
2+8+1 > 10 で、8は単独で入れるしかないので、8をしまう。ans=1, L=[2,4,5]
2+5+1 <= 10で、2と5が両方入るので、両方しまう。ans=2, L=[4]
最後に4をしまう。ans=3

こんな感じ。

実際は、lとrの2つのインデックスを操作すれば、配列の要素を消すことなく、シミュレーションできる！
計算量は、

ソートにO(NlogN)
貪欲なシミュレーションがO(N)

O(NlogN) なので大丈夫！

最後にちょっと脱線

このブログについて、本当は勉強したことをまとめていって自分用のノートにするつもりだったけど、気づいたら競プロの参加記になってた件。

まとめたいネタはいくつかあるんだけど、どうも、人が見て分かるような体裁にまとめるのが苦手というか、意外と骨が折れることが分かった。
記事にまとめるのより、過去問にチャレンジした方が楽しい ^^;。

まあ、無理せず、自分のペースでやればいっか。

2017-10-01

Kyoto University Programming Contest 2017

コンテスト参加記

結果

A,B の2完。タイム08:06。165位。
初の5時間越えのコンテストに参加するので、お菓子に飲み物と万全の体制で臨んだ。
なのに、C問題以降が難しすぎて、早々にダレてしまった。
これだけ時間があったら、せめてC問題は解きたかった...。
おのれ、京都大学ぅ〜。
後で解説きたら勉強させてもらおう...。

A Credits

A: Credits - Kyoto University Programming Contest 2017 | AtCoder

できるだけ少ない科目数で必要単位を取る場合の科目数を答える問題。

需要あるか分からないけど、コードペタペタしていく。

N,K = map(int,input().split())
src = list(map(int,input().split()))
src.sort(reverse=True)
ans = c = 0
for i in range(N):
    c += src[i]
    ans += 1
    if c >= K:
        print(ans)
        break
else:
    print(-1)

降順にソートして、貪欲に単位数を足していって、必要単位Kに達したらbreak。
全部足してもKに達しなかったら、-1。
Nは50までなので、計算量も余裕。

B Camphor Tree

B: Camphor Tree - Kyoto University Programming Contest 2017 | AtCoder

完全二分木の形のくすのきがあって、ある分岐Sからある分岐Tに登れるか。登れる場合は距離を出力。登れない場合は-1。

N,S,T = map(int,input().split())
 
n = T
ans = 0
while(n >= S):
    if n == S:
        print(ans)
        break
    ans += 1
    n //= 2
else:
    print(-1)

完全二分木の性質を知っていれば楽勝でした。
2で割れば、1つ親のノードに行けるので、Sを2で割っていってTにたどり着けるかどうか。
木の高さN=25なので、計算量も余裕。