へなちょここーだー

プログラミング初心者がtopcoderなどの競技プログラミングに挑戦。勉強したアルゴリズムなどを書いていきます。現在topcoder緑でcodeforces青。どちらもDiv1昇格を目指しています。

2015-05-01から1ヶ月間の記事一覧

101 Hack May'15

いやー全然ダメでした。205/556位、完答は1問のみと厳しい結果でした。悔しかったのでModerateまでは大会後にEditorialを見ずに解いた感じでは3問完答までは少なくともいけた・・・。まぁ、前回初参戦でbronze medalをとったので完全に浮かれてた自分が悪い…

Codeforces Round #303 (Div. 2)

初めてCodeforcesに参戦しました。結果は5問中4問正解で2826人出場した中で254位でした。そしてレイティングは1500 → 1704でCandidate Masterに!!ん?これってDiv.1じゃないか。#304(Div.2)にも参加する気でワクワクしていたのでちょっと複雑wまぁレイティ…

The Magic Lines

今回はHackerRankにて、The Magic Linesという大会に参加しました。結果は1/1292位!!とはいえ、同率一位が239人いて、自分は忙しかったので期限ギリギリにsubmitしたため時間を考慮すると230位でした。初めてコードの一部を補完する形式のコンテストに参加し…

UnKoder #04

GW最高。ってな訳でプロコン連日参加中。今回はUnKoder#04に参加して、19/36位でした。 Islands in Circle とってもシンプルなコードになりました。 int main() { int N, K, result; cin >> N >> K; if(N % 2 == 1){ result = min(K + 1, N); }else{ result …

XOR(排他的論理和)の計算

Grundy数を計算する際にXORの計算をしました。Exclusive orとか日本語では排他的論理和と言われているものですね。基本的なことですが、どうやって計算するのかを紹介します。 まずは基本から まずは表で計算結果を見てみましょう。 A B A XOR B 0 0 0 0 1 1…

Grundy数 その3

前回までにGrundy数についての説明をしました。Grundy数 その1 - へなちょここーだーaugusuto04.hatenablog.com Grundy数 その2 - へなちょここーだーaugusuto04.hatenablog.com 長くなったGrundy数の記事も今回でラスト。実際に使ってみます。 実践例 AtCo…

Grundy数 その2

前回はGrundy数とは何かを説明しました。Grundy数に関する基本的な求め方は前の記事をご覧ください。Grundy数 その1 - へなちょここーだーaugusuto04.hatenablog.com ただ、これだけではあまり多くの問題に使えないのでもう少し発展的な使い方を紹介します…

Grundy数 その1

Grundy numberについての勉強をしたので、そのまとめ(自分用のメモでもある)。ちなみにNimberとも言うみたいですね。実際にいくつかのゲームを考えながら説明をしていきます。最後の結論まで少し長いです。 そもそもGrundy数ってなんだろう 具体例は後で出…

WL-Algorithm

AtCoderで出題されていて、topcoderでも紹介していたのでちょっとまとめてみました。2人が最適な行動を行ったとき、勝つか負けるかを判定する単純なアルゴリズムです。 WL-AlgorithmというとWang-Landau Algorithmを指すことが多いようなのですが、今回はtop…

復習

AtCoder Regular Contest 038の復習完了。解説があるのがとてもありがたい! マス目と駒 全探索→メモ化再帰というところまではすぐに思いついたのですが、そっか判定は結構単純ですね。 今のマスが盤外or障害物→勝ち 次の番の人が負ける→勝ち 上記以外→負け …

AtCoder Regular Contest 038

ゴールデンウィークはコンテストに集中するチャンス! とウキウキでしたが惨敗でした。 A-カードと兄妹 100点 さすがにこのレベルの問題は簡単。 B - マス目と駒 0点 C - 茶碗と豆 0点 D - 有向グラフと数 0点 全部似たような問題なんですかね。3問とも2人で…

101 Hack April'15

勉強を始めてから約3週間、初めてコンテストに出場しました! その結果がこちら。 Rat Race (Easy) 20/20点 a / bがintになることを忘れるという凡ミスをして最初は焦りましたが、楽勝! Twisty Tuple (Moderate) 60/60点 最初は全探索を行ってタイムアウト…

累乗計算の高速化

HackerRankのAntiPalindromic Stringsを解くときにどうしても累乗計算がO(n)になってしまいタイムアウトになってしまっていたところ、凄くキレイで高速なアルゴリズムを発見! 高速な累乗計算 - あどけない話 これを使ってみました。 単純なxのn乗をmを法と…