純ブログ

ちょっとプログラミングしてる人のブログです。

日本情報オリンピック 2014/2015 予選にオープン参加した

コンテスト プログラミング 日記

タイトルの通りです.

結果を受けて追記しました. (2014/12/18)

カテゴリ分けしてなかったのでしました. (2016/01/12)

問題 1

やるだけ.

問題 2

これもやるだけ.

落としました.

問題 3

ある区画 (i, j) のいくつ西の小区画に雲があるか数える. 雲が上空にあるなら 0. 雲が上空にも西にもなければ -1.

行末に空白を出力しないように注意.

これも落ちた.

問題 4

dp[i][j] := i 日目に都市 j にいるときの疲労度の最小値

とすると,

dp[i][0] = 0,
dp[i][j] = INF (j > i),
dp[i][j] = min( dp[i-1][j-1]+D[j-1]*C[i-1], dp[i-1][j] ) (else)

という漸化式が立てられる (グラフを書いてみればわかる). min{dp[i][N]} が解.

問題 5

崩壊した城の 8 近傍のみ更新すれば良い.

問題 6

解けなかった.

感想

思ったより簡単だった. 6 問中 5 問提出, 3 完でした...

問題 2, 3 について (2014/12/18 追記)

提出ファイルをダウンロードして確認したところ, なぜか入力ファイルを提出してしまっていました.

本来提出するはずだったファイルとの diff をとってみたところ, すべてのケースで正解のものと一致しました. つまり, 提出ファイルを間違わなければ 5 完できていたようです.

ファイルを提出するときはしっかり確認しましょう (自戒).

CODE THANKS FESTIVAL 2014 A日程 参加記

プログラミング 日記 コンテスト

12 月 7 日にコワーキング・スペース MONO で行われた, (株)リクルートホールディングス主催のフェス型プログラミングコンテスト, CODE THANKS FESTIVAL 2014 に参加した.

会場到着からコンテスト開始まで

会場の最寄り駅に到着:

西と東を間違えて

14 階のエレベータホール前で

受付開始. T シャツを貰って席につく.

ハンドルネームを誤字る. (jun でも良かった)

目標:

5 問正解でトートバッグがもらえると聞いて

chokudai さんにサインを貰う.

こんな感じでした.

コンテスト

A 問題

頭が回ってなくて, 入出力例を見てようやくカメとツルの足の本数を把握する. 00:55 (開始から 55 秒後, 以下同様) に Accepted (AC).

B 問題

読む. あー, 見たことあるけど解いたことないなー. 貪欲で行けないかな～. (それ以上考えてなかった.) 全探索でいけることに気づいて実装. main 関数の最初で宣言してた変数を for の中でまた宣言してて 2 Wrong Answers (WA). そのあと気づいて修正, 10:45 に AC.

C 問題

めっちゃ簡単, やるだけ. 13:20 に AC.

D 問題

なぜか全探索を実装, 当然 Time Limit Exceeded (TLE) (WA なケースもあった. 1 つだけ AC). a,b,s,t の大小関係を全通り図に書く. それを見ながら間違った条件分岐を実装, WA (また 1 つだけ AC だった). 冷静になり, えっなにこれはと思いながら修正, 55:26 に AC.

ここまで順調

1 時間以内に 4 完, これは 5 完いけるでしょ, と思った.

E 問題

何も考えずに O(RCN^2) な全探索を実装, 当然 TLE. そういえば剰余って遅いんだっけ. そう思って if 文に書き換えるも TLE. (時間計算量は変わってないので当たり前.) 入力時に石像の状態求めておけば早くなるんじゃね? などと思って変更, 提出. なんか Runtime Error (RE) だらけ.

あれ?

5 完阻止されている気分になる.

F 問題

一度 F 問題を読んでみる. いろいろ図を描いてるうちに, グラフっぽい, 自分より上の人数数えればいいんじゃね? と思いつく. 幅優先を実装, しかし WA. 順位関係の情報に高橋君 (参加者 1) が入ってない (1 3 とか 3 1 とかがない) ことあるんじゃね? と思って修正するも WA. 三項演算子を if 文に変えてみる. 当然 WA. 提出結果をよく見てみると, (参加当時) 最後の 5 つだけが WA になってた. えー, コーナーケースあるの...? なんだろう...

また E 問題

列のループの条件をミスってて無限ループしてた. 修正して提出, WA (と TLE). オーダーを下げる方法が思いつかない.

もう一度 F 問題

コーナーケースを考えてみる. ...... 思いつかない. 適当に弄って投げまくる. もちろん全部 WA (最終提出は 174:50).

諦め

トートバッグもらえないのめっちゃ悔しかったけど, どうしようもなかった. つらい.

最終結果

4 完 (A, B, C, D), 4 WA (B, D 各 2 WA), 52 位だった. 目標 (5 完) 達成ならず... (悔しい) ちなみに, E, F はそれぞれ 6 WA した.

(切実)

コンテスト解説

