あけましておめでとうございます(激遅)。 近況報告です。
高専を卒業した
落としていた某教科の再評価を無事にクリアし、3 月 18 日に高専を卒業しました。
奨学金申請の関係で成績を見たのですが、思ったより「優」が多くて驚きました。
続きを読むCODE THANKS FESTIVAL 2015 に参加しました. 昨年に続き 2 度目になります.
昨年達成できなかった 5 完.
n 完達成で景品がなかったのが少し残念でした.
やっぱりコミュ障してた.
頭回ってなかった. F の解説を聞いて, 偶奇で良かったのか...ってなった.
順位表を見て, 5 完勢の下の方にいたので底辺であることを再確認した.
CODE FESTIVAL にも参加してみたいし, 精進したいなーと思った. (というか, 予選突破講習会とかあったんですね...)
タイトルの通りです.
結果を受けて追記しました. (2014/12/18)
カテゴリ分けしてなかったのでしました. (2016/01/12)
やるだけ.
これもやるだけ.
落としました.
ある区画 (i, j) のいくつ西の小区画に雲があるか数える.
雲が上空にあるなら 0
. 雲が上空にも西にもなければ -1
.
行末に空白を出力しないように注意.
これも落ちた.
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]}
が解.
崩壊した城の 8 近傍のみ更新すれば良い.
解けなかった.
思ったより簡単だった.
6 問中 5 問提出, 3 完でした...
提出ファイルをダウンロードして確認したところ, なぜか入力ファイルを提出してしまっていました.
本来提出するはずだったファイルとの diff をとってみたところ, すべてのケースで正解のものと一致しました. つまり, 提出ファイルを間違わなければ 5 完できていたようです.
ファイルを提出するときはしっかり確認しましょう (自戒).
12 月 7 日にコワーキング・スペース MONO で行われた, (株)リクルートホールディングス主催のフェス型プログラミングコンテスト, CODE THANKS FESTIVAL 2014 に参加した.
会場の最寄り駅に到着:
I'm at テレコムセンター駅 (Telecom Center Sta.) (U09) - @yurikamome_info in 江東区, 東京都 https://t.co/mP1j4edAmC
— jun (@nahcnuj) December 7, 2014
西と東を間違えて
14階に辿りつけない
— jun (@nahcnuj) December 7, 2014
14 階のエレベータホール前で
誰が誰かわからんな?
— jun (@nahcnuj) December 7, 2014
受付開始. T シャツを貰って席につく.
座席番号71です
— jun (@nahcnuj) December 7, 2014
ハンドルネームを誤字る. (jun でも良かった)
ハンドルネーム誤字ってnahc■nujになってしまった
— jun (@nahcnuj) December 7, 2014
目標:
目標はn完です (n∈ℕ)
— jun (@nahcnuj) December 7, 2014
5 問正解でトートバッグがもらえると聞いて
5完目標にします(たぶんできない)
— jun (@nahcnuj) December 7, 2014
chokudai さんにサインを貰う.
蟻本に直大さんのサインをもらう参加者 (自分はちゃんと(?)チーター本に書いてもらいました) #codefes https://t.co/pngCDVqVOx
— jun (@nahcnuj) December 7, 2014
こんな感じでした.
頭が回ってなくて, 入出力例を見てようやくカメとツルの足の本数を把握する. 00:55 (開始から 55 秒後, 以下同様) に Accepted (AC).
読む. あー, 見たことあるけど解いたことないなー. 貪欲で行けないかな~. (それ以上考えてなかった.) 全探索でいけることに気づいて実装. main 関数の最初で宣言してた変数を for の中でまた宣言してて 2 Wrong Answers (WA). そのあと気づいて修正, 10:45 に AC.
めっちゃ簡単, やるだけ. 13:20 に AC.
なぜか全探索を実装, 当然 Time Limit Exceeded (TLE) (WA なケースもあった. 1 つだけ AC). a,b,s,t の大小関係を全通り図に書く. それを見ながら間違った条件分岐を実装, WA (また 1 つだけ AC だった). 冷静になり, えっなにこれはと思いながら修正, 55:26 に AC.
1 時間以内に 4 完, これは 5 完いけるでしょ, と思った.
何も考えずに な全探索を実装, 当然 TLE. そういえば剰余って遅いんだっけ. そう思って if 文に書き換えるも TLE. (時間計算量は変わってないので当たり前.) 入力時に石像の状態求めておけば早くなるんじゃね? などと思って変更, 提出. なんか Runtime Error (RE) だらけ.
5 完阻止されている気分になる.
一度 F 問題を読んでみる.
いろいろ図を描いてるうちに, グラフっぽい, 自分より上の人数数えればいいんじゃね? と思いつく.
幅優先を実装, しかし WA.
順位関係の情報に高橋君 (参加者 1) が入ってない (1 3
とか 3 1
とかがない) ことあるんじゃね? と思って修正するも WA.
三項演算子を if 文に変えてみる.
当然 WA.
提出結果をよく見てみると, (参加当時) 最後の 5 つだけが WA になってた.
えー, コーナーケースあるの...?
なんだろう...
列のループの条件をミスってて無限ループしてた. 修正して提出, WA (と TLE). オーダーを下げる方法が思いつかない.
コーナーケースを考えてみる. ...... 思いつかない. 適当に弄って投げまくる. もちろん全部 WA (最終提出は 174:50).
トートバッグもらえないのめっちゃ悔しかったけど, どうしようもなかった. つらい.
4 完 (A, B, C, D), 4 WA (B, D 各 2 WA), 52 位だった. 目標 (5 完) 達成ならず... (悔しい) ちなみに, E, F はそれぞれ 6 WA した.
4完勢にトートバッグ惜しかったで賞欲しい
— jun (@nahcnuj) December 7, 2014
(切実)
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 国内予選に, 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; }