A, C は解説と同じだった. B は最初の 3 つを貪欲に選んで良かったみたい. D は if 文使わない方法もあるんだ, へー, と思った (小並感). E は, 各操作が可換なことから, 操作を忘れなかった場合を求めておいて, それに忘れた操作を Undo (?) すれば良いと聞いて, 若干そんな気がしてたようなしてなかったような感じになった. F はコーナーケースでも解説されるでしょと思ってたけど,そんなことはなかった. G, H はチラ見しただけだったのでよく聞いてなかった (良くない. H のハッシュは聞いてた).

懇親会

ひたすらコミュ障していた.

感想

トートバッグもらえないのめっちゃ悔しかった.

来週は CODE THANKS FESTIVAL 2014 B日程にオープン参加するつもり日本情報オリンピック 2014/2015 予選の方に参加することにしました (2014/12/13 追記).

ACM-ICPC 2014 国内予選参加記

プログラミング 日記 部活・サークル コンテスト

一昨日行われた ACM-ICPC 2014 国内予選に, KCCT-A2014 というチーム (自分 @nahcnuj, @akahana_1, @summation_hsp2) で参加しました.

自分は B 問題を解きました. 問題文を読んでやるだけっぽいと思ったので, すぐに実装をはじめましたが, 石の落下処理の実装に手間取りました. 入出力例が合うことを確認して, Data No.1 の出力を提出したところ Wrong Answer. 落ちるケースが分からないままコンテスト終了.

他のチームメンバが A 問題と C 問題を解いていましたが正答できず... 結果, 一問も正答することができませんでした.

来年の ICPC に向けて競技プログラミングの勉強をしていこうと思います.

自分が書いた B 問題のソースコードを貼っておきます.

#include <iostream>
using namespace std;

int field[10][5] = {{0}};   // empty is 0
int H;

// スコア計算および消去処理 返却値はその処理で得られたスコア
int calc() {
    int score = 0;

    for (int i = 0; i < H; ++i) {
        int count = 1, before = field[i][0], start = 0;
        for (int j = 1; j < 5; ++j) {
            if (field[i][j] == 0) continue;

            if (before == field[i][j]) ++count;
            else if (count >= 3) { break; }
            else { count = 1; before = field[i][j]; start = j; }
        }
        if (count >= 3) {
            for (int j = start; j < start+count; ++j) {
                field[i][j] = 0;
            }
            score += before*count;
        }
    }

    for (int j = 0; j < 5; ++j) {
        int spcount = 0;
        for (int i = H-1; i >= 0; --i) {
            if (field[i][j] == 0) spcount++;
            else {
                if (spcount > 0) {
                    field[i+spcount][j] = field[i][j];
                    field[i][j] = 0;
                }
            }
        }
    }

    return score;
}

int main()
{
    while (cin >> H, H) {
        for (int i = 0; i < H; ++i) {
            for (int j = 0; j < 5; ++j) {
                cin >> field[i][j];
            }
        }
        int score = 0, before = 0;
        do {
            before = score;
            score += calc();
        } while (score-before > 0);
        cout << score << endl;
    }
    return 0;
}

電算部 2014春合宿

日記 プログラミング 部活・サークル ゲーム

3 月 4 日から 2 泊 3 日の日程で合宿がありました. その合宿で, プログラミング班の自分がしたことをまとめます.

1 日目

部室にあるデスクトップパソコンなどの機材を合宿室へ移動させて環境を整えたあと, 事前に作ってきた AI でリバーシ風ボードゲームの大会（6 人参加, 総当り）をしました. リバーシ風ボードゲームのルールは, 通常のリバーシと次の 2 点が異なります.

  • 盤の大きさは 8×8, 9×9, ..., 15×15 のいずれか.
  • 使うとまだ石が置かれていない任意のマスに石が置ける“フリーコイン”がある.

自分は, 盤面にある自分の石の数をそのまま評価値に用いて, ネガアルファ法で探索しました. ただ, 常にフリーコインを考慮すると計算量が大きくなってしまうため, 通常のリバーシでパスする場面のみフリーコインを用いるようにしました. 合宿 3 日前から（1 日ぐらい自分なりに）本気出して作ったこの AI で大会に臨んだところ, 3勝2敗でした.

大会後はハッカソンをやる予定だったのですが, インターネットが接続できなかった*1ため, AI の修正や強化をすることになりました. 自分は, 図書館にあった『リバーシのアルゴリズム』という本のソースコードを写経しつつ, 9×9～15×15 の盤面やフリーコインの実装をしました.

2 日目

一日中, 1 日目に続いて AI の実装をしました.

3 日目

片付けや合宿室の掃除などのあと, もう一度リバーシ風ボードゲームの大会（8 人参加, トーナメント）をしました. 初戦は 10×10, フリーコイン 10 枚; 準決勝は 11×11, フリーコイン 10 枚; 決勝は 8×8, フリーコイン 5 枚（制限時間はいずれも 30 秒）でした. 自分は, 初戦を 57 対 43 で勝ち, 準決勝で 56 対 65 で負けました.

まとめ

リバーシしかやらなかった.

*1:普通は部室から合宿室へ LAN を通して, インターネットに接続する.

日本情報オリンピック 2013-2014 予選に参加した

日記 プログラミング コンテスト

12 月 15 日 13 時から 3 時間行われた，日本情報オリンピックの予選に参加しました。 本選に出場できるのは高校/高専 2 年生までですが，予選には誰でも参加できるので参加してみました。

続きを読